Перейти к содержанию

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

Материал из Википедии — свободной энциклопедии

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

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

Определение

[править | править код]

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

[править | править код]

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

dj={0когда m=013(m|s1|+m|s2|+m−tm)в остальных случаях

Где:

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

Два символа из s1 и s2 соответственно, считаются совпадающими только если они одинаковы и не дальше, чем ⌊max⁡(|s1|,|s2|)2⌋−1.

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

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

[править | править код]

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

dw=dj+(ℓp(1−dj))

где:

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

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

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

dw={djесли dj<btdj+(ℓp(1−dj))в остальных случаях

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

Даны строки s1 MARTHA и s2 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. В желтых ячейках приведенной таблицы указаны единицы, когда символы идентичны (имеется совпадение), и нули в противном случае.

Получается:

  • m=6
  • |s1|=6
  • |s2|=6
  • Есть несовпадающие символы T/H и Н/Т, в результате: t=22=1

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

dj=13(66+66+6−16)=0.9(4)

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

ℓ=3

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

dw=0.9(4)+(3⋅0.1(1−0.9(4)))=0.96(1)

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

  • m=4
  • |s1|=6
  • |s2|=5
  • t=22=1

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

dj=13(46+45+4−14)=0.73(8)

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

ℓ=1

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

dw=0.73(8)+(1⋅0.1(1−0.73(8)))=0.765

Даны строки s1 DIXON и s2 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) не считаются совпавшими, поскольку они находятся за пределами третьего окна совпадения.

  • m=4
  • |s1|=5
  • |s2|=8
  • t=22=1

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

dj=13(45+48+4−14)=0.68(3)

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

ℓ=2

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

dw=0.68(3)+(2⋅0.1(1−0.68(3)))=0.74(6)

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

[править | править код]

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

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

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

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

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

[править | править код]

Примечания

[править | править код]
  1. ↑ Record Linkage Algorithms in F# — Extensions to Jaro-Winkler Distance (Part 3). Дата обращения: 21 марта 2017. Архивировано 31 декабря 2019 года.
  2. ↑ Алгоритмы приблизительного сравнения текста, часть 2. Дата обращения: 21 марта 2017. Архивировано 22 марта 2017 года.
  3. ↑ Database PL/SQL Packages and Types Reference. Дата обращения: 21 марта 2017. Архивировано 12 января 2017 года.
  4. ↑ Архивированная копия. Дата обращения: 23 февраля 2011. Архивировано из оригинала 23 февраля 2011 года.
  5. ↑ Distance de jaro-winkler Архивная копия от 22 марта 2017 на Wayback Machine (фр.)
  6. ↑  (англ.)