Насколько похожи две строки? В PHP для выяснения подобия строк есть две функции — similar_text() и levenshtein().
Первая из них считает процент совпадения символов в двух строках, а вторая вычисляет расстояние Левенштейна — кол-во операций вставки, замены, удаления символов, приводящих одну строку к другой.
Время работы функции levenshtein очень быстро растет с ростом длины сравниваемых строк (как n³). Также установлена максимальная длина для строк — 255 символов. После вычисления требуется нормировка, чтобы можно было использовать результат вычислений для сравнения с другими результатами. А если вы переставите аргументы местами, то получите отличный от предыдущего результат.
Все эти факторы склоняют меня в сторону выбора функции similar_text. Она устроена более сложно, чем я упоминал ранее.
Пример работы:
|
1 2 3 4 5 |
$s1 = 'ac'; $s2 = 'ac'; similar_text($s1, $s2, $per); echo $per; //выводит 100, т.е. 100% совпадение |
А вот результаты сравнения других строк:
ac и ca — 50%;
AC и ac — 0%
aac и ac — 80%
abc и ac — 80%
caa и ac — 40%
cba и ac — 40%
vb ac и ac vb — 40%
vb ac и vc ab — 60%
Как видите, не так уж она прямолинейна и предсказуема. Для функции важен порядок слов и регистр букв. По умолчанию, она не работает с кириллицей и UTF8.
Давайте избавим функцию от этих недостатков.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
setlocale(LC_ALL, "UTF-8"); //сравнение строк function strSimilar($str1, $str2) { similar_text(strNormalize($str1), strNormalize($str2), $per); return $per; } //нормализация текста function strNormalize($str) { $n = str_word_count(mb_strtolower($str), 1, '1234567890абвгдеёжзийклмнопрстуфхцчшщъыьэюя'); sort($n, SORT_LOCALE_STRING ); return implode(' ', $n); } |
Получившаяся функция strSimilar пренебрегает регистром букв, порядком слов и работает с UTF-8. Для этого требуется предварительная нормализация строк.
Алгоритм очень медленный и едва ли применим для реальных задач, где требуется выявить подобие строк.