Информатика

Алгоритмы приблизительного сравнения текста, часть 2

Часть 1, Часть 2

Метрика похожести

Другие процедуры, обсуждаемые здесь, используют различные типы метрики текстуального сходства. Их можно использовать в поиске, позволяющем ошибки.

Многие из этих процедур вычисляют сходство двух строк как число между 0 и 1. Величина 0 означает, что строки полностью различны. Величина 1 означает совершенное совпадение строк. Промежуточные значения соответствуют частичному совпадению.

Алгоритмы метрик похожести полезны для проверки орфографии, для опознавания речи, для анализа ДНК, для обнаружения плагиата, для нахождения разницы между файлами и для дистанционного обновления дисплея.

Дистанция Хэмминга

Для двух строк одинаковой длины, дистанция Хэмминга (Hamming distance) - количество мест, в которых строки имеют разные символы.

Примеры

1. Дистанция Хэмминга от ALEXANDRE до ALEKSANDR: 6 (ALE совпадает, остальные 6 символов различны).

Дистанция редактирования

Дистанция редактирования (edit distance) между двумя строками определяется как минимальное число вставок, замен и удалений символов необходых для того, чтобы преобразовать первую строку во вторую. Дистанция 0 означает, что строки идентичны.

Алгоритм был изобретён в 1965 советским научным работником Владимиром Левенштейном. По этой причине Дистанция редактирования называется также Дистанцией Левенштейна.

Имеются современные варианты алгоритма, придавая различные веса вставке, замене и удалению.

Примеры

1. Дистанция редактирования от 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

Примеры

1. Сходство ALEXANDRE и ALEKSANDER: 2*3 / (9+10) = 0.32 (совпадают _AL, ALE, AND).

Распознавание форм Ратклиффа/Обершелпа

Алгоритм Ратклиффа/Обершелпа (Ratcliff/Obershelp pattern recognition) вычисляет сходство двух строк как удвоенное число соответствующих символов разделённое на полное число символов в строках. Соответствующие символы находятся в самой длинной общей подпоследовательности плюс, рекурсивно, соответствующие символы в остальной части по любую сторону от самой длинной общей подпоследовательности.

Примеры

1. Сходство 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. Он также даёт меньший вес некоторым типам ошибок: визуального сканирования, клавишного ввода и в конце строки.

Примеры

1. Сходство 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-грамма	схожесть	орфографические ошибки, редактированный текст
Ратклифф/Обершелп	схожесть	орфографические ошибки, редактированный текст
Джаро-Винклер	схожесть	ошибки орфографические и опечатки

Ресурсы

Смотрите также обширную библиографию Интернета на английском языке.

1. Дистанция Левенштейна в Википедии — свободной энциклопедии.
   http://ru.wikipedia.org/
2. Описание функций обработки строк PHP: levenshtein, soundex, similar_text e metaphone.
   http://www.php.net/manual/ru/ref.strings.php

Алгоритмы приблизительного сравнения текста
Часть 1, Часть 2