Быстрый доступ к ключу в файле (без загрузки всего файла в память)

Question

Справочная информация: я пишу приложение на c # для Windows Mobile, которое будет искать определения (научные) из словаря из файловой системы. Файл выглядит так (файл имеет 100K + записей):

 Word1:Meanings(2)
-meaning 1 bla bla bla
-meading 2 bla bla bla
[...]

Пользователь должен быть в состоянии ввести слово и получить значение как можно быстрее. Пользователи будут искать только 1 или 2 слова. Для этого я создал второй файл с отсортированным списком с фактическим словом и байтовым смещением в файле словаря. Пример:

word1:12344
word2:32241
word3:298

Я просматриваю свой «индекс» (простой цикл по всем строкам и сравниваю, если он равен), а затем «произвольно обращаюсь» к файлу словаря, используя смещение байтов. Проблема в том, что это все еще медленно. Я попытался загрузить индекс в массив / список / хеш-таблицу, но из-за медленного ввода-вывода это занимает слишком много времени (около 20 секунд для загрузки индекса). Это плохо, потому что пользователь обычно ищет только одно слово. Поэтому я ищу какой-то тип реализации n-дерева, который может работать непосредственно с файлом (без обхода всего индекса). У кого-нибудь есть совет, как это сделать? Мое текущее решение выглядит так (но с ошибками и грязью): Новый индекс имеет следующий формат:

a:FileOffsetInDictionary:FileOffsetOf"ab" //the first 2 character starting with a
b:FileOffsetInDictionary:FileOffsetOf"ba"
c:FileOffsetInDictionary:0 //"0" means that their are no words starting with "c" (just for example)
[...]
ab:FileOffsetInDictionary:FileOffsetOf"aba"
ac:FileOffsetInDictionary:878878 //(just some random values for illustration)
[...]
ba:FileOffsetInDictionary:456
[...]
aba:FileOffsetInDictionary:2342
[...]

И поиск осуществляется следующим образом:

Users enter the word "Tree"
Look for "t" in index by looping through the index
if "t" found then goto FileOffsetOf2Digit
if "tr" found then goto FileOffsetOf3Digit
[...]
[actually recursively coded]

Answer 1

Если вам нужно реализовать это самостоятельно, вы должны создать три всего вашего корпуса. Это быстрее, чем B-деревья, красно-черные деревья или хеш-таблицы для известных данных, и может хранить частичные совпадения. То есть если вы назовете его с «T», он вернет первый экземпляр символа «T» в вашем корпусе. Если затем вызвать его с помощью «r» и указать первый экземпляр «T», он вернет первый экземпляр «Tr» в корпусе без необходимости сначала искать «T» и т. Д.

Answer 2

Правильный ответ, вероятно, будет указывать вам использовать b-tree индекс, который идеально подходит для дискового индекса такого типа, или еще лучше, если вы говорите о мобильном 6.5 и более ранних версиях.может использовать базу данных SQL CE.И вы можете найти несколько реализаций, но, не сумев, вы могли бы сделать следующее:

Используя что-то в соответствии с вашей текущей идеей индексного файла, сделайте каждую индексную запись фиксированного размера.Таким образом, если вы знаете, что слово никогда не будет больше 50 символов и смещение будет помещаться в четырехбайтовое целое число, вы можете создать записи в индексном файле, которые будут 54 байта (при условии ASCII для слов, измените соответственно).Затем вы можете выполнить двоичный поиск в индексном файле, а не сканировать весь файл для доступа к каждой записи.