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

From

Sergei Emantayev ()

To

Sergei Emantayev

Date

2002-06-30T14:04:47Z

Area

RU.ALGORITHMS

From: Sergei Emantayev <sergeie@ectel.com>


Sergei Emantayev <sergeie@ectel.com> пишет:

SE> Теперь у меня есть обратная задача: есть таблица
SE> слов,
SE> на вход приходит некоторый текст. Нужно найти все
SE> слова
SE> из таблицы, которые находятся во входном тексте.
SE> Можно опять же взять линейный проход по таблице +
SE> алгоритм
SE> типа Морриса-Пратта. Но это не устраивает.
SE> Я посмотрел алгоритм Карпа-Рабина, там при
SE> сравнении
SE> используются хеши. Можно было бы захешировать
SE> таблицу
SE> и при сравнении искать хеши, но проблема в том
SE> что все
SE> паттерны в таблице имеют разную длину. Т.е. при
SE> поиске во
SE> входном тексте я не знаю, какой длины взять
SE> следующую
SE> подстроку для вычисления хеша. Можно конечно
S*> *> рать минимальную
SE> длину слова в таблице для хеша, мне кажется, что
SE> это
SE> неподходящее решение.
S*> *> уду признателен за любые советы и идеи.

Поделюсь тем решением, которое более-менее меня удовлетворяет
на данный момент. Слова загоняются в этакое префиксное дерево,
оно еще "trie" называется. Далее, по дереву бегают несколько 
поинтеров. Когда приходит новая буква из текста, поинтеры 
продвигаются на следующие узлы дерева. Тот кто не смог найти
нужную букву, выбывает из игры. 

Тем не менее, буду рад услышать о других интересных решениях 
данной проблемы.

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