В прошлой статье про морфологию я рассмотрел поиск по словам в прямом порядке - сначала сравниваем базовые строки, а потом их окончания. Поиск выполняется довольно быстро, если процент ошибок в словах довольно мал. При 20% ошибок на АМД 2500+ скорость поиска около 120000 слов в секунду. Но если слово не найдено нам прийдеться перебирать усеченный псевдохешем (первым и последним словом с такими двумя буквами) диапазон слов. Можно найти все словарные слова одна или несколько словоформ которых глючит - их примерно 25%. Записать их индексы в файл, ввести свойство слова HaveGluk и при загрузке базы загружать этот файл и заполнять это поле. Так можно сократить в 4ре раза поиск по ненайденым при прошлом поиске словам. Если псевдохеш считать не по двум буквам а по трем или четырем, то процент быдет значительно ниже.
Но есть и другой подход - искать сначала концы слова в окончаниях, а потом остаток слова в соответствующим им Базовым формам.
Вариантов окончаний около 120000, базовых форм около 180000. Т.е. нам нужно дополнительно 300.000 * (4 или 8 байт памяти). 1,2 - 2.4 метра. В зависимости сколько байт выделять на чек сумм. 4 байта быстрее будет работать на 32 битных машинах, второй вариант на 64 битных. Еще нам нужно для каждой модели окончаний добавить список всех базовых строк, которые на нее ссылаются. Это еще 4 байта на каждое словарное слово. И необходимо указывать номер Флексиамодели (2 байта) и номер окончания (1 байт). Это еще где-то 1 метр. Итого - 2.2-3.2 метра. Ссылки с флексиа модель (их 3000) на массивы индексов словарных слов. Займут (12000-24000 кб).
Итак мы считаем чек сумм всех окончаний. Упорядочиваем их по этой сумме. По длине их можно не разбивать - скорость бинарного поиска измениться не более чем на 10% процентов. Упорядочиваем для каждой флексиа модели словарные слова по чек сумму их базовой строки.
Теперь сам поиск. Для примера возьмем слово.
“ДЛИНА”
Один бинарный поиск займет максимум log2(120000)=19 шагов.
1. Ищем “А” в окончаниях. Максимум за 19 шагов находим одно из соответствующих окончаний.
По каждому соответствующему окончанию находим Флексиа Модель. Опять же бинарным поиском находим базовые строки с чек сумм равной “ДЛИН”. (в большинстве случаев Не больше 5 шагов).
2. Ищем “НА” в окончаниях. Находим одно из соответствующих окончаний.
По каждому соответствующему окончанию находим Флексиа Модель. Находим базовые строки с чек сумм равной “ДЛИ”.
…
Итак мы имеем в худшем случае (не найдено слово) MIN(Максимальная_длина_Окончания,Длина_слова)*(19 + Среднее_число_найденных_ФМ * 5))
MIN(Максимальная_длина_Окончания,Длина_слова) примерно равно 7ми.
Среднее_число_найденных_ФМ =30;
Около 7*170 шагов.
В случае прямого поиска при длине индекса псевдохеша 2ум, я получал около 280 шагов, но шаги были сложнее. Однако, если увеличить длину индекса псевдохеша до 3 или 4 рех мы получим гораздо меньшее число шагов. Это займет в случае 3ех (33*33*33 *4) 145 кило, в случае 4ех - 5 метров.
Среднее число шагов у прямого поиска меньше этого показателя у обратного. Так что при естественном проценте ошибок прямой поиск работает намного быстрее.
Другими словами, я читаю оптимальным по сочетанию память/скорость прямой поиск с длиной индекса равной трем.
