|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladimir A. Pertzel 2:5020/400 30 Jun 2002 16:30:48
To : Sergei Emantayev
Subject : Re: Обратная задача: поиск в таблице паттернов
--------------------------------------------------------------------------------
"Sergei Emantayev" <sergeie@ectel.com> wrote in message
news:afmpnl$rfh$1@host.talk.ru...
VA> Если это набор фиксированых строк, то количество
VA> состояний автомата есть в точности количество
VA> всех начальных подстрок из набора, включая сами
VA> строки и пустую строку, плюс один.
VA> (Есть взаимно-однозначное соответствие.)
> Hу да. Т.е. если у меня входная таблица порядка 10000 слов,
> по 10 букв в каждом слове, то получаем порядка 100000 состояний.
> А ведь для каждого состояния нужно еще и саму подстроку хранить
> и еще что-то, или я не прав? Получаются большие расходы памяти.
> А хочется все-таки все в памяти хранить, чтобы максимально быстро
> работало.
Во-первых, про "плюс один" я ошибся, потому,
что пустую строку уже учел.
Во-вторых, если найденные строки могут
перекрываться, то сами строки из подсчета подстрок
можно исключить.
В третьих, подстрок длины 1 будет не 10000, а,
скажем, 26.
Грубо говоря, в конечном автомате, каждое состояние
есть структура, содержащая указатель на возвращаемые
данные (не ноль тогда и только тогда, когда автомат
что-то распознал) и вектор переходов, сиречь указателей
на следующее состояние, причем проиндексированный
элементами алфавита. В вашем случае число состояний
будет около 30 тысяч (на основании своего опыта), а
алфавит -- 256 символов. То есть 30000 строк по 257
указателей, около 8-10 мегабайт. Вам решать, подойдет
ли алгоритм для конкретного приложения.
В четвертых, можно в 8 раз сократить требования к памяти,
если известно, что используются только буквы кириллицы,
но для этого каждый поступающий байт надо пропускать
через таблицу хеширования, которая каждую букве
преобразует в её номер, а прочие символы - в 0. Я
сегодня нечто с этой идеей уже отправлял.
--
/\ /\ From the Holy Land, with respect
((ovo)) Vladimir A. Pertsel
():::() news://news.relhum.org
--PVA-------------------------------------------------
An ancestor of mine, by the name of Noah, was once the
commanding admiral of the combined fleets of my planet
--- ifmail v.2.15dev5
* Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
