Оптимальный способ искать слова в текстовой (txt) базе.

[Alex Cones]

Собственно имеется 3 базы слов в формате txt : G.txt S.txt P.txt
В базах соответственно содержатся Глаголы, Существительные, Прилагательные.
Я ввожу слово (например в edit, причем я не указываю, что это, глагол, существительное или прилагательное) теперь мне нужно узнать строку в базе, в которой "затаилось" это слово. Причем найти его там не проблема, важно найти его с наибольшей скоростью. В общем задача - получить номер строки и тип слова.
Мои наработки:
1) Я считаю неоптимальным грузить базу с помощью AssignFile и после считывать каждую строку. Долго и нудно.
2) Возможно будет быстрее грузить весь файл в StringList, затем циклом пройтись по всем строкам или попробовать поискать Pos`ом.
3) Может есть другие способы, более быстрые?

P.S. Отрезок базы G.txt:

...
СТОИТЬ СТОИЛ СТОИЛА СТОИЛО СТОИЛИ СТОЮ СТОИТ СТОЯТ
РЕЗАТЬ РЕЗАЛ РЕЗАЛА РЕЗАЛО РЕЗАЛИ РЕЖУ РЕЖЕТ РЕЖУТ
...

[Lime]

Если грузить только слова с первой буквы , 2+3+ ? не грузить весь файл в программу а там же проходится по строкам ?

[Alex Cones]

Дело в том, что компьютер будет получать целую фразу, а потом выяснять все про каждое слово. Так что побуквенно... В смысле даже в готовой фразе?

P.S. Только что посчитал объем баз. В общем выходит около 1-2 мегов на базу.

[grenles]

может попытаться для файла сделать дополнительный файл индексов.
Вроде, как это делают в БД.
ну хотя бы примитивно.
G.ind для G.txt
где в G.ind
А с 1-100
Б с 100 - 1200
....
Тогда читать надо будет не весь файл, а блок.

Даа, вопрос - а слова в файлах отсортированны?

[mutabor]

3) Может есть другие способы, более быстрые?

Есть, с помощью дерева (но список должен быть отсортирован). Чем больше база, тем больше выигрыш в скорости по сравнению с обычным перебором.

[grenles]

Сообщение от mutabor

Есть, с помощью дерева (но список должен быть отсортирован). Чем больше база, тем больше выигрыш в скорости по сравнению с обычным перебором.

грубо говоря - каждый раз мы отсеиваем половину дерева, если оно двоичное?
Эдакий поиск делением списка на два по принципу - больше или меньше данное слово, чем искомое?

Дык, а время на построение дерева в памяти?

[mutabor]

грубо говоря - каждый раз мы отсеиваем половину дерева, если оно двоичное?
Эдакий поиск делением списка на два по принципу - больше или меньше данное слово, чем искомое?

Совершенно верно, это один из быстрых алгоритмов.

Дык, а время на построение дерева в памяти?

Ничего специально строить не надо. Дерево - объект умозрительный )

Если загрузить список в TStringList (пару мегабайт в памяти это не страшно на сегодняшний день, правда возможно подождать пару секунд пока он грузится, нужно будет) тогда список будет проиндексированный и можно быстро переходить на нужные позиции.
Загрузку можно сделать при старте программы, если такой способ с загрузкой в память не подходит, то наверное лучше отказаться от текстового файла в пользу бинарного со структурами - узлами дерева, а не просто строками, в структуре как минимум должны быть позиция левой ветки в файле, правой, и сама строка. Тогда можно будет открыть файл на чтение, и гулять по нему производя поиск, при этом без задержки на загрузку в память этого файла.

Прирост скорости в сравнении с простым перебором:
к примеру у вас 256 элементов в списке, если искать перебором, то в худшем случае вам понадобится 256 итераций. В аналогичном двоичном дереве чтобы добраться до крайней ветки, понадобится 8 итераций. Если же список увеличить до 65000 то время поиска перебором увеличится в тысячи раз, в дереве же нужно всего 16 итераций!

[Serge_Bliznykov]

прежде всего, размеры в несколько мегабайт это детский лепет!
вот, рекомендую ознакомится с темой
Загрузка и поиск в большом файле
там, кстати, несколько полезных программ (в исходниках, разумеется).
Так вот, 160 МБ файл (10 000 000 строк) через TStringList.LoadFromFile загружается около 14 секунд.
файл размером 32 Мб (1000000 строк) грузится около секунды...

во-вторых, слова должны быть ОТСОРТИРОВАНЫ.
Тогда можно воспользоваться методом поиска TSTRINGLIST.FIND (он как раз ищет только в отсортированных списках).

[Alex Cones]

Строки будут отсортированны в алфавитном порядке. Это раз. Насчет стринглиста я не сомневался. Это два.

может попытаться для файла сделать дополнительный файл индексов.
Вроде, как это делают в БД.
ну хотя бы примитивно.
G.ind для G.txt
где в G.ind
А с 1-100
Б с 100 - 1200

Дело в том, что новые слова будут добавляться регулярно, даже из тех фраз, что он будет "кушать", так что перестраивать всю базу и список к ней?

слова должны быть ОТСОРТИРОВАНЫ.

Только в алфавитном? Тогдга не проблема. Проблема будет в том, что-бы записать в базу слово с буквы "а".

[Serge_Bliznykov]

Дело в том, что новые слова будут добавляться регулярно, даже из тех фраз, что он будет "кушать", так что перестраивать всю базу и список к ней?

ну вот. Только всё так хорошо придумали.. А жизнь вносит свои суровые коррективы!

Да, Вы правы, это слабое место данного способа.
Варианта решения собственно два:
— если слова добавляются редко (сколько при этом слов добавляется, абсолютно неважно!) - то просто пересортировывать (это всего одна строчка кода - TStringList.Sort; )
— если же добавление слов происходит достаточно часто,
то надо мутить так, как это сделано в любой СУБД - добавлять индексы и при каждом изменении файла перестраивать индекс. Ну, как Вы, вероятно, догадываетесь, это намного сложнее!

p.s. А Вам не кажется, что Вы занимаетесь изобретением велосипеда? Любая СУБД легко и эффективно решит Вашу задачу. Почему не хотите воспользоваться СУБД?!