Каков наилучший способ разбора текста текста против нескольких (15+) регулярных выражений в каждой строке?

Question

У меня есть текст, который я должен отсканировать, и каждая строка содержит как минимум 2, а иногда и четыре части информации. Проблема в том, что каждая строка может быть 1 из 15-20 разных действий.

рубина текущий код выглядит примерно так:

 
text.split("\n").each do |line| #around 20 times.. 

.............. 

     expressions['actions'].each do |pat, reg| #around 20 times 

................. 

Это, очевидно, «ПРОБЛЕМА». Мне удалось сделать это быстрее (на C++ на 50%), объединив все regexen в один, но это все еще не такая скорость, которую мне нужно - мне нужно разобрать тысячи этих файлов FAST!

Прямо сейчас я сопоставляю их с регулярными выражениями - однако это невыносимо медленно. Я начал с Ruby и перешел на C++ в надежде, что я получу ускорение скорости, и этого просто не происходит.

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

В основном я разбираю истории рук в покере, и каждая строка истории рук обычно содержит 2-3 бита информации, которую мне нужно собрать: , кем был игрок, сколько денег или какие карты влечет за собой действие. и т.д ..

Пример текста, который должен быть проанализирован:

 
buriedtens posts $5 
The button is in seat #4 
*** HOLE CARDS *** 
Dealt to Mayhem 31337 [8s Ad] 
Sherwin7 folds 
OneMiKeee folds 
syhg99 calls $5 
buriedtens raises to $10 

После того как я собирать эту информацию каждое действие превращена в узел XML.

Прямо сейчас моя реализация ruby ​​намного быстрее, чем моя C++, но это проблема. Просто потому что я не написал в коде С в течение более 4-5 лет

UPDATE: Я не хочу, чтобы получить возможность отправлять весь код здесь, но до сих пор мои руки/второй выглядеть следующим образом:

 
588 hands/second -- boost::spirit in c++ 
60 hands/second -- 1 very long and complicated regex in c++ (all the regexen put together) 
33 hands/second -- normal regex style in ruby 

В настоящее время я тестирую antlr, чтобы узнать, можем ли мы пойти дальше, но по состоянию на данный момент я очень доволен результатами духа.

Связанный вопрос: Efficiently querying one string against multiple regexes.

Answer 1

Я хотел бы предложить

• Boost Spirit или
• Antlr, если грамматика является сложной;
• Xpressive, если это немного проще,
• Tokenizer и ручной код, если это тривиально.

Успехов

Answer 2

Boost.Spirit фантастическая библиотека, которая позволяет сделать детальный анализ синтаксического анализатора, а поскольку анализатор генерируется и компилируется прямо в коде, должны быть гораздо быстрее, чем динамически вычисленного решения. Синтаксис в основном выполняется с помощью шаблонов выражений (причудливый термин для множества перегруженных операторов), что означает, что вы фактически записываете их прямо в свой код.

Answer 3

См. Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...). В зависимости от объема ваших данных и того, насколько сложным является ваше регулярное выражение, может быть просто быстрее написать собственную логику синтаксического анализа.

Answer 4

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

Если матчи никогда не перекрывают друг друга, запустить поиск, используя одно регулярное выражение, которое объединяет 15 регулярных выражений у вас есть сейчас:

regex1|regex2|regex3|...|regex15 

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

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

Answer 5

Вот один из способов сделать это, если вы использовали Perl.
скопирован из perldoc perlfaq6

while (<>) { 
    chomp; 
    PARSER: { 
     m/ \G(\d+\b )/gcx && do { print "number: $1\n"; redo; }; 
     m/ \G(\w+  )/gcx && do { print "word: $1\n"; redo; }; 
     m/ \G(\s+  )/gcx && do { print "space: $1\n"; redo; }; 
     m/ \G([^\w\d]+)/gcx && do { print "other: $1\n"; redo; }; 
    } 
} 

Для каждой строки, цикл PARSER первого пытается сопоставить ряд цифр с последующей границей слова. Это совпадение должно начинаться с того места, где осталось последнее совпадение (или начало строки в первом матче). Так как использует флаг c, если строка не соответствует этому регулярному выражению, perl не сбрасывает pos(), и следующий матч начинается с той же позиции, чтобы попробовать другой шаблон.

Answer 6

Попробуйте простой тест на Perl. Читайте о функции «исследования». То, что я мог бы попробовать это:

• Читать весь файл или большое количество строк, если эти файлы очень большие в одну строку
• Добавить номер строки в начале каждой строки, как вы идете.
• «изучать» строку. Это создает таблицу поиска по символу, может быть большой.
• Выполнение совпадений регулярных выражений в строке, ограниченных символами новой строки (используйте модификаторы m и s regex). Выражение должно извлекать номер строки вместе с данными.
• Установите элемент массива, индексированный номером строки, на данные, найденные на этой строке, или сделайте что-нибудь еще более умное.
• Наконец, вы можете обрабатывать данные, хранящиеся в массиве.

Я не пробовал, но это может быть интересно.

Answer 7

Еще одна идея, если у вас есть spiffy quad или oct core server для этого.

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

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

Answer 8

ОК, это делает вещи более ясными (истории рук покера). Я предполагаю, что вы делаете инструмент статистики (коэффициент агрессии, пошел на вскрытие, добровольно вложил $ в банк и т. Д.). Я не уверен, зачем вам нужны чрезмерные скорости для этого; даже если вы многозадачны с 16 таблицами, руки должны щекотать только с умеренной скоростью.

Я не знаю Ruby, но в Perl я бы сделал небольшое заявление о переключении, в то же время получая значимые части в 1 доллар, 2 доллара США и т. Д. По моему опыту, это не медленнее, чем создание строки сравнение, а затем разделение линии другими способами.

HAND_LINE: for ($Line) 
    { /^\*\*\* ([A-Z ]+)/ and do 
     { # parse the string that is captured in $1 
      last HAND_LINE; }; 
     /^Dealt to (.+) \[(.. ..)\]$/ and do 
     { # $1 contains the name, $2 contains the cards as string 
      last HAND_LINE; }; 
     /(.+) folds$/ and do 
     { # you get the drift 
      last HAND_LINE; }; }; 

Я не думаю, что вы действительно можете сделать это быстрее. Поместите проверки на линии, которые больше всего присутствуют на первой позиции (вероятно, сложения), и те, которые встречаются редко (начиная с новой руки, "*** NEXT PHASE ***").

Если вы обнаружите, что фактическое чтение файла является узким местом, вы можете взглянуть на то, какие модули вы можете использовать для обращения к большим файлам; для Perl, Tie::File приходит на ум.

Убедитесь, что вы читали каждую руку только один раз. Не читайте все данные снова после каждой руки, вместо этого продолжайте, например. хэш-таблица идентификаторов рук уже проанализирована.

Answer 9

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

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

В Ruby есть Treetop, который является генератором синтаксического анализатора, который использует PEG. Недавно мне было очень приятно заменять регулярный синтаксический анализатор с регулярным выражением краткой грамматикой.

Answer 10

Для решения этой проблемы я просто закрыл глаза и использовал генератор Lexer + Parser. Вы можете побить это с помощью ручной оптимизации, но гораздо проще использовать генератор. Кроме того, это намного более гибко, когда вход внезапно меняется.