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

From

Sergei Emantayev ()

To

Vladimir A. Pertzel

Date

2002-06-30T17:27:38Z

Area

RU.ALGORITHMS

From: Sergei Emantayev <sergeie@ectel.com>


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

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

VA>> Ну да. Т.е. если у меня входная таблица порядка
VA> 10000 слов,
VA>> по 10 букв в каждом слове, то получаем порядка
VA> 100000 состояний.
VA>> А ведь для каждого состояния нужно еще и саму
VA> подстроку хранить
VA>> и еще что-то, или я не прав? Получаются большие
VA> расходы памяти.
VA>> А хочется все-таки все в памяти хранить, чтобы
VA> максимально быстро
VA>> работало.

VA> Во-первых, про "плюс один" я ошибся, потому,
VA> что  пустую строку уже учел.
VA> Во-вторых, если найденные строки могут
VA> перекрываться, то сами строки из подсчета
VA> подстрок
VA> можно исключить.
VA> В третьих, подстрок длины 1 будет не 10000, а,
VA> скажем, 26.

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

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

можно не хранить

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

VA> а
VA> алфавит -- 256 символов. То есть 30000 строк по
VA> 257
VA> указателей, около 8-10 мегабайт. Вам решать,
VA> подойдет
VA> ли алгоритм для конкретного приложения.

30000 * 257 * (размер ук-ля = 4 байта) = 30Мб

VA> В четвертых, можно в 8 раз сократить требования к
VA> памяти,
VA> если известно, что используются только буквы
VA> кириллицы,
VA> но для этого каждый поступающий байт надо
VA> пропускать
VA> через таблицу хеширования, которая каждую букве
VA> преобразует в её номер, а прочие символы - в 0. Я
VA> сегодня нечто с этой идеей уже отправлял.

У меня правда не кириллица, но все же размер 
алфавита можно сократить до 64 символов 
плюс-минус.

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


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