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

редактировать

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

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

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

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

Содержание

1 Определение
- 1.1 Сходство Джаро
- 1.2 Сходство Джаро – Винклера
2 Связь с другими метриками расстояния редактирования
3 См. Также
4 Сноски
5 Ссылки
6 Внешние ссылки

Определение

Сходство Джаро

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

simj = {0, если m = 0 1 3 ( m | s 1 | + m | s 2 | + m - tm) в противном случае {\ 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 {else}} \ end {array}} \ right.}

{\ 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 {else}} \ end {array}} \ right.}

Где:

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

Два символа из $s 1 {\ displaystyle s_ {1}}$ $s_ {1}$ и $s 2 {\ displaystyle s_ {2}}$ $s_ {2}$ соответственно считаются совпадающими, только если они совпадают и не дальше $⌊ макс (| s 1 |, | s 2 |) 2 ⌋ - 1 {\ displaystyle \ left \ lfloor {\ frac {\ max (| s_ {1} |, | s_ {2} |)} {2}} \ right \ rfloor -1}$ $\ left \ lfloor {\ frac {\ max (| s_ {1} |, | s_ {2} |)} {2 }} \ right \ rfloor -1$ символов друг от друга.

Каждый символ $s 1 {\ displaystyle s_ {1}}$ $s_ {1}$ сравнивается со всеми соответствующими ему символами в $s 2 {\ displaystyle s_ {2}}$ $s_ {2}$ . Количество совпадающих (но различающихся порядком следования) символов, деленное на 2, определяет количество транспозиций. Например, при сравнении CRATE с TRACE совпадающими символами являются только 'R' 'A' 'E', т.е. m = 3. Хотя 'C' и 'T' встречаются в обеих строках, они находятся дальше, чем 1 (результат $⌊ 5 2 ⌋ - 1 {\ displaystyle \ lfloor {\ tfrac {5} {2}} \ rfloor - 1}$ ${\ displaystyle \ lfloor {\ tfrac {5} {2}} \ rfloor -1}$ ). Следовательно, t = 0. В DwAyNE по сравнению с DuANE совпадающие буквы уже находятся в том же порядке D-A-N-E, поэтому транспонирование не требуется.

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

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

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

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

где:

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

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

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

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

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

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

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

См. Также

Сноски

Ссылки

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

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

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

strcmp.c - Оригинальная реализация C автором алгоритма