Подібність Джаро — Вінклера

В інформатиці та статистиці подібність Джаро — Вінклера — це рядкова метрика, що вимірює відстань редагування між двома послідовностями. Є модифікацією метрики подібності Джаро (1989, Метью А. Джаро), запропонованою у 1990 році Вільямом Е. Вінклером.

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

Чим менша відстань Джаро–Вінклера для двох рядків, тим більш подібними є рядки. Оцінка нормується таким чином, що 1 означає точну відповідність, а 0 означає відсутність будь-якої подібності. Подібність Джаро — Вінклера дає протилежні результати.

Хоча її часто називають метрикою відстані, відстань Яро–Вінклера не є метрикою в математичному розумінні, оскільки вона не виконує нерівність трикутника.

Визначення

Подібність Джаро

Подібність Джаро ${\displaystyle sim_{j}}$ з двох заданих рядків ${\displaystyle s_{1}}$ і ${\displaystyle s_{2}}$ визначається як

${\displaystyle sim_{j}=\left\{{\begin{array}{l l}0&{\text{якщо }}m=0,\\{\frac {1}{3}}\left({\frac {m}{|s_{1}|}}+{\frac {m}{|s_{2}|}}+{\frac {m-t}{m}}\right)&{\text{в іншому разі}}\end{array}}\right.}$

Тут:

• ${\displaystyle |s_{i}|}$ - довжина рядка ${\displaystyle s_{i}}$;
• ${\displaystyle m}$ - кількість співпадінь (див. нижче);
• ${\displaystyle t}$ - кількість транспозицій (див. нижче).

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

Кожен символ ${\displaystyle s_{1}}$ порівнюється з усіма відповідними символами в ${\displaystyle s_{2}}$. Кількість відповідних (але в різному порядку) символів, розділених на 2, визначає кількість транспозицій. Наприклад, при порівнянні «CRATE» з «TRACE» лише символи «R», «A», «E» є співпадіннями, тобто ${\displaystyle m=3}$ Незважаючи на те, що «C» та «T» з'являються в обох рядках, вони розташовані далі один від одного, ніж 1 (результат ${\displaystyle \lfloor {\tfrac {5}{2}}\rfloor -1}$ ). Отже, ${\displaystyle t=0}$. Якщо порівнювати «DwAyNE» та «DuANE», то тут співпадіння уже розташовані в тому самому порядку, тож транспозиції відсутні.

Подібність Джаро — Вінклера

Подібність Джаро — Вінклера використовує оцінку префікса ${\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)=0\leftrightarrow x=y}$ .

Взаємозв'язок з іншими метриками відстані редагування

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

• відстань Левенштейна дозволяє видалення, вставлення та заміну;
• відстань Дамерау — Левенштейна дозволяє всталення, видалення, заміну та транспонування двох сусідніх символів;
• найдовша загальна відстань підпослідовності (LCS) дозволяє лише вставлення та видалення, але не заміну;
• відстань Геммінга допускає лише заміну, отже, вона використовується лише для рядків однакової довжини.

Відстань редагування зазвичай визначається як параметризована метрика, обчислена з певним набором дозволених операцій редагування, і кожній операції присвоюється вартість (можливо, нескінченна). Це додатково узагальнюється алгоритмами вирівнювання послідовностей ДНК, такими як алгоритм Сміта — Вотермана, які роблять вартість операції залежною від того, де вона застосовується.

Див. також

• Зв'язані записи
• Перепис населення

Виноски

 

1. Jaro-Winkler « Inviting Epiphany. RichardMinerich.com. Архів оригіналу за 31 грудня 2019. Процитовано 12 червня 2017.

Список літератури

• Cohen, W. W.; Ravikumar, P.; Fienberg, S. E. (2003). A comparison of string distance metrics for name-matching tasks (PDF). KDD Workshop on Data Cleaning and Object Consolidation. 3: 73—8. Архів оригіналу (PDF) за 6 травня 2021. Процитовано 16 квітня 2021.
• Jaro, M. A. (1989). Advances in record linkage methodology as applied to the 1985 census of Tampa Florida. Journal of the American Statistical Association. 84 (406): 414—20. doi:10.1080/01621459.1989.10478785.
• Jaro, M. A. (1995). Probabilistic linkage of large public health data file. Statistics in Medicine. 14 (5–7): 491—8. doi:10.1002/sim.4780140510. PMID 7792443.
• Winkler, W. E. (1990). String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage (PDF). Proceedings of the Section on Survey Research Methods. American Statistical Association: 354—359. Архів оригіналу (PDF) за 16 квітня 2021. Процитовано 16 квітня 2021.

• Winkler, W. E. (2006). Overview of Record Linkage and Current Research Directions (PDF). Research Report Series, RRS. Архів оригіналу (PDF) за 6 травня 2021. Процитовано 16 квітня 2021.

Зовнішні посилання

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