Реализация индекса для содержимого текстового файла

Question

У меня есть текстовый файл с огромным количеством слов (~ 50 МБ). Какая структура данных лучше всего подходит для построения индекса содержимого этого файла?

Или с помощью какой структуры данных я могу достичь наилучших результатов при поиске?

Заранее спасибо

Jijoy

Answer 1

Если ваши данные представляют собой словарь слов, то Trie хорошо подходит.

Answer 2

вы можете сократить накладные расходы на использование структур данных и написание алгоритма с использованием некоторой библиотеки, например [lucene] [1]

[1]: http://lucene.apache.org/. Я не очень уверен для вашего случая, будет ли это правильно, но когда в Java нужно создавать индексы для файлов и выполнять некоторые операции поиска, используя эти индексы, используя Люцен считается справедливым.

Answer 3

Если вы ищете полнотекстовую индексацию, то большой выбор - суффиксный массив:

http://en.wikipedia.org/wiki/Suffix_array

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

Answer 4

Дерево B + было бы весьма эффективным, если бы вы думали о нем как о таблице, однако, если бы это был просто большой список слов, вы могли бы попробовать деревья Фибоначчи.