|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergei Emantayev 2:5020/400 30 Jun 2002 17:27:38
To : Vladimir A. Pertzel
Subject : Re: Обратная задача: поиск в таблице паттернов
--------------------------------------------------------------------------------
Vladimir A. Pertzel <voldemar@relhum.org> пишет:
VA> "Sergei Emantayev" <sergeie@ectel.com> wrote in
VA> message news:afmpnl$rfh$1@host.talk.ru...
VA>> Hу да. Т.е. если у меня входная таблица порядка
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
