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