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

From

Andrey Tarasevich ()

To

Sergei Emantayev

Date

2002-07-03T00:47:47Z

Area

RU.ALGORITHMS

From: "Andrey Tarasevich" <atarasevich@telocity.com>

Sun Jun 30 2002 14:04, Sergei Emantayev wrote to Sergei Emantayev:

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

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

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

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

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

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

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

Best regards,
Андрей.

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)