Найти последовательные индексы подстрок

Question

Учитывая строку поиска и строку результата (которая гарантированно содержит все буквы строки поиска, без учета регистра, по порядку), как я могу наиболее эффективно получить массив диапазонов, представляющих индексы в строке результата, соответствующиек буквам в строке поиска?

Желаемый вывод:

substrings( "word", "Microsoft Office Word 2007" )
#=> [ 17..20 ]

substrings( "word", "Network Setup Wizard" )
#=> [ 3..5, 19..19 ]
#=> [ 3..4, 18..19 ]   # Alternative, acceptable, less-desirable output

substrings( "word", "Watch Network Daemon" )
#=> [ 0..0, 10..11, 14..14 ]

Это поле для автозаполнения поиска.Вот скриншот из инструмента , похожего на Ртуть , который подчеркивает буквы, как я и собираюсь сделать.Обратите внимание, что - в отличие от моего идеального вывода выше - этот скриншот не предпочитает более длинные одиночные совпадения.

Результаты теста

Сравнительный анализ текущих рабочих результатов показывает, что регулярное выражение @ toklandответ на основе в основном такой же быстрый, как и решения на основе StringScanner, которые я выдвинул, с меньшим количеством кода:

               user     system      total        real
phrogz1    0.889000   0.062000   0.951000 (  0.944000)
phrogz2    0.920000   0.047000   0.967000 (  0.977000)
tokland    1.030000   0.000000   1.030000 (  1.035000)

Вот эталонный тест:

a=["Microsoft Office Word 2007","Network Setup Wizard","Watch Network Daemon"]
b=["FooBar","Foo Bar","For the Love of Big Cars"]
test = { a=>%w[ w wo wor word ], b=>%w[ f fo foo foobar fb fbr ] }
require 'benchmark'
Benchmark.bmbm do |x|
  %w[ phrogz1 phrogz2 tokland ].each{ |method|
    x.report(method){ test.each{ |words,terms|
      words.each{ |master| terms.each{ |term|
        2000.times{ send(method,term,master) }
      } }
    } }
  }
end

Answer 1

Чтобы начать с чего-то, как насчет этого?

>> s = "word"
>> re = /#{s.chars.map{|c| "(#{c})" }.join(".*?")}/i # /(w).*?(o).*?(r).*?(d)/i/
>> match = "Watch Network Daemon".match(re)
=> #<MatchData "Watch Network D" 1:"W" 2:"o" 3:"r" 4:"D">
>> 1.upto(s.length).map { |idx| match.begin(idx) }
=> [0, 10, 11, 14]

И теперь вам нужно только построить диапазоны (если они вам действительно нужны, я думаю, отдельные индексытоже нормально).

Answer 2

Вот последний участник, который делает ход, приближаясь к финишной черте.

код

def substrings( search_str, result_str )
  search_chars = search_str.downcase.chars
  next_char = search_chars.shift
  result_str.downcase.each_char.with_index.take_while.with_object([]) do |(c,i),a|
    if next_char == c
      (a.empty? || i != a.last.last+1) ? a << (i..i) : a[-1]=(a.last.first..i)
      next_char = search_chars.shift
    end   
    next_char
  end
end

демо

substrings( "word", "Microsoft Office Word 2007" ) #=> [17..20]
substrings( "word", "Network Setup Wizard" )       #=> [3..5, 19..19]
substrings( "word", "Watch Network Daemon" )       #=> [0..0, 10..11, 14..14]

тест

              user     system      total        real
phrogz1   1.120000   0.000000   1.120000 (  1.123083)
cary      0.550000   0.000000   0.550000 (  0.550728)

Answer 3

Модуль Ruby's Abbrev является хорошей отправной точкой.Он разбивает строку на хеш, состоящий из уникальных ключей, которые могут идентифицировать полное слово:

require 'abbrev'
require 'pp'

abbr = Abbrev::abbrev(['ruby'])
>> {"rub"=>"ruby", "ru"=>"ruby", "r"=>"ruby", "ruby"=>"ruby"}

Для каждого нажатия клавиши вы можете выполнить поиск и посмотреть, есть ли совпадение.Я бы отфильтровал все ключи короче определенной длины, чтобы уменьшить размер хеша.

Ключи также дадут вам быстрый набор слов для поиска совпадений подслов в вашей исходной строке.

Для быстрого поиска, чтобы увидеть, есть ли совпадение подстроки:

regexps = Regexp.union(
  abbr.keys.sort.reverse.map{ |k|
    Regexp.new(
      Regexp.escape(k),
      Regexp::IGNORECASE
    )
  }
)

Обратите внимание, что он экранирует шаблоны, которые позволяют вводить символы, такие как ?, *или ., и будут рассматриваться как литералы, а не специальные символы для регулярных выражений, как они обычно обрабатываются.

Результат выглядит так:

/(?i-mx:ruby)|(?i-mx:rub)|(?i-mx:ru)|(?i-mx:r)/

Регулярное выражение match будетвернуть информацию о том, что было найдено.

Поскольку union «ИЛИ» паттернов, он найдет только первое совпадение, которое будет самым коротким вхождением в строке.Чтобы исправить это, переверните сортировку.

Это должно дать вам хорошее начало в том, что вы хотите сделать.

---

РЕДАКТИРОВАТЬ: Вот код, чтобы прямо ответить на вопрос.Мы были заняты на работе, поэтому потребовалось несколько дней, чтобы вернуть это:

require 'abbrev'
require 'pp'

abbr = Abbrev::abbrev(['ruby'])
regexps = Regexp.union( abbr.keys.sort.reverse.map{ |k| Regexp.new( Regexp.escape(k), Regexp::IGNORECASE ) } )

target_str ='Ruby rocks, rub-a-dub-dub, RU there?'
str_offset = 0
offsets = []
loop do
  match_results = regexps.match(target_str, str_offset)
  break if (match_results.nil?)
  s, e = match_results.offset(0)
  offsets << [s, e - s]
  str_offset = 1 + s
end

pp offsets

>> [[0, 4], [5, 1], [12, 3], [27, 2], [33, 1]]

Если вы хотите, чтобы диапазоны заменили offsets << [s, e - s] на offsets << [s .. e], который вернет:

>> [[0..4], [5..6], [12..15], [27..29], [33..34]]

Answer 4

Вот моя реализация:

require 'strscan'
def substrings( search, master )
  [].tap do |ranges|
    scan = StringScanner.new(master)
    init = nil
    last = nil
    prev = nil
    search.chars.map do |c|
      return nil unless scan.scan_until /#{c}/i
      last = scan.pos-1
      if !init || (last-prev) > 1
        ranges << (init..prev) if init
        init = last
      end
      prev = last
    end
    ranges << (init..last)
  end
end

А вот более короткая версия, использующая другой метод утилиты (также необходимый для ответа @ tokland):

require 'strscan'
def substrings( search, master )
  s = StringScanner.new(master)
  search.chars.map do |c|
    return nil unless s.scan_until(/#{c}/i)
    s.pos - 1
  end.to_ranges
end

class Array
  def to_ranges
    return [] if empty?
    [].tap do |ranges|
      init,last = first
      each do |o|
        if last && o != last.succ
          ranges << (init..last)
          init = o
        end
        last = o
      end
      ranges << (init..last)
    end
  end
end

Answer 5

Я не думаю, что есть какие-то встроенные методы, которые действительно могут помочь с этим, вероятно, лучший способ - это просмотреть каждую букву в слове, которое вы ищете, и создать диапазоны вручную.Ваш следующий лучший вариант, вероятно, будет построить регулярное выражение, как в ответе @ tokland.