Есть следующая задача.
Имеется база большого объема (порядка миллиона записей), представляющая собой словарь (например, список всех возможных фамилий или список всех возможных улиц всех городов России).
Необходимо проверить введенное значение на наличие в словаре, и при отсутствии в словаре предложить наиболее близкое по написанию слово из словаря.
ПРИЧЕМ ПРИ ЭТОМ ДОЛЖНА ДОСТИГАТЬСЯ МАКСИМАЛЬНАЯ ПРОИЗВОДИТЕЛЬНОСТЬ!
Первое, что приходит на ум — если по точному совпадению на нашли, делаем перебор по всему словарю, для каждого имеющегося в словаре значения считаем отличие от введенного значения (например, используя алгоритм Левенштейна), и в качестве альтернативы предлагаем те слова из словаря, у которых отличие от введенного значения минимальное.
Сомнения вызывает производительность такого подхода при большом объеме словаря — миллион раз вызывать функцию определения отличия (Левенштейна) слишком подгрузит систему.
Существуют ли какие-нибудь методы, позволяющие оптимизировать этот процесс (может можно создать какие-нибудь индексы по словарям, которые бы помогли оптимизировать алгоритм)?
Вот как раз
обсуждение этой темы на sql.ru — проблема одна и та же
Здравствуйте, E_g_0_r, Вы писали:
E__>Есть следующая задача.
E__>Имеется база большого объема (порядка миллиона записей), представляющая собой словарь (например, список всех возможных фамилий или список всех возможных улиц всех городов России).
E__>Необходимо проверить введенное значение на наличие в словаре, и при отсутствии в словаре предложить наиболее близкое по написанию слово из словаря.
E__>ПРИЧЕМ ПРИ ЭТОМ ДОЛЖНА ДОСТИГАТЬСЯ МАКСИМАЛЬНАЯ ПРОИЗВОДИТЕЛЬНОСТЬ!
E__>Первое, что приходит на ум — если по точному совпадению на нашли, делаем перебор по всему словарю, для каждого имеющегося в словаре значения считаем отличие от введенного значения (например, используя алгоритм Левенштейна), и в качестве альтернативы предлагаем те слова из словаря, у которых отличие от введенного значения минимальное.
E__>Сомнения вызывает производительность такого подхода при большом объеме словаря — миллион раз вызывать функцию определения отличия (Левенштейна) слишком подгрузит систему.
E__>Существуют ли какие-нибудь методы, позволяющие оптимизировать этот процесс (может можно создать какие-нибудь индексы по словарям, которые бы помогли оптимизировать алгоритм)?
Тут на самом деле две задачи:
1)Исправление очепяток.
2)Поиск близкого по звучанию слова.
Для второго нужен алгоритм вроде soundex, сходу нашел
http://community.livejournal.com/ru_php/1062493.html
Для первого можно сгенерировать все возможные опечатки (1-2 буквы) а потом лукапить по базе.
Можно совместить два алгоритма. Сначала сгенерить опечатки, потом пропустить слова через soundex, выбрать разные, по значениям soundex вытянуть слова из баз, после этого на клиенте Левенштейном.
При хорошем генераторе опечаток можно "Шо" исправлять на "Что".
