Учитывая строку, как перебрать много регулярных выражений, чтобы найти совпадение?

Question

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

Неэффективно ли просто повторятьчерез хэш регулярных выражений, пробуя каждое регулярное выражение в строке, затем выводя значение?Конечно, я не могу явно перечислить все возможные отображения типа string => integer, но кажется плохим пытаться сопоставить каждое регулярное выражение в связке регулярных выражений.

Answer 1

RegexpTrie , которого не было рядом, когда я в последний раз искал что-то подобное, помогает с такой проблемой:

require 'regexp_trie'

sentence = 'life on the mississippi'
words_ary = %w[the sip life]

words_regex = /\b(?:#{RegexpTrie.union(words_ary, option: Regexp::IGNORECASE).source})\b/i 
# => /\b(?:(?:the|sip|life))\b/i

words_to_ints = words_ary.each_with_index.to_h
# => {"the"=>0, "sip"=>1, "life"=>2}

sentence_words = sentence.split
# => ["life", "on", "the", "mississippi"]

word_hits = sentence_words.map { |w| w[words_regex] }
# => ["life", nil, "the", nil]

nil означает, что в регулярном выражении не было совпадения этого слова.

words_to_ints.values_at(*word_hits)
# => [2, nil, 0, nil]

Опять же, nil означает, что совпадений не было. nil значения можно игнорировать, используя:

word_hits = sentence_words.map { |w| w[words_regex] }.compact
# => ["life", "the"]

words_to_ints.values_at(*word_hits)
# => [2, 0]

Аналогично, если вы хотите отсканировать предложение на предмет совпадения слов вместо отдельных слов:

require 'regexp_trie'

sentence = 'life on the mississippi'
words = %w[the sip life]

words_regex = /\b(?:#{RegexpTrie.union(words, option: Regexp::IGNORECASE).source})\b/i 
# => /\b(?:(?:the|sip|life))\b/i

words_to_ints = words.each_with_index.to_h
# => {"the"=>0, "sip"=>1, "life"=>2}

word_hits = sentence.scan(words_regex)
# => ["life", "the"]

words_to_ints.values_at(*word_hits)
# => [2, 0]

---

В Perl есть действительно полезный модуль для такого рода вещей, который называется Regexp :: Assemble , который позволяет объединять регулярные выражения в один большой, а затем искать строку, возвращая попадания. Вы можете попросить его указать, какой шаблон использовался, если хотите знать.

В Ruby такого модуля нет, но это довольно близко:

patterns = {
  /(foo)/ => 1,
  /(bar)/ => 2
}

pattern_union = Regexp.union(patterns.keys)

pattern_union # => /(?-mix:(foo))|(?-mix:(bar))/

str = 'foo some text'

if (pattern_union =~ str)

  # these show what are being processed...
  pattern_union.match(str).captures # => ["foo", nil]
  pattern_union.match(str).captures.zip(patterns.keys).find_all{ |c| c[0] }.map{ |c| c[1] } # => [/(foo)/]

  # process it...
  matched_pattern_values = patterns.values_at(*pattern_union.match(str).captures.zip(patterns.keys).find_all{ |c| c[0] }.map{ |c| c[1] })

  # here's what we got
  matched_pattern_values # => [1]

end

Возможно, есть способ сделать это в одну строку, но это работает.

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

См. " Существует ли эффективный способ выполнения сотен подстановок текста в Ruby? " для получения дополнительной информации об использовании Regexp :: Assemble из Ruby.

Answer 2

Просто сделайте, как вы предлагаете, переберите хэш регулярных выражений / чисел и верните первое, соответствующее строке:

def find_match(regex_mapping, str)
  regex_mapping.each do |regex, n|
    return n if str =~ regex
  end
  return nil
end

Единственное, что можно сказать об эффективности, это то, что это, вероятно, в любом случае не имеет значения. Просто напишите свой код как можно более четко и просто, а затем, в конце концов, если он замедлится, запустите его через профилировщик (например, совершенно потрясающий perftools.rb ) и посмотрите, что горячие точки есть. Оптимизация тех. Не оптимизируйте, пока не написали код.

Тем не менее, простая оптимизация, которую вы можете сделать в этом случае, которая вам ничего не стоит, состоит в том, чтобы поместить регулярные выражения в хэш отображения в таком порядке, чтобы на первом месте было наиболее вероятное совпадение, и таким образом меньше сравнений должны быть сделаны (но это вероятностная оптимизация, время выполнения наихудшего случая остается тем же самым). Это относится только к Ruby 1.9, поскольку хэши не сохраняют порядок вставки в 1.8.

Answer 3

Вы говорите «это кажется плохим», но, в конце концов, вы, вероятно, ничего не можете сделать: вам придется сопоставлять каждую строку с последовательностью регулярных выражений, пока не будет найдено одно.Вы можете запомнить результаты и проявить смекалку другими способами, например, «если это регулярное выражение не сработает, остальные 10 также не сработают», но это все те оптимизации производительности, которые вам могут не понадобиться.

Самой простой оптимизацией может быть создание групп регулярных выражений с общими характеристиками и сначала проверка, в какой группе находится строка. Если строка = ~ / ^ a / равна нулю, все остальные регулярные выражения, проверяющие строку, начинающуюся сне нужно больше тестироваться.

Answer 4

Это зависит от того, насколько сложны ваши регулярные выражения. Если вы можете поместить их в блоки захвата и отобразить блоки захвата обратно на целые числа, которые вам нужны, то все будет в порядке.

Например:

(is).*(test)

имеет два блока захвата. Это будет соответствовать:

This is a test

Захваты будут 1:is и 2:test

Вы можете быстро попробовать его на http://www.rubular.com/