Re: Обратная задача: поиск в таблице паттернов

From

Vladimir A. Pertzel ()

To

Sergei Emantayev

Date

2002-06-30T18:10:21Z

Area

RU.ALGORITHMS

From: "Vladimir A. Pertzel" <voldemar@relhum.org>


"Sergei Emantayev" <sergeie@ectel.com> wrote in message news:afn0vl$ig3$1@host.talk.ru...

> Да и вообще подстроки можно не хранить. Если что-то
> нашли, то результат можно из входного потока
> восстановить.

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

> VA> Грубо говоря, в конечном автомате, каждое
> VA> состояние
> VA> есть структура, содержащая указатель на
> VA> возвращаемые
> VA> данные (не ноль тогда и только тогда, когда
>
> можно не хранить

Это или указатель на строку-образец поиска,
либо указатель на функцию (представитель класса),
которую (виртуальный метод которого) надо выполнить
по нахождении.
.......
> VA> состояний
> VA> будет около 30 тысяч (на основании своего опыта),
>
> ???? это я не понял почему,
> ну хорошо - пусть будет так.

Пример, ищем строку из набора:
КИТ
КОТ
КОК
КОЛ

состояния автомата соответствуют подстрокам
0: ""
1: К
2: КИ
3: КИТ
4: КО
5: КОТ
6: КОК
7: КОЛ
то есть их 8, что меньше, чем 3х4=12;

> Вообще, идея интересная, надо подумать как
> табличку посильнее сжать. Мне кажется, там
> будет много переходов в нулевое состояние -
> как бы эти нули повыковыривать?

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

Для развлечения можно попробовать построить
автомат для поиска одного слова "баобаб"
Обратите внимание, что в пятом состоянии
(после последовательности "баоба", буква "о"
переводит автомат не в нулевое состояние, а
в третье.


--- ifmail v.2.15dev5
 * Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)