Хэширование слов

Простое и банальное решение, весь словарь грузить в память. Размер позволяет. Скорость работы с памятью в сотни раз быстрее, чем с винтом.

И при этом использовать двоичный поиск в массиве без всякого хэширования.

2^19 = 524288

То есть за 20 простых сравнений слово будет найдено что быстрее чем вычислить хэш функцию и потом разбираться с совпадениями.

В каком массиве? Тут поиск будет по слову, а это дольше, чем по идентификатору, разве нет?

И нет разницы, как искать - хоть дихотомией, хоть прямым перебором. Все равно дольше, чем в БД по ключу.

@---,---`-----

Массивов может быть несколько для каждой длины слова отдельно что позволит как лучше использовать память при этом ускоряя поиск и обновление так возможно и обойтись 16 бит идентификаторами для слов при этом используя длину слова в качестве неявного расширения пространства идентификаторов. А если для Вашей задачи достаточно скорости последовательного поиска то словарь можно даже сжать причем намного плотнее чем обычный текст.

Artisan,

Cпасибо. Я над этим думала. Это, на мой взгляд, половинчатый выход из положения. Подумаю еще - обязательно расскажу, что придумала.

p.s. Цветок, надо полагать, к празднику. Спасибо!

Если не секрет, над чем работаете ? Новый поисковик ?

Maxim Golubev, Вроде уже рассказывала. Пока все, что я делаю - проба сил, набивание шишек и прочие неприятные вещи века.

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

Maxim Golubev,

Все верно. Поиск идет по т.н. "обратному индексу". Прямой хранить, наверное, придется.

Все зависит от точной постановки задачи, можно вообще обойтись без явных идентификаторов и вместо них использовать номера слов в массивах отдельно для каждой длины слова.