[to leikind]
Я прекрасно знаю, что такое детерминированные и недетерменированные (и с эпсилон-переходами) конечные автоматы (хотя серьезно никогда этим не занимался, поэтому, буду рад, если мне посоветуют какие либо источники, ссылки в Internet и т. п.). Если вы не заметили, в своей программе я как раз и реализовал очень простой детерминированный конечный автомат. Я попробую вам это доказать.
Как известно ДКА это пятерка (Q, E, f, q0, F), где
Q - множество состояний;
E - входной алфавит;
f - функция переходов;
q0 - начальное состояние;
F - подмножество Q, определяющее множество допускающих состояний.
ДКА и регулярные выражения определяют эквивалентные регулярные языки.
Рассмотрим ДКА реализованный в моей программе (определен неформально ({} - множество)):
A = ({<после любого символа, не пробела>, <после пробела>}, {ASCII или ANSI, как угодно}, f, <после любого символа, не пробела>, {<после пробела>})
функцию f определим следующим образом:
Код: Выделить всё
._______________________________________________________________________________________________
| входной символ | любой символ, не пробел | пробел |
|_____ состояние _______________________________________________________________________________|
| --> <после любого символа, не пробела> | <после любого символа, не пробела> | <после пробела> |
| <после пробела> | <после любого символа, не пробела> | <после пробела> |
|_______________________________________________________________________________________________|
при каждом переходе дополнительно реализуется какое либо действие с выходным потоком. Например при переходе с <после любого символа, не пробела> в <после пробела> в выходной поток копируется пробел. А при переходе из <после пробела> в <после пробела> ничего не делается.
Надеюсь убедил.
По поводу обгона Perl'ом С. Как вы и говорили, слишком многое зависит от большого количества фактов. В данном случае я думаю дело в pcre. Опять же в Perl'е те же регекспы реализованы на С.
Теперь о том, что я яко-бы считаю что регулярные выражения медленны по-определению. Я такого никогда не говорил. У меня такого даже в мыслях не было. Регулярные выражения УНИВЕРСАЛЬНЫ.
Я писал: Сравни по скорости прогу на С, специально написанную под данную задачу, и ту же прогу на перле с регулярными выражениями. Я повторяю - СПЕЦИАЛЬНО НАПИСАННУЮ ПОД ДАННУЮ ЗАДАЧУ. То есть, в данном примере, нам не надо строить конечный автомат. Он уже реализован в самой программе. То есть мы проводим вычисления уже готовым автоматом, не заботясь о его построении.
Теперь (я немного отвлекусь от темы), о специфических задачах (не всегда связанных с поиском текста). Регекспы не решение всех проблем и иногда непосредственная реализация конечного автомата намного проще. В качестве примера приведу простую задачу:
Есть строка. Алфавит - {0, 1}. Она определяет двоичное число. Определить, делится ли оно, допустим, на 5.
Построим конечный автомат из 5-и состояний, каждое из которых определяется расширенной функцией переходов: если в результате деления на 5 уже прочитанной части числа, мы имеем остаток 0 - то мы в 0-ом состоянии, если 1 - то в 1-ом и т. д.):
Код: Выделить всё
_________1_________ 1
/ \ / \
_|/__ _________\___1_______ \|/ |
| ___ | _/_ _\_ _\| ___
|| 0 ||__1__\| 1 |__0__\| 2 |/__1__| 3 |/__0__| 4 |
||___|| /|___| /|___|\ |___|\ |___|
|_____| |\ \ / /|
| /|\ \ \_______/__0________/
| | \_______1________/
\_0_/
Это был граф конечного автомата:). Наверное прийдется пояснять таблицей, а то довольно криво получилось...
Код: Выделить всё
входной символ
0 1
_________________
сос- | 0 | 0 1
тоя- | 1 | 2 3
ния | 2 | 4 0
| 3 | 1 2
| 4 | 3 4
Итак, такой конечный очень просто запрограммированть и на чистом С и на асме. А теперь, регулярное выражение определяющее тот же регулярный язык, что и этот автомат:
Код: Выделить всё
(0 + 101 + 11(01)*001 + (100 + 11(01)*000)(1 + 0(01)*000)*(0(01)*001))*
Надеюсь, вы согласны, что такое регулярное выражение намного сложнее вывести, чем автомат.
Замечания:
1. Надеюсь правильно вывел. Делал это на бумаге (методом исключения состояний), поэтому мог ошибиться. Для заинтересовавшихся, могу написать прогу.
2. Запись приведенное здесь регулярного выражения отлична от принятой в UNIX. Не следует считать регекспы в UNIX стандартом, они не появились там сразу. Итак
а) объединения двух языков A и B (A + B). Например, A = {001, 100, 11} и B = {001, 101, 10}, то A + B = {001, 100, 101, 10, 11}.
б) конкатенация языков A и B (AB). Пример - A = {001, 100, 11} и B = {10}, то AB = {00110, 10010, 1110}.
в) итерация языка A (A*) - множество всех цепочек, которые можно образовать путем конкатенации любого количества цепочек из A. Пример - A = {0, 1}, A* - все цепочки, состоящие из нулей и единиц.
При поиске просто текста (без метасимволов) тоже есть более эффективные алгоритмы. Бойера-Мура, например. Эффективность - O (n/m) (n - длина текста, m - длина шаблона). Его я думаю, также можно приткнуть к регекспам, увеличив их эффективность. Например, если внутри регулярного выражения есть довольно длинный статический участок текста, то искать его по более эффективному алгоритму. А затем в обе стороны идти по шаблону с помощью регекспов. Но это только спонтанная догадка, ее не реализовывал, может как-нить попробую. Заинтересовавшимся, если будете искать алгоритм Бойера-Мура - ищите в первоисточнике. Почему-то и в Кнуте, и у Кормена там вместо 4-х эвристик всего 3. В результате в среднем время есть O(n/m), но в худшем все равно O(n*m)
И напоследок, никак не хотел поругаться, я вас очень уважаю и согласен со всем, что вы говорили, но не всегда я говорил о том, что вы доказывали, поэтому и получался спор. Но если вы снова с чем-то не согласны, я снова готов доказывать свою точку зрения (пока не докажу или пока вы не докажете мне, что я спорол явную чушь
)
а по ночам, девушка, я программы пишу ...
, а также хорошо ляжет на асм IA32, в то время, как библиотечные функции выльются в нечто большое (опять же - эти функции универсальны, а я написал узко специализированную функцию, где вся их мощь ни к чему).
