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

From

Vladimir A. Pertzel ()

To

Sergei Emantayev

Date

2002-06-30T16:30:48Z

Area

RU.ALGORITHMS

From: "Vladimir A. Pertzel" <voldemar@relhum.org>


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

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

> Ну да. Т.е. если у меня входная таблица порядка 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)