Каков наиболее эффективный способ поиска в массиве текста массива регулярных выражений? - PullRequest
3 голосов
/ 14 апреля 2011

Я ищу наиболее эффективный способ поиска большого количества текста (± 1/2 КБ) для многих регулярных выражений, хранящихся в массиве.

Пример кода:

patterns = [/patternA/i,/patternB/i,/patternC/m,...,/patternN/i]

content  = "Lorem ipsum dolor sit amet, consectetur... officiam id est laborum."

r = patterns.collect{ |pattern|

  pattern unless ( content =~ pattern ).blank?

}.compact

Где r теперь содержит шаблоны, соответствующие строке content .

Ответы [ 4 ]

2 голосов
/ 14 апреля 2011

Если вас интересует, соответствует ли какой-либо из шаблонов тексту, рассмотрите возможность объединения всех шаблонов в одно большое регулярное выражение, используя оператор регулярного выражения 'или', и один раз скомпилируйте это гигантское регулярное выражение.

Например, если ваши шаблоны: A, B, C, создайте одно регулярное выражение в форме A|B|C

Извините, я не знаю Ruby, но, надеюсь, вы можете превратить это в код (:

Примечание: Вот как обрабатываются файлы .hgignore в Mercurial в последний раз, когда я смотрел. В этом случае есть тысячи имен файлов, которые выбрасываются в одном большом регулярном выражении, что более эффективно, чем те имена файлов, которые выбрасываются в каждом из сотен меньших регулярных выражений.

2 голосов
/ 14 апреля 2011

Решение 1

Сделайте это:

r = patterns.select{|pattern| content =~ pattern}

Поскольку строка огромна, лучше реализовать этот метод на String, а не на чем-тоиначе, потому что передача большого аргумента кажется медленной.

class String
  def filter_patterns patterns
    patterns.select{|r| self =~ pattern}
  end
end

и используйте его как:

content.filter_patterns(patterns)

Решение 2

оно имеетограничения, что каждое регулярное выражение не включает именованный / пронумерованный захват.

combined_regex = Regexp.new(patterns.map{|r| "(?=[.\n]*(#{r.source}))?"}.join)
content =~ combined_regex

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

r = patterns.select.with_index{|pattern, i| Regexp.last_match[i]}

Добавление

Дано:

dogs = {
  'saluki' => 'Hounds',
  'russian wolfhound' => 'Hounds',
  'italian greyhound' => 'Hounds',
   ..
}
content = "Running in the fields at great speeds, the sleek saluki dog comes from..."

вы можете сделать это:

combined_regex =
    Regexp.new(dogs.keys.map{|w| "(?=[.\n]*(#{w}))?"}.join, Regexp::IGNORECASE)
content =~ combined_regex
r = patterns.select.with_index{|pattern, i| Regexp.last_match[i]}
"This article talks about #{r.collect{|x| dogs[x]}.to_sentence}."
=> "This article talks about Hounds."

Чтобы избежать выводов типа This article talks about Hounds, Hounds and Hounds., вы можете добавить uniq.

"This article talks about #{r.uniq.collect{|x| dogs[x]}.to_sentence}."
1 голос
/ 15 апреля 2011

Как насчет:

text = 'Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor magna'
targets = [ /(am?et)/, /(ips.m)/, /(elit)/, /(magna)/, /([Ll]or[eu]m)/ ]

regex = Regexp.union(targets)

hits = []
text.scan(regex) { |a| hits += a.each_with_index.to_a }
r = hits.select{ |w,i| w }.map{ |w,i| targets[i]} # => [/([lL]or[eu]m)/, /(ips.m)/, /(am?et)/, /(elit)/, /(magna)/]

Это работает для возврата совпавших шаблонов в том порядке, в котором слова были найдены в тексте.

Вероятно, есть способ сделать это, используя именованные захваты.

0 голосов
/ 15 апреля 2011

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...