|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladimir A. Pertzel 2:5020/400 30 Jun 2002 18:10:21
To : Sergei Emantayev
Subject : Re: Обратная задача: поиск в таблице паттернов
--------------------------------------------------------------------------------
"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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
