|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Krotoff 2:5020/400 02 May 2002 20:24:56
To : Valentin Davydov
Subject : Re: поиск подстроки в таблице
--------------------------------------------------------------------------------
Valentin Davydov <val@sqdp.trc-net.co.jp> wrote:
>>Задачка такая: есть таблица слов, необходимо организовать поиск
>>подстроки, точнее подслова в таблице. Вопрос в том, какова должна
>>быть структура таблицы, чтобы поиск был максимально эффективным.
>>Hапример если заранее известно, что искомое слово является префиксом
>>(или суффиксом), то можно воспользоваться бинарным деревом.
>>А если общий случай - поиск в середине слова? Можно взять алгоритм
>>типа Морриса-Пратта, но тогда придется линейно просматривать всю
>>таблицу.
>>Существует ли какое-то более красивое решение?
VD> Если памяти не жалко, а таблица статичная (словарь), то можно хранить
VD> таблицы хэшей (т.е. 256 массивов индексов слов, содержащих данную букву,
VD> 65536 массивов индексов слов, содержащих данное буквосочентание и т.д.).
Как вариант (если таблица небольшая, меняется редко, а искать подстроки
нужно часто и быстро).
struct {
int i, j, p;
const char *str;
};
создаешь списк структур такого вида. Для каждой iой jой клетки таблицы
strlen(table[i][j]) структур. Член str каждой pой структуры указывает
на p-ый символ в строке table[i][j].
Затем этот список сортируешь по полю str (лексикографический порядок
строк). Подстроку ищешь бинарным поиском в получившемся списке, либо,
если искать нужно _очень_ быстро, строишь над структурами один из
вариантов дерева поиска (те же B-деревья).
Если нужен качественный результат - есть подстрка или нет - поля i,j,p
структуры не нужны. Если нужно находить подстроку с точностью до
клетки в таблице - не нужно поле p.
--
Успехов,
Саша.
--- ifmail v.2.15dev5
* Origin: Он знал Сашу Бло. (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
