Алгоритм поиска логической схожести ФИО по базе (ардженикидзе = орджоникидзе = ...)

Question

[Shing]

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

Поэтому
ардженикидзе = орджоникидзе = арджоникидзе = арджиникидзе = ардженикидзэ
и так далее, то есть вариантов написания может быть много, но логически при человеческом прочтении ясно, что это на 99% одна и та же фамилия.

В поиске участвует фамилия, имя, отчество.
Везде могут быть неверные написания. Но общий логический «код» должен сойтись.

Ордженикидзэ Алексей Вечеславович = Ардженикидзе Алексий Вячеславович

Есть идеи по алгоритму?

Answer 1

[ertaquo]

На хабре было несколько статей на эту тему:
habrahabr.ru/blogs/algorithm/117063/
habrahabr.ru/blogs/algorithm/115147/
habrahabr.ru/blogs/algorithm/114947/
В PHP есть встроенные функции алгоритмов Soundex и Metaphone, но работают ли они с русским языком — не знаю.

Answer 2

[Всеволод]

Я когда-то использовал этот алгоритм в Делфи: www.delphikingdom.ru/asp/viewitem.asp?catalogid=722
Он хорош тем, что позволяет настраивать чувствительность. И он действительно работал.
Думаю, его без труда можно портировать с Паскаля на любой другой язык.

Answer 3

[philpirj]

Postgres + trigram. Осторожно, зарубежный язык.