Расстояние Яро–Винклера

В информатике и статистике сходство Джаро –Винклера — это строковая метрика, измеряющая расстояние редактирования между двумя последовательностями. Это вариант метрики расстояния Джаро ^[1] (1989, Мэтью А. Джаро), предложенной в 1990 году Уильямом Э. Винклером . ^[2]

Расстояние Яро–Винклера использует шкалу префиксов , которая дает более благоприятные оценки строкам, которые совпадают с самого начала для заданной длины префикса .${\displaystyle p}$${\displaystyle \ell }$

Чем выше расстояние Яро–Винклера для двух строк, тем менее похожи строки. Оценка нормализована таким образом, что 0 означает точное совпадение, а 1 означает, что сходства нет. Оригинальная статья фактически определила метрику в терминах сходства, поэтому расстояние определяется как инверсия этого значения (расстояние = 1 − сходство).

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

Сходство Джаро двух данных строк и равно${\displaystyle sim_{j}}$${\displaystyle s_{1}}$${\displaystyle s_{2}}$

${\displaystyle sim_{j}=\left\{{\begin{array}{ll}0&{\text{if}}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {mt}{m}}\right)&{\text{inotherwise}}\end{array}}\right.}$

Где:

• ${\displaystyle |s_{i}|}$длина строки ;${\displaystyle s_{i}}$
• ${\displaystyle м}$количество совпадающих символов (см. ниже);
• ${\displaystyle т}$— число транспозиций (см. ниже).

Показатель сходства Jaro равен 0, если строки вообще не совпадают, и 1, если они точно совпадают. На первом этапе каждый символ из сравнивается со всеми соответствующими ему символами в . Два символа из и соответственно считаются совпадающими , только если они одинаковы и не дальше символов друг от друга. Например, следующие две строки длиной в девять символов, FAREMVIEL и FARMVILLE, имеют 8 совпадающих символов. «F», «A» и «R» находятся в одной и той же позиции в обеих строках. Также «M», «V», «I», «E» и «L» находятся в пределах трех (результат ) символов друг от друга. ^[3] Если совпадающих символов не найдено, то строки не похожи, и алгоритм завершается, возвращая показатель сходства Jaro 0.${\displaystyle s_{1}}$${\displaystyle s_{2}}$${\displaystyle s_{1}}$${\displaystyle s_{2}}$${\displaystyle \left\lfloor {\frac {\max(|s_{1}|,|s_{2}|)}{2}}\right\rfloor -1}$${\displaystyle \lfloor {\tfrac {\max(9,9)}{2}}\rfloor -1}$

Если найдены ненулевые совпадающие символы, следующим шагом будет поиск количества транспозиций. Транспозиция — это количество совпадающих символов, которые не находятся в правильном порядке, деленное на два. В приведенном выше примере между FAREMVIEL и FARMVILLE, 'E' и 'L' — это совпадающие символы, которые не находятся в правильном порядке. Таким образом, количество транспозиций равно одному.

Наконец, подставив число совпадающих символов и число транспозиций, можно рассчитать сходство Джаро между FAREMVIEL и FARMVILLE,${\displaystyle м}$${\displaystyle т}$${\displaystyle {\frac {1}{3}}\left({\frac {8}{9}}+{\frac {8}{9}}+{\frac {8-1}{8}}\right)=0,88}$

Сходство Джаро–Винклера использует шкалу префиксов , которая дает более благоприятные оценки строкам, которые совпадают с самого начала для заданной длины префикса . Для двух строк и их сходство Джаро–Винклера равно:${\displaystyle p}$${\displaystyle \ell }$${\displaystyle s_{1}}$${\displaystyle s_{2}}$${\displaystyle sim_{w}}$

${\displaystyle sim_{w}=sim_{j}+\ell p(1-sim_{j}),}$

где:

• ${\displaystyle sim_{j}}$есть подобие Джаро для струн и${\displaystyle s_{1}}$${\displaystyle s_{2}}$
• ${\displaystyle \ell }$длина общего префикса в начале строки, максимум до 4 символов
• ${\displaystyle p}$— постоянный коэффициент масштабирования, указывающий, насколько оценка корректируется в сторону увеличения из-за наличия общих префиксов. не должно превышать 0,25 (т.е. 1/4, где 4 — максимальная длина рассматриваемого префикса), в противном случае сходство может стать больше 1. Стандартное значение этой константы в работе Винклера равно${\displaystyle p}$${\displaystyle р=0,1}$

Расстояние Яро–Винклера определяется как .${\displaystyle d_{w}}$${\displaystyle d_{w}=1-sim_{w}}$

Хотя расстояние Яро–Винклера часто называют метрикой расстояния , оно не является метрикой в ​​математическом смысле этого термина, поскольку не подчиняется неравенству треугольника . ^[4] Расстояние Яро–Винклера также не удовлетворяет аксиоме тождества .${\displaystyle d(x,y)=0\leftrightarrow x=y}$

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

• расстояние Левенштейна допускает удаление, вставку и замену;
• расстояние Дамерау –Левенштейна допускает вставку, удаление, замену и перестановку двух соседних символов;
• расстояние наибольшей общей подпоследовательности (LCS) допускает только вставку и удаление, но не замену;
• Расстояние Хэмминга допускает только замену, поэтому оно применимо только к строкам одинаковой длины.

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

• Запись связи
• Перепись

• Cohen, WW; Ravikumar, P.; Fienberg, SE (2003). "Сравнение метрик расстояния строк для задач сопоставления имен" (PDF) . Семинар KDD по очистке данных и консолидации объектов . 3 : 73– 8.
• Jaro, MA (1989). «Достижения в методологии связывания записей применительно к переписи населения 1985 года в Тампе, Флорида». Журнал Американской статистической ассоциации . 84 (406): 414– 20. doi :10.1080/01621459.1989.10478785.
• Jaro, MA (1995). «Вероятностная связь большого файла данных общественного здравоохранения». Статистика в медицине . 14 ( 5– 7): 491– 8. doi : 10.1002/sim.4780140510. PMID  7792443.
• Winkler, WE (1990). «Метрики компаратора строк и улучшенные правила принятия решений в модели Феллеги-Сантера для связывания записей» (PDF) . Труды секции по методам исследования опросов . Американская статистическая ассоциация: 354–359 .

• Винклер, У. Э. (2006). «Обзор связей записей и текущие направления исследований» (PDF) . Серия исследовательских отчетов, RRS .

• strcmp.c — Оригинальная реализация на языке C от автора алгоритма
• Модуль nltk.metrics.distance — реализация Python в Natural Language Toolkit