Алгоритмы приблизительного сравнения текста, часть 2
Часть 1, Часть 2
Метрика похожести
Другие процедуры, обсуждаемые здесь, используют различные типы
метрики текстуального сходства.
Их можно использовать в поиске, позволяющем ошибки.
Многие из этих процедур вычисляют сходство двух строк как число между 0 и 1.
Величина 0 означает, что строки полностью различны.
Величина 1 означает совершенное совпадение строк.
Промежуточные значения соответствуют частичному совпадению.
Алгоритмы метрик похожести полезны для проверки орфографии,
для опознавания речи, для анализа ДНК, для обнаружения плагиата,
для нахождения разницы между файлами и для дистанционного обновления дисплея.
Дистанция Хэмминга
Для двух строк одинаковой длины, дистанция Хэмминга
(Hamming distance)
- количество мест, в которых строки имеют разные символы.
Примеры
- Дистанция Хэмминга от ALEXANDRE до ALEKSANDR: 6
(ALE совпадает, остальные 6 символов различны).
Дистанция редактирования
Дистанция редактирования (edit distance)
между двумя строками определяется как минимальное число вставок, замен и удалений
символов необходых для того, чтобы преобразовать первую строку во вторую.
Дистанция 0 означает, что строки идентичны.
Алгоритм был изобретён в 1965 советским научным работником Владимиром Левенштейном.
По этой причине Дистанция редактирования называется также Дистанцией Левенштейна.
Имеются современные варианты алгоритма, придавая различные веса
вставке, замене и удалению.
Примеры
- Дистанция редактирования от ALEXANDRE до ALEKSANDER: 4
(замена X на K, введение S после K, введение E после D, удаление E в конце).
Триграмма
Триграммное сходство (trigram similarity)
между двумя строками определяется числом совпадающих символьных триплетов в обоих строках.
Алгоритм можно обобщить на n-граммы, где n=1, 2, ...
Строки string1 и string2 пополняются слева и справа одним символом пробела.
Затем строки разделяются на триплеты (триграммы).
Окончательно, сходство вычисляется по формуле:
s = 2*m / (a + b).
Здесь:
m - число совпадающих триграмм
a - число триграмм в string1
b - число триграмм в string2
Примеры
- Сходство ALEXANDRE и ALEKSANDER: 2*3 / (9+10) = 0.32
(совпадают _AL, ALE, AND).
Распознавание форм Ратклиффа/Обершелпа
Алгоритм Ратклиффа/Обершелпа
(Ratcliff/Obershelp pattern recognition)
вычисляет сходство двух строк как удвоенное число соответствующих символов
разделённое на полное число символов в строках.
Соответствующие символы находятся в самой длинной общей подпоследовательности плюс,
рекурсивно, соответствующие символы в остальной части
по любую сторону от самой длинной общей подпоследовательности.
Примеры
- Сходство ALEXANDRE и ALEKSANDER: 2 * (3+3+1+1) / (9+10) = 0.84
(соответствуют ALE, AND, E, R).
Джаро-Винклер
Сходство Джаро-Винклера (Jaro-Winkler similarity)
было применено в переписи США и использовано в последующей обработке.
Для данных строк string1 и string2, их сходство задаётся формулой:
s = m/3a + m/3b + (m-t)/3m.
Здесь:
m - число соответствующих символов
a - длина string1
b - длина string2
t - число перестановок
Два символа считаются соответствующими, только
если они находятся не дальше чем (max(a,b)/2 - 1).
Первый соответствующий символ в string1
сравнивается с первым соответствующим символом в string2;
второй соответствующий символ в string1
сравнивается со вторым соответствующим символом в string2, и так далее.
Число соответствующих символов делённое на 2 даёт число перестановок.
Улучшенный метод Джаро-Винклера использует веса отличные от 1/3.
Он также даёт меньший вес некоторым типам ошибок: визуального сканирования,
клавишного ввода и в конце строки.
Примеры
- Сходство ALEXANDRE и ALEKSANDER: (8/9 + 8/10 + (8-1)/8) / 3 = 0.85
(соответствуют A, L, E, A, N, D, R, E; 1 перестановка).
Опечатки
Имеются некоторые алгоритмы, учитывающие ошибки ввода на клавиатуре:
V вместо B, 6 вместо Y и так далее.
Сравнение алгоритмов
Выбор одного из алгоритмов приблизительного сравнения строк
главным образом зависит от природы ошибок, влияющих на текст.
Ресурсы
Смотрите также обширную библиографию Интернета
на английском языке.
- Дистанция Левенштейна в Википедии — свободной энциклопедии.
http://ru.wikipedia.org/
- Описание функций обработки строк PHP: levenshtein, soundex, similar_text e metaphone.
http://www.php.net/manual/ru/ref.strings.php
Алгоритмы приблизительного сравнения текста Часть 1, Часть 2
|