Алгоритм сравнения текстовых строк?

Посоветуйте алгоритм сравнения строк с принципом работы вроде:


'Иван Иваныч Иванов' = 'Иванов Иван Иваныч'

'Иван Иваныч' ~ 'Иванов Иваныч'

'Иван Иваныч Иванов с утра ходит без штанов' != 'Иванов Иван Иваныч одевает штаны на ночь'


То есть, нужно найти коэффициент похожести строк, с учетом того, что слова в строке могут быть поменяны местами.

UPD: Кажется придумал:

a — массив слов первой строки

b — массив слов второй строки


n — количество слов первой строки

m — количество слов второй строки


Сij — коэффициент похожести слов a[i] и b[j] (можно использовать soundex или Levenshtein distance)


K = (С11 + С12 +… + С1m + C21 + C22 +… + C2m +… + Cnm) / ((n + m) / 2)


Итого для примера, пусть Cij считается как a[i] == b[j] ? 1 : 0


a = ['Иван', 'Иваныч', 'Иванов']

b = ['Иванов', 'Иван', 'Иваныч']


K = (0 + 1 + 0 + 0 + 0 + 1 + 1 + 0 + 0) / ((3 + 3) / 2) = 3 / 3 = 1 — строки одинаковы


a = ['Иван', 'Иваныч']

b = ['Иванов', 'Иваныч']


K = (0 + 0 + 0 + 1) / ((2 + 2) / 2) = 1 / 2 = 0.5 — похожи, но не равны


Вроде логично.


Спасибо hamMElion, что напомнил разбить строки на слова %)