Из этого вопрос: как понять, что дима = дмитрий или дим = дмитр?
Используем только, если расстояние большое!
Сначала уравниваем "веса" некоторых букв: е=ё, р=ш=н.
Проверки:
1. Смена первых соседних букв местами: 123 -> 132 (
Дима->
Дмитрий) или 123 -> 213 (...)
2. Сдвиг с добавлением новой буквы впереди: 12 -> 012 (
Лена->
Елена,
Катя->
Екатерина,
Лёша->
Алексей)
3. Совпадение первых двух букв с паттерном внутри слова и затем проверка: или две согласных подряд, или совпадение 3-х букв подряд:
Саша -> Алек
сандр,
Кеша -> Ино
кентий.
Это без словаря, но со словарём - будет надёжнее!