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

From

Sergei Emantayev ()

To

Vladimir A. Pertzel

Date

2002-06-30T15:23:54Z

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:afmjjo$987$1@host.talk.ru...

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

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

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

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