|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 03 Jul 2002 00:47:47
To : Sergei Emantayev
Subject : Re: Обратная задача: поиск в таблице паттернов
--------------------------------------------------------------------------------
Sun Jun 30 2002 14:04, Sergei Emantayev wrote to Sergei Emantayev:
SE>> Теперь у меня есть обратная задача: есть таблица
SE>> слов,
SE>> на вход приходит некоторый текст. Hужно найти все
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
