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

Эта статья про меру. Для использования в других целях см. Jaro.

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

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

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

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

Определение

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

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

${displaystyle sim_{j}=left{{egin{array}{l l}0&{ ext{if }}m=0{frac {1}{3}}left({frac {m}{|s_{1}|}}+{frac {m}{|s_{2}|}}+{frac {m-t}{m}}ight)&{ ext{otherwise}}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) расстояние позволяет только вставку и удаление, но не замену;
• то Расстояние Хэмминга позволяет только подстановку, следовательно, применяется только к строкам одинаковой длины.

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

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

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

Сноски

1. «Яро-Винклер« Приглашающее Крещение ». RichardMinerich.com. Получено 12 июн 2017.

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

• 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 автора алгоритма