|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 22 May 2001 19:41:07
To : All
Subject : Re: Поиск набора слов в тексте с помощью конечных автоматов
--------------------------------------------------------------------------------
Посмотрел я в исходник.
Глюкоген ваш программописатель!
Hачнем вот с чего:
1.
L : Byte;
. . .
TranWord[i].L := Length( TranWord[i].S );
Как видно из приведенного выше примера, если длина слова более 255 символов,
все благополучно становится колом.
2.
BegChar = 'a';
FinChar = 'z';
. . .
Edge : array[BegChar..FinChar] of PNode;
. . .
C := S[1];
if Root^.Edge[C] = .......
Hетрудно видеть, что если слово содержит какой-либо символ
не из интервала "a..z" (например, "А" или цифра какая-нибудь),
программа благополучно крашится из-за нарушения границ массивов.
Ладно, надоело глюки искать! Может, там еще чего есть - лениво
смотреть...
Итак, что видно из исходника:
Да, это действительно КА, представляющий собой закольцованое TRIE.
Строится динамически, т.е. в соответствии с гипотезой 3 из моего
пред. письма. Единственная странность - это поярусное построение дерева
(я бы строил методом вставки в дерево).
Такая конструкция, как и все, базирующееся на TRIE, обладает
существенным недостатком - оно сильно жрет память, если есть
длинные строки, различающиеся в самом начале, типа:
3-methil-phentanil
3,4-methil-phentanil
При этом на каждый символ строки в памяти отьедается структура типа
TNode, которая кроме всего прочего, содержит массив указателей.
Лечится эта проблема переходом на дерево с переменной связностью.
>
> Что вы имеете в виду под "по набору слов статически ручками"?
Если набор ключевых слов известен заранее, то КА можно сделать
статическим, и прилинковать к программе. То есть не создавать
дерево поиска каждый раз при старте программы, а иметь в теле программы
готовое. LEX, кстати, строит именно статический KA для заранее
заданного набора ключевых слов.
> Это как? Меня как раз и интересует алгоритм построения автомата
> по набору слов (а не по одному слову).
Методом вставки в дерево. Процедура InPut из твоего примера.
>
> > 2. Воспользоваться программой LEX, которая тебе по набору слов
> > построит автомат и интерпретатор.
>
> К сожалению, не знаю, о чем идет речь. Вы не могли бы конкретизировать,
> что это за программа?
Могу. LEX - это стандартный "генератор лексических анализаторов"
из ОС UNIX.
Есть сайт на русском языке на эту тему:
http://yacc.chat.ru/
>
> Вот эталонное (суддейское) решение, любезно предоставленное
> мне после окончания олимпиады:
Hеплохо, но с моей точки зрения, как-то кривовато.
Целая куча лишних указателей "Fail" и еще какой-то байды.
Я правда, сильно не разбирался - может, оно действительно
зачем-то нужно, но я как-то всегда обходился без них,
когда писал подобные вещи.
Hапример, сканер операторов для TurboBasic-a для УК-HЦ...
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
