В інформатиці та статистиці подібність Джаро — Вінклера — це рядкова метрика, що вимірює відстань редагування між двома послідовностями. Є модифікацією метрики подібності Джаро (1989, Метью А. Джаро), запропонованою у 1990 році Вільямом Е. Вінклером.
Відстань Джаро–Вінклера використовує оцінку довжини префікса , що дає більш сприятливі оцінки рядкам, що з самого початку відповідають заданій довжині префікса .
Чим менша відстань Джаро–Вінклера для двох рядків, тим більш подібними є рядки. Оцінка нормується таким чином, що 1 означає точну відповідність, а 0 означає відсутність будь-якої подібності. Подібність Джаро — Вінклера дає протилежні результати.
Хоча її часто називають метрикою відстані, відстань Яро–Вінклера не є метрикою в математичному розумінні, оскільки вона не виконує нерівність трикутника.
Визначення
Подібність Джаро Подібність Джаро з двох заданих рядків і визначається як
Тут:
- довжина рядка ; - кількість співпадінь (див. нижче); - кількість транспозицій (див. нижче).
Два символи від і відповідно, вважаються співпадінням лише в тому випадку, якщо вони однакові і розташовані не далі, ніж один від одного.
Кожен символ порівнюється з усіма відповідними символами в . Кількість відповідних (але в різному порядку) символів, розділених на 2, визначає кількість транспозицій. Наприклад, при порівнянні «CRATE» з «TRACE» лише символи «R», «A», «E» є співпадіннями, тобто Незважаючи на те, що «C» та «T» з'являються в обох рядках, вони розташовані далі один від одного, ніж 1 (результат ). Отже, . Якщо порівнювати «DwAyNE» та «DuANE», то тут співпадіння уже розташовані в тому самому порядку, тож транспозиції відсутні.
Подібність Джаро — Вінклера Подібність Джаро — Вінклера використовує оцінку префікса що дає більш сприятливі оцінки рядкам, які з самого початку відповідають заданій довжині префікса . Дано два рядки і . Їхня подібність Джаро-Вінклера визначається як:
де:
— подібність Джаро для рядків і — довжина загального префіксу на початку рядка — максимум до 4 символів є сталим коефіцієнтом масштабування того, наскільки оцінка коригується вгору за наявність загальних префіксів. не повинен перевищувати 0,25 (тобто 1/4, причому 4 - це максимальна довжина префікса, що розглядається), інакше подібність може стати більшою за 1. Стандартним значенням цієї константи у роботі Вінклера є .
Відстань Джаро — Вінклера визначається як .
Хоча її часто називають метрикою, відстань Джаро — Вінклера не є метрикою в математичному розумінні, оскільки вона не підпорядковується нерівності трикутника. Відстань Джаро — Вінклера також не відповідає аксіомі ідентичності .
Взаємозв'язок з іншими метриками відстані редагування Є й інші популярні міри відстані редагування, які обчислюються з використанням іншого набору допустимих операцій редагування. Наприклад,
відстань Левенштейна дозволяє видалення, вставлення та заміну; відстань Дамерау — Левенштейна дозволяє всталення, видалення, заміну та транспонування двох сусідніх символів; найдовша загальна відстань підпослідовності (LCS) дозволяє лише вставлення та видалення, але не заміну; відстань Геммінга допускає лише заміну, отже, вона використовується лише для рядків однакової довжини.
Відстань редагування зазвичай визначається як параметризована метрика, обчислена з певним набором дозволених операцій редагування, і кожній операції присвоюється вартість (можливо, нескінченна). Це додатково узагальнюється алгоритмами вирівнювання послідовностей ДНК, такими як алгоритм Сміта — Вотермана, які роблять вартість операції залежною від того, де вона застосовується.
Див. також
Зв'язані записи Перепис населення
Виноски
Список літератури
Зовнішні посилання
strcmp.c - оригінальна реалізація на C автором алгоритму