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

Question

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

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

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

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

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

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

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

Сейчас я сопоставляю их с регулярными выражениями - однако это невыносимо медленно. Я начал с 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 ++, но это проблематично. Просто потому, что я не писал в коде 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, чтобы посмотреть, сможем ли мы пойти дальше, но на данный момент я очень доволен результатами духа.

Смежный вопрос: Эффективный запрос одной строки для нескольких регулярных выражений.

Answer 1

Я бы предложил

• Повышение духа или
• Antlr , если грамматика сложная;
• Xpressive если немного проще,
• Tokenizer и код ручной работы, если он тривиален.

Удачи

Answer 2

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

Answer 3

Вот один из способов сделать это, если вы использовали 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 сначала пытается найти последовательность цифр, за которыми следует граница слова. Этот матч должен начинаться с того места, где остановился последний матч (или с начала строки первого матча). Поскольку m/ \G( \d+\b )/gcx использует флаг c, если строка не соответствует этому регулярному выражению, perl не сбрасывает pos() и следующее совпадение начинается в той же позиции, чтобы попробовать другой шаблон.

Answer 4

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

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

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

Answer 5

См. Сопоставление регулярных выражений может быть простым и быстрым (но медленно в Java, Perl, PHP, Python, Ruby, ...) . В зависимости от объема ваших данных и от того, насколько сложным является ваше регулярное выражение, может быть просто быстрее написать собственную логику анализа.

Answer 6

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

Answer 7

ОК, это проясняет ситуацию (история покерных рук). Я предполагаю, что вы делаете статистический инструмент (фактор агрессии, пошел на вскрытие, добровольно положил $ в банк и т. Д.). Я не уверен, почему вам нужны чрезмерные скорости для этого; даже если вы используете мультитач с 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 8

Еще одна идея, если у вас есть для этого элегантный четырехъядерный или восьмиъядерный основной сервер.

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

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

Answer 9

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

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

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

Answer 10

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

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

regex1|regex2|regex3|...|regex15

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

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