Каков наилучший способ анализа текста по множеству (15+) регулярных выражений в каждой строке?
У меня есть текст, который я должен отсканировать, и каждая строка содержит как минимум 2, а иногда и четыре части информации. Проблема в том, что в каждой строке может быть 1 из 15-20 разных действий.
в ruby текущий код выглядит примерно так:
text.split ("\ n"). каждый делает |line| # около 20 раз
..............
выражения ['действия']. каждый делает |pat, reg| # около 20 раз
.................
Это, очевидно, "ПРОБЛЕМА". Мне удалось сделать это быстрее (в C++ с 50% -ным запасом), объединив все регулярные выражения в одно, но это все еще не та скорость, которая мне требуется - мне нужно БЫСТРО разобрать тысячи этих файлов!
Прямо сейчас я сопоставляю их с регулярными выражениями - однако это невыносимо медленно. Я начал с ruby и переключился на C++ в надежде, что получу повышение скорости, а этого просто не происходит.
Я случайно прочитал о разборке PEG и грамматики, но это выглядит довольно сложно для реализации. Это направление, в котором я должен идти, или есть разные маршруты?
в основном я разбираю истории покерных рук, и каждая строка истории рук обычно содержит 2-3 бита информации, которую мне нужно собрать: кем был игрок, сколько денег или какие карты вызвало действие... и т.д..
Пример текста, который необходимо проанализировать:
похороненные посты $5 Кнопка находится в месте № 4 *** ОТКРЫТЫЕ КАРТЫ *** Приступить к Mayhem 31337 [8s Ad] Sherwin7 складывает OneMiKeee складывает syhg99 звонит 5 долларов похоронен поднимает до 10 долларов
После того как я соберу эту информацию, каждое действие превращается в узел XML.
Прямо сейчас моя рубиновая реализация этого намного быстрее, чем моя C++, но это проблема. Просто потому, что я не писал в коде c более 4-5 лет
ОБНОВЛЕНИЕ: я не хочу размещать весь код здесь, но пока мои руки / секунды выглядят следующим образом:
588 рук в секунду - boost::spirit в C++ 60 рук в секунду - 1 очень длинное и сложное регулярное выражение в C++ (все регулярные выражения вместе взятые) 33 руки в секунду - обычный стиль регулярных выражений в ruby
В настоящее время я тестирую antlr, чтобы посмотреть, сможем ли мы пойти дальше, но на данный момент я очень доволен результатами духа.
Смежный вопрос: Эффективный запрос одной строки к нескольким регулярным выражениям.
10 ответов
Я бы предложил
- Boost Spirit или
- Antlr, если грамматика сложна;
- Xpressive, если это немного проще,
- Токенайзер и код ручной работы, если он тривиален.
Удачи
Boost.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 и грамматике, но это выглядит довольно сложно для реализации. Это направление, в котором я должен идти, или есть разные маршруты?
Лично я полюбил ПЭГ. Возможно, потребуется немного времени, чтобы освоиться с ними, однако я думаю, что они настолько более ремонтопригодны, что это явная победа. Я считаю, что код разбора является источником множества неожиданных ошибок, поскольку вы обнаруживаете новые крайние случаи во входных данных. Декларативные грамматики с нетерминалами для меня легче обновлять, когда это происходит, по сравнению с циклическим и условным кодом регулярного выражения. Именование - это мощно.
В Ruby есть Treetop, который является генератором парсера, который использует PEG. Недавно я обнаружил, что довольно приятно заменить регулярный тяжелый рукописный парсер короткой грамматикой.
ОК, это проясняет ситуацию (история покерных рук). Я предполагаю, что вы делаете статистический инструмент (фактор агрессии, пошел на вскрытие, добровольно положил $ в банк и т. Д.). Я не уверен, почему вам нужны чрезмерные скорости для этого; даже если вы используете мультитач с 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 приходит на ум.
Убедитесь, что вы прочитали каждую руку только один раз. Не читайте все данные снова после каждой раздачи, вместо этого сохраняйте, например, хеш-таблицу уже проанализированных идентификаторов раздач.
Попробуйте простой тест на Perl. Читайте о функции "изучение". Что я мог бы попробовать это:
- Прочитать весь файл или большое количество строк, если эти файлы очень большие в одну строку
- По мере добавления добавляйте номер строки в начало каждой строки.
- "изучить" строку. Это строит таблицу поиска за символом, может быть большим.
- Запустите совпадения регулярных выражений в строке, ограниченной символами новой строки (используйте модификаторы регулярных выражений m и s). Выражение должно извлечь номер строки вместе с данными.
- Установите элемент массива, индексированный по номеру строки, для данных, найденных в этой строке, или сделайте что-нибудь еще умнее.
- Наконец, вы можете обрабатывать данные, хранящиеся в массиве.
Я не пробовал, но это может быть интересно.
Совпадают ли совпадения с регулярными выражениями? То есть, когда два или более регулярных выражений соответствуют одной и той же строке, они всегда совпадают с разными частями строки (без перекрытия)?
Если совпадения никогда не пересекаются, запустите поиск, используя одно регулярное выражение, объединяющее 15 регулярных выражений, которые у вас есть:
regex1|regex2|regex3|...|regex15
Используйте группы захвата, если вам нужно определить, какие из 15 регулярных выражений совпадают.
Поиск ваших данных один раз для длинного регулярного выражения будет быстрее, чем поиск в 15 раз. Насколько быстрее зависит от используемого вами механизма регулярных выражений и сложности ваших регулярных выражений.
Еще одна идея, если у вас есть для этого достаточно элегантный четырехъядерный или восьмиъядерный сервер.
Создайте конвейер обработки, который разделяет работу. Первый этап может разрезать файлы в одну игру или раздачу, а затем записывать каждый из них в один из восьми каналов второго этапа, которые читают данные, обрабатывают их и каким-либо образом выводят, возможно, в базу данных на другом компьютере.
По моему опыту, эти многопроцессорные конструкции на основе конвейеров почти так же быстры и намного проще в отладке, чем многопоточные. Также было бы легко настроить кластер машин, используя сетевые сокеты вместо каналов.
Для такой проблемы я бы просто закрыл глаза и использовал генератор Lexer+Parser. Вы можете победить это с помощью ручной оптимизации, но гораздо проще использовать генератор. Кроме того, он становится более гибким, когда ввод внезапно меняется.