Ускорьте мой лексический алгоритм

Question

Я делю потенциально большую строку (скажем, 20 МБ, хотя это совершенно произвольно) на токены, определенные списком регулярных выражений.

Мой текущий алгоритм использует следующий подход:

1. Все регулярные выражения оптимизированы, чтобы иметь утверждение нулевой ширины ^ в начале их
2. Для каждого регулярного выражения в списке я пытаюсь #slice! входная строка
3. Если мы #slice! что-нибудь, мы получили совпадение И входная строка была продвинута, готовая найти следующий токен (так как #slice! изменяет строку)

К сожалению, это медленно, что связано с #slice! на длинной строке... кажется, что изменение больших строк в ruby ​​не быстро.

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

Текущий алгоритм в (проверенном, работающем) псевдокоде:

  rules = {
    :foo => /^foo/,
    :bar => /^bar/,
    :int => /^[0-9]+/
  }

  input = "1foofoo23456bar1foo"
  # or if you want your computer to cry
  # input = "1foofoo23456bar1foo" * 1_000_000

  tokens = []

  until input.length == 0
    matched = rules.detect do |(name, re)|
      if match = input.slice!(re)
        tokens << { :rule => name, :value => match }
      end
    end

    raise "Uncomsumed input: #{input}" unless matched
  end

  pp tokens
  # =>
  [{:rule=>:int, :value=>"1"},
   {:rule=>:foo, :value=>"foo"},
   {:rule=>:foo, :value=>"foo"},
   {:rule=>:int, :value=>"23456"},
   {:rule=>:bar, :value=>"bar"},
   {:rule=>:int, :value=>"1"},
   {:rule=>:foo, :value=>"foo"}]

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

Answer 1

String#match()Метод имеет двухпараметрическую версию, которая будет соответствовать регулярному выражению, начинающемуся с определенной позиции символа в строке. Вам просто нужно получить символ "один из последних совпадений" из предыдущего матча в качестве начальной позиции для нового матча.

В непроверенном, незапущенном псевдокоде:

input = "foo"
input_pos = 0
input_end = input.length

until input_pos == input_end do
  matched = rules.detect do |(name, re)|
    if match = input.match(re, input_pos)
        tokens << { :rule => name, :value => match }
        input_pos = match.post_match
    end
  end
end

Answer 2

Возможно, я упрощаю, но String#scan, скорее всего, превзойдет все остальное:

tokens = input.scan(/foo|bar|\d+/).map{|m| {:value => m, :rule => rules.find{|name,re| m =~ re}[0]}}

или в целом:

rules = {
    :foo => /foo/,
    :bar => /bar/,
    :int => /[0-9]+/
}
tokens = input.scan(Regexp.union(rules.values)).map{|m| {:value => m, :rule => rules.find{|name,re| m =~ re}[0]}}