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

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

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

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

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

Визначення

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

Подібність Джаро $si{m}_j$ з двох заданих рядків $s_1$ і $s_2$ визначається як

$si{m}_j=\{\begin{array}{cc}0& \text{якщо }m=0,\\ \frac{1}{3}(\frac{m}{|s_1|}+\frac{m}{|s_2|}+\frac{m-t}{m})& \text{в іншому разі}\end{array}$

Тут:

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

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

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

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

Подібність Джаро — Вінклера використовує оцінку префікса $p$ що дає більш сприятливі оцінки рядкам, які з самого початку відповідають заданій довжині префікса $\ell$. Дано два рядки $s_1$ і $s_2$. Їхня подібність Джаро-Вінклера $si{m}_w$ визначається як:

$si{m}_w=si{m}_j+\ell p(1-si{m}_j),$

де:

• $si{m}_j$ — подібність Джаро для рядків $s_1$ і $s_2$
• $\ell$ — довжина загального префіксу на початку рядка — максимум до 4 символів
• $p$ є сталим коефіцієнтом масштабування того, наскільки оцінка коригується вгору за наявність загальних префіксів. $p$ не повинен перевищувати 0,25 (тобто 1/4, причому 4 - це максимальна довжина префікса, що розглядається), інакше подібність може стати більшою за 1. Стандартним значенням цієї константи у роботі Вінклера є $p=0.1$.

Відстань Джаро — Вінклера $d_w$ визначається як $d_w=1-si{m}_w$.

Хоча її часто називають метрикою, відстань Джаро — Вінклера не є метрикою в математичному розумінні, оскільки вона не підпорядковується нерівності трикутника. Відстань Джаро — Вінклера також не відповідає аксіомі ідентичності $d(x,y)=0\leftrightarrow x=y$ .

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

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

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

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

Див. також

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

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

• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal

• Шаблон:Cite journal

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

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