Сходство Джаро — Винклера

В области информатики и статистики сходство Джаро — Винклера представляет собой меру схожести строк для измерения расстояния между двумя последовательностями символов. Это вариант, который в 1999 году предложил Уильям Э. Винклер (William E. Winkler) на основе расстояния Джаро (1989, Мэтью А. Джаро, Matthew A. Jaro). Неформально, расстояние Джаро между двумя словами — это минимальное число односимвольных преобразований, которое необходимо для того, чтобы изменить одно слово в другое.

Чем меньше расстояние Джаро — Винклера для двух строк, тем больше сходства имеют эти строки друг с другом. Результат нормируется, так что означает отсутствие сходства, а  — точное совпадение. Сходство Джаро — Винклера равно .

Определение

Расстояние Джаро

Расстояние Джаро между двумя заданными строками и это:

Где:

  •  — длина строки ;
  •  — число совпадающих символов (см. ниже);
  •  — половина числа транспозиций (см. ниже).

Два символа из и соответственно, считаются совпадающими только если они одинаковы и не дальше, чем .

Каждый символ строки сравнивается со всеми соответствующими ему символами в . Количество совпадающих (но отличающихся порядковыми номерами) символов, которое делится на 2, определяет число транспозиций. Например, при сравнении слова CRATE со словом TRACE, только 'R' 'A' и 'Е' являются совпадающими символами, то есть m=3. Хотя 'C' и 'T' появляются в обоих строках, они дальше, чем на 1, то есть floor(5/2)-1=1. Следовательно, t=0 . В сравнении DwAyNE с DuANE соответствующие буквы находятся уже в том же самом порядке D-A-N-E, так что никаких перестановок не требуется.

Расстояние Джаро — Винклера

Расстояние Джаро — Винклера использует коэффициент масштабирования , что дает более благоприятные рейтинги строкам, которые совпадают друг с другом от начала до определённой длины , которая называется префиксом. Даны две строки и . Их расстояние Джаро — Винклера это:

где:

  •  — расстояние Джаро для строк и
  •  — длина общего префикса от начала строки до максимума 4-х символов
  •  — постоянный коэффициент масштабирования, использующийся для того, чтобы скорректировать оценку в сторону повышения для выявления наличия общих префиксов. не должен превышать 0,25, поскольку в противном случае расстояние может стать больше, чем 1. Стандартное значение этой константы в работе Винклера: .

Хотя расстояние Джаро-Винклера часто называют метрикой расстояния, это не метрика в математическом смысле этого слова, потому что оно не подчиняется неравенству треугольника . Также расстояние Джаро-Винклера не удовлетворяет аксиоме, которая гласит, что [1].

В некоторых реализациях алгоритма расчёта расстояния Джаро — Винклера префиксный бонус добавляется, только если сравниваемые строки имеют расстояние Джаро выше установленного «порога усиления» . Порог в реализации Винклера составил 0,7.

Примеры

Следует отметить, что написанный Винклером программный код на языке программирования C различается по крайней мере в двух местах от опубликованных работ по метрике Джаро — Винклера. Первое — это его использование таблицы опечаток (adjwt), а второе — это некоторые дополнительные условия для длинных строк.

Пример 1

Даны строки MARTHA и MARHTA. Представим их пересечение в табличном виде:

M A R T H A
M 1 0 0 0 0 0
A 0 1 0 0 0 0
R 0 0 1 0 0 0
H 0 0 0 0 1 0
T 0 0 0 1 0 0
A 0 0 0 0 0 1

Здесь максимальное расстояние составляет 6/2 — 1 = 2. В желтых ячейках приведенной таблицы указаны единицы, когда символы идентичны (имеется совпадение), и нули в противном случае.

Получается:

  • Есть несовпадающие символы T/H и Н/Т, в результате:

Расстояние Джаро:

Чтобы найти результат Джаро — Винклера с помощью стандартного веса мы продолжаем искать:

Таким образом:

Пример 2

Даны строки DWAYNE и DUANE. Получается:

Расстояние Джаро:

Чтобы найти результат Джаро-Винклера с помощью стандартного веса мы продолжаем искать:

Таким образом:

Пример 3

Даны строки DIXON и DICKSONX. Получается:

D I X O N
D 1 0 0 0 0
I 0 1 0 0 0
C 0 0 0 0 0
K 0 0 0 0 0
S 0 0 0 0 0
O 0 0 0 1 0
N 0 0 0 0 1
X 0 0 0 0 0

Здесь закрашенные клетки — это окно соответствия для каждого символа. Единицы в ячейке указывает на совпадение. Заметим, что два икса (X) не считаются совпавшими, поскольку они находятся за пределами третьего окна совпадения.

Расстояние Джаро:

Чтобы найти результат Джаро-Винклера с помощью стандартного веса мы продолжаем искать:

Таким образом:

Отношения с другими метриками изменения расстояния

Есть и другие популярные меры изменения расстояния, которые рассчитываются с использованием другого набора допустимых операций редактирования. Например,

Изменение расстояния обычно определяется как параметризуемая метрика, вычисленная с помощью определённого набора допустимых операций редактирования, и каждой операции присваивается стоимость (возможно, бесконечная). Это является дальнейшим обобщением генетических алгоритмов выравнивания последовательностей, таких, как алгоритм Смита-Ватермана, которые делают стоимость операции зависящей от того, где она применяется.

Практическое применение

  • Алгоритм Джаро-Винклера использовался для обработки результатов переписи населения[2].
  • Алгоритм сравнения строк Джаро — Винклера реализован в СУБД Oracle[3].

Реализации алгоритма на различных языках программирования

Примечания

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.