Информатика
Алгоритмы приблизительного сравнения текста, часть 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 и так далее.
Сравнение алгоритмов
Выбор одного из алгоритмов приблизительного сравнения строк главным образом зависит от природы ошибок, влияющих на текст.
Алгоритм | Тип | Когда использовать |
---|---|---|
Саундэкс | фонетический | английские слова с орфографическими ошибками |
Дэйч-Мокотофф | фонетический | европейские фамилии написанные по-разному |
NYSIIS | фонетический | английские и некоторые иностранные слова с орфографическими ошибками |
Метафон, Двойной метафон | фонетический | английские слова с орфографическими ошибками |
Каверфон 2.0 | фонетический | английские слова с орфографическими ошибками |
Хэмминг, Левенштейн | схожесть | локальные орфографические ошибки |
Триграмма, n-грамма | схожесть | орфографические ошибки, редактированный текст |
Ратклифф/Обершелп | схожесть | орфографические ошибки, редактированный текст |
Джаро-Винклер | схожесть | ошибки орфографические и опечатки |
Ресурсы
Смотрите также обширную библиографию Интернета на английском языке.
- Дистанция Левенштейна в Википедии — свободной энциклопедии.
http://ru.wikipedia.org/ - Описание функций обработки строк PHP: levenshtein, soundex, similar_text e metaphone.
http://www.php.net/manual/ru/ref.strings.php
Алгоритмы приблизительного сравнения текста
Часть 1, Часть 2