Степень похожести строк (Ivan Petrov и Иван Петров)?

Question

[FilimoniC]

Добрый день!

Существует проблемка:

В виду перевода с одной инфраструктуры на другую, необходимо связаять ФИО на русском и ФИО на транслите.

Имеющиеся данные:

Полное корректное ФИО на русском (Иванов Петр Федорович) и транслитированное ФИ\ФИо\ФИО (Ivanov Petr\Ivanov Petr F.\Ivamov Petr Fedorovich)


Требуется

Функция, которая принимает ФИО, транслитирированное из полного русского ФИО роботом (по правилам) и список пар [ФИО;id], где ФИО — транслитирированное человеком ФИО, почти по правилам. При том в списке ФИО может не быть отчества или оно может быть сокращено.


Требуется:

Вернуть список формата
ФИОтрансл | id | степень похожести


То есть, например,
F(toTranslit('Иванова Юлия Мымрова'),$ListTranslit)

даст
Ivanova Yulia Mymrova | BBB1123 | 130

Ivanova Julia M. | AAA5543 | 100

Ivanova Ylia | CCC2234 | 95


Подскажите, есть ли подобное решение или хотя бы алгоритм сравнения похожести строк, дающий оценку похожести в некоторых условных единицах

Comments

[FilimoniC]

Нашел Алгоритм «Расстояние Левинштейна» Подскажите, насколько он применим?

И уточнение: Алгоритм преобразования заранее предопределен, есть робот, но когда в 1й тнфраструктуре заводились пользователи, робота не было, и было много ошибок преобразования человеческими ресурсами (привет от «Я», «Ю», «Ц», «Ч», «Щ» и т.д.)

Answer 1

[jdponomarev]

Вполне применим.
Можно попробовать для каждого ФИО построить все возможные транслитерации и потом посчитать для всех расстояние Левинштейна и найти наиболее похожее ФИО.

Тут можно посмотреть схему транслитерации
akmac.narod.ru/st/st9.htm

Answer 2

[ssbb]

Про определение похожести строк: habrahabr.ru/qa/1186/

Answer 3

[Otkrick]

Sphynx умеет из коробки, PostgreSQL тоже умеет. Метод Левинштейна для поиска ошибок, он создавал проблемы для имен вроде Чон(«Chon» /«Сhyohn»)

Answer 4

[xmoonlight]

Как определить похожесть двух строк?