Есть следующая задача.
Имеется база большого объема (порядка миллиона записей), представляющая собой словарь (например, список всех возможных фамилий или список всех возможных улиц всех городов России).

Необходимо проверить введенное значение на наличие в словаре, и при отсутствии в словаре предложить наиболее близкое по написанию слово из словаря.
ПРИЧЕМ ПРИ ЭТОМ ДОЛЖНА ДОСТИГАТЬСЯ МАКСИМАЛЬНАЯ ПРОИЗВОДИТЕЛЬНОСТЬ!

Первое, что приходит на ум — если по точному совпадению на нашли, делаем перебор по всему словарю, для каждого имеющегося в словаре значения считаем отличие от введенного значения (например, используя алгоритм Левенштейна), и в качестве альтернативы предлагаем те слова из словаря, у которых отличие от введенного значения минимальное.

Сомнения вызывает производительность такого подхода при большом объеме словаря — миллион раз вызывать функцию определения отличия (Левенштейна) слишком подгрузит систему.

Существуют ли какие-нибудь методы, позволяющие оптимизировать этот процесс (может можно создать какие-нибудь индексы по словарям, которые бы помогли оптимизировать алгоритм)?