Python-сообщество

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

В питоновской регулярке наиболее уязвимые места итак написаны на С, поэтому скорость врядли будет существенно выше, если использовать полностью сишный аналог.
Возможно, будет полезно Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …)
И еще, на сколько может быть простым движок регулярки. Хотя здесь небольшой финт ушами - в примере отсутствует компилляция строки во внутренее представление, но написать самому ее будет не так уж и сложно.

Отредактировано (Авг. 9, 2008 16:15:55)

ZAN Спасибо, буду изучать.
http://paste.lisp.org/display/24849 - красивый код, но голову можно сломать %)

Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …) - очень интересная ссылка. Отправная точка для дальнейших исследовний.

Отредактировано (Авг. 10, 2008 19:15:23)

На данный момент, остановился на том, что написал небольшой DFA (детереминированого автомата состояний).
Но в нем есть минус в том, что чтобы задать условия прасинга - надо описывать его в конструкция питона. Что не сложно, но кода много. И пока задаешь - мысль расползается.
Теперь понятно, почему в регулярках и в других подобных парсерах используется специальный синтаксис.

Отредактировано (Авг. 10, 2008 17:32:18)

вопрос немного в сторону, а как часто меняется формат текста которого необходимо парсить ?
если не очень часто, то лучше оставить так как есть, через время у тебя будет набор процедур для парсинга типовых конструкций

asv13 как ты - еще не пробовал ANTLR?

В процессе поисков набрел на вот такую штуку:
http://bisqwit.iki.fi/source/regexopt.html - оптимизатор регулярок.
Мне правда не помогло сильно (на четверть время сократил) но может кому пригодится.

Сточил я 2 мыши, стоптал 2 клавиатуры, потратил столько электроэнергии, что можно было-бы обеспечить потребности среднего города в течении одной пикосекунды…
Испробовал все, до чего мог дотянутся.

И результат весьма неожиданный: самый быстрый результат (при приемлемом удобстве составления шаблонов) дал egrep вызываемый через subprocess.

На нем на данный момент и остановился. =)

shiza
самый быстрый результат (при приемлемом удобстве составления шаблонов) дал egrep вызываемый через subprocess.

UXIX-Way таки ралит ;)

shiza
На данный момент, остановился на том, что написал небольшой DFA (детереминированого автомата состояний).
Но в нем есть минус в том, что чтобы задать условия прасинга - надо описывать его в конструкция питона. Что не сложно, но кода много. И пока задаешь - мысль расползается.
Теперь понятно, почему в регулярках и в других подобных парсерах используется специальный синтаксис.

А можно посмотреть код DFA? Насколько он сложен? Пытался свой написать, упрощал структуру как мог, но очень быстро запутался в условиях и бросил. Что-то изменять, это полдня надо снова вникать в написанное.

Постоянная головная боль с разбором текстов. Сейчас сделал разбор текста с finite state machine, но на языке J.

Убил все выходные, уж очень синтаксис языка непривычный. В этом языке есть готовый оператор для реализации конечного автомата, он включает в себя задание таблицы переходов по условию из одного состояния в другое. http://kinetic.dnsalias.org/~metlov/dictionary/d332.htm В каждой ячейке таблицы два числа - первое указывает на номер строки и меняет состояние а второе на номер функции, например 0 - ничего не делать, 1 - запомнить индекс начала слова, 2 - запомнить слово (атом, строку и т.п.) и создать индекс для следующего, 3-запомнить слово, но следующее не задавать. На входе уже не текст даже а подготовленный пошагово одномерный массив из чисел. Сделать его пошагово - элементарно и прозрачно, легко понять какое число какому условию сопоставлено.

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

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

Отредактировано (Фев. 16, 2009 11:13:40)

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

Именно поэтому не нужно его хардкодить. Я не случайно сбрасывал ссылку в этой ветке - там описано, как создать ДКА по регулярному выражению. Чтобы реализовать этот алгоритм нужно фактически написать парсер строки в AST регулярки. Парсер, кстати, может предствавлять собой некий “неизменяемый” конечный автомат.

Это тоже будет полезно:
http://habrahabr.ru/blogs/algorithm/50349/