|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergei Emantayev 2:5020/400 02 May 2002 13:09:01
To : All
Subject : Обратная задача: поиск в таблице паттернов
--------------------------------------------------------------------------------
Теперь у меня есть обратная задача: есть таблица слов,
на вход приходит некоторый текст. Hужно найти все слова
из таблицы, которые находятся во входном тексте.
Можно опять же взять линейный проход по таблице + алгоритм
типа Морриса-Пратта. Hо это не устраивает.
Я посмотрел алгоритм Карпа-Рабина, там при сравнении
используются хеши. Можно было бы захешировать таблицу
и при сравнении искать хеши, но проблема в том что все
паттерны в таблице имеют разную длину. Т.е. при поиске во
входном тексте я не знаю, какой длины взять следующую
подстроку для вычисления хеша. Можно конечно брать минимальную
длину слова в таблице для хеша, мне кажется, что это
неподходящее решение.
Буду признателен за любые советы и идеи.
=====
Serge
mailto:sergeem*@yahoo.com
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
