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

Эта статья о мере. Чтобы узнать о других значениях, см. Jaro .

В информатике и статистике сходство Джаро -Винклера представляет собой строковую метрику, измеряющую расстояние редактирования между двумя последовательностями. Это вариант метрики расстояния Джаро. (1989, Мэтью А. Джаро ) Предложено в 1990 году Уильямом Э. Винклером .

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

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

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

Определение

Сходство года

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

$sim_{j}=\left\{{\begin{array}{l l}0&{\text{if }}m=0\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {m-t}{m}}\right)&{\text{otherwise}}\end{array}}\right.$

Где:

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

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

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

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

Сходство Яро-Винклера

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

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

где:

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

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

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

Связь с другими метриками расстояния редактирования

Основная статья: Изменение расстояния

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

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

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

См. также

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

Ссылки

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

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

Внешние ссылки

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