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

https://stackoverflow.com/questions/303830

08-07-2019
|

Вопрос

У меня есть текст, который мне нужно отсканировать, и каждая строка содержит как минимум две, а иногда и четыре части информации.Проблема в том, что в каждой строке может быть 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++, но это проблема.Просто потому, что я не писал код на Си уже более 4-5 лет.

ОБНОВЛЯТЬ:Я не хочу публиковать здесь весь код, но пока мои руки/секунды выглядят следующим образом:

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, чтобы посмотреть, сможем ли мы пойти дальше, но на данный момент я очень доволен результатами Spirit.

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

Решение

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

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

Удачи

Другие советы

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

Вот один из способов сделать это, если вы используете 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() и следующее совпадение начинается с той же позиции, чтобы попробовать другой шаблон.

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

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

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

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

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

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

regex1|regex2|regex3|...|regex15

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow