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

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

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

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]}}