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

From

Sergei Emantayev ()

To

Andrey Tarasevich

Date

2002-07-03T09:24:22Z

Area

RU.ALGORITHMS

From: Sergei Emantayev <sergeie@ectel.com>


Andrey Tarasevich <atarasevich@telocity.com> пишет:
AT> Sun Jun 30 2002 14:04, Sergei Emantayev wrote to
AT> Sergei Emantayev:

SE>>> Теперь у меня есть обратная задача: есть
AT> таблица
SE>>> слов,
SE>>> на вход приходит некоторый текст. Нужно
AT> найти все
SE>>> слова
SE>>> из таблицы, которые находятся во входном
AT> тексте.

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

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

AT> Для решения этой задачи существует известный
AT> алгоритм Ахо-Корасик, описанный в
AT> статье

AT> A. Aho and M. Corasick. Efficient string
AT> matching: an aid to bibliographic
AT> search. Communications of the Association for
AT> Computing Machinery 18 (1975),
AT> 333-340

AT> У меня есть бумажная копия. В Инете я этой статьи
AT> не видел.

http://www.win.tue.nl/~watson/2R080/opdracht/p333-aho-corasick.pdf

Спасибо, посмотрю на досуге.

AT> Они строят специальный автомат, который ищет
AT> строки в тексте "сразу все
AT> одновременно".

единственное, что меня пугает в автоматах, так это
размер памяти, необходимый для их построения. Так
что идеи с автоматами встречаю с осторожностью, хотя
Vladimir A. Pertzel несколько сдвинул мою позицию.

AT> Best regards,
AT> Андрей.

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