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

From

Sergei Emantayev ()

To

Vladimir A. Pertzel

Date

2002-06-30T19:43:34Z

Area

RU.ALGORITHMS

errol.relhum.org>
From: Sergei Emantayev <sergeie@ectel.com>


Vladimir A. Pertzel <voldemar@relhum.org> пишет:

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

Правила для того и созданы, чтобы их нарушать :)

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

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

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

И все таки, хотелось бы какую-нить статистическую
зависимость, хотя бы для случайных, равномерно 
распределенных ключей.

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

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

Да, так и есть :(

Словом, попытаюсь это дело реализовать и 
посмотреть что выйдет.

=====
Serge
mailto:sergeem*@yahoo.com
-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.ru (2:5020/400)