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

Question

[Xp0M0u]

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


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

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

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


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

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, что напомнил разбить строки на слова %)

Answer 1

[dmitryim]

Дополнительно, после разбиения строки на слова, их можно сравнивать с помощью levinshtein(). Потом с учетом длины слова получать коэффициент похожести. Таким образом можно с довольно точно определять схожесть, даже если допущена опечатка в слове, или если оно написано немного иначе.
Ну и дополнительный бонус — транслитерация строки и очистка ее от мусора.

Answer 2

[hamMElion]

1. Разбить обе строки на массивы слов (split)
2. Цикл поиска элементов одного массива в другом (подсчет совпадений = k)
3. Нахождение числа совпадений для второго массива из пропорции k1/n1=k2/n2 (n — число элементов массива)
4. Разница |k1-k2| и есть коэффициент похожести

Answer 3

[tyomitch]

Алгоритмов — хоть антилопой жуй.
На staffwww.dcs.shef.ac.uk/people/S.Chapman/stringmetrics.html есть описания и ссылки на реализации. Выбери подходящий.

Comments

[Xp0M0u]

Я на вики искал, все что находил было на стравнение слов, а не строк. Как то я не подумал чтоб разбить строки на слова. За ссылку спасибо.

Answer 4

[Дмитрий Гроза]

по вашему алгоритму получается, что строки «Джей Джей Йохансон» и «Джей Кью Йохансон» равны. нужно исключать из массивов строк уже совпавшие

Answer 5

[xmoonlight]

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

Answer 6

[RuWeb]

Вот уже готовый онлайн сервис TextTools.ru