поиск по списку слов.

← →
aka (2011-12-19 17:48) [0]

Господа, писал я тут недавно программу, в которой есть словарь (относительно небольшой) с поиском списка слов по первым буквам.
Сделал тупо перебором - диапазон поиска списка сокращается, отталкиваясь только от первой буквы слова ( в списке заранее известна позиция слов от "a" до "я").
Итого грубо говоря получает сокращение длинны итерации в 33 раза взяв первую букву слова.

Делал в скорях, пока на нужное количество слов этого вполне достаточно.

Где посмотреть алгоритм сокращения диапазона поиска в 33*(кол-во первых букв)?
Это должно быть что-то вроде дерева поиска.

← →
Jeer © (2011-12-19 17:50) [1]

быстрее по хэш-у ( индексу )

← →
aka (2011-12-19 17:58) [2]

> быстрее по хэш-у ( индексу )

только что скачал:
Стивенс. Delphi Готовые алгоритмы.pdf
Бакнелл Джулиан М. «Фундаментальные алгоритмы и структуры да.pdf
и сразу, особо не вникая, мне показалось, что нужно делать по типу Б-дерева

← →
MBo © (2011-12-19 18:11) [3]

хэш-таблица или структура данных trie

← →
Ega23 © (2011-12-19 18:14) [4]

сортированный список

← →
Кто б сомневался © (2011-12-19 19:14) [5]

TStringList - там включаем сортировку. И Find (не помню как точно функция называется) .
Он сам все сделает (хэширует, сортирует итп)

← →
TUser © (2011-12-19 19:33) [6]

> Где посмотреть алгоритм сокращения диапазона поиска в 33*(кол-
> во первых букв)?
> Это должно быть что-то вроде дерева поиска.

Алгоритм Ахо-Корасика. Описан, например, в книге

Д. Гасфилд. Строки, деревья и последовательности в алгоритмах: информатика и вычислительная биология.

Ну и наверняка много где еще.

← →
И. Павел © (2011-12-19 19:36) [7]

> aka (19.12.11 17:48)

По моему, тут будет удобен обычный бинарный поиск: смотрите на слово в середине словаря. Если искомое слово "меньше" среднего, то отбрасываете вторую часть словаря, и повторяете поиск в первой.

Кстати, если создать словарь как индексированное поле в БД, как раз будет использоваться B-дерево для поиска.

Хотя не, это я глупость сказал.

Вот как раз недавно этим занимался.

1. Дин.массив строк.
2. TList<Integer> индексов строк. Сортировка здесь.
3. Идём дихотомией по TList<Integer>, сравниваем значение array[TList<Integer>] с Value. Делим пополам.

> Идём дихотомией

И пошел народ вразнос: дефки, вотка, пиво, кастрация..

поиск по списку слов. Найти похожие ветки