Поиск слов, содержащих заданные буквы

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

1. На базе морфологического словаря создается индекс основных форм слов с указанием возможных частей речи.
2. Буквы каждого слова преобразуются в нижний регистр и сортируются по алфавиту.
3. Из полученной строки формируются все возможные диграммы и триграммы. Использование перестановок четырех и более букв приводит к чрезмерному увеличению размера индекса и поэтому не применяется.
4. Для каждой буквы алфавита создается отдельный файл индекса. Это сделано с целью повысить надежность системы и уменьшить время создания базы.
5. В соответствующие индексы записываются полученные диграммы и триграммы, основная форма слова и возможные части речи.

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

Построенные таким образом индексы для русского и английского языка содержат около 120.000.000 записей и имеют объем 2.5 гигабайта.

Данный поисковый режим задуман и реализован на конференции Диалог-2001