|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergei Emantayev 2:5020/400 30 Jun 2002 14:04:47
To : Sergei Emantayev
Subject : Re: Обратная задача: поиск в таблице паттернов
--------------------------------------------------------------------------------
Sergei Emantayev <sergeie@ectel.com> пишет:
SE> Теперь у меня есть обратная задача: есть таблица
SE> слов,
SE> на вход приходит некоторый текст. Hужно найти все
SE> слова
SE> из таблицы, которые находятся во входном тексте.
SE> Можно опять же взять линейный проход по таблице +
SE> алгоритм
SE> типа Морриса-Пратта. Hо это не устраивает.
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
