Расстояние Яро – Винклера - Jaro–Winkler distance

В Информатика и статистика, то Расстояние Яро – Винклера это строковая метрика измерение редактировать расстояние между двумя последовательностями. Это вариант, предложенный в 1990 г. Уильям Э. Винклер из Расстояние Джаро метрическая (1989, Мэтью А. Джаро ).

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

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

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

Определение

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

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

${displaystyle sim_ {j} = left {{egin {array} {ll} 0 & {ext {if}} m = 0 {frac {1} {3}} left ({frac {m} {| s_ {1}) |}} + {frac {m} {| s_ {2} |}} + {frac {mt} {m}} ight) & {ext {else}} end {array}} ight.}$

Где:

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

Два персонажа из ${displaystyle s_ {1}}$ и ${displaystyle s_ {2}}$ соответственно считаются соответствие только если они такие же и не дальше чем ${displaystyle leftlfloor {frac {max (| s_ {1} |, | s_ {2} |)} {2}} ightfloor -1}$ символы отдельно.

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

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

Сходство Яро – Винклера использует префикс шкала ${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}$ это постоянная коэффициент масштабирования на сколько счет повышается для наличия общих префиксов. ${displaystyle p}$ не должно превышать 0,25 (т.е. 1/4, где 4 - максимальная длина рассматриваемого префикса), в противном случае сходство может стать больше 1. Стандартное значение этой константы в работе Винклера равно ${displaystyle p = 0,1}$

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

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

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

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

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

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

Смотрите также

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

Сноски

Рекомендации

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

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

внешняя ссылка

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