В інформатиці та статистиці подібність Джаро — Вінклера — це , що вимірює між двома послідовностями. Є модифікацією метрики подібності Джаро (1989, ), запропонованою у 1990 році .
Відстань Джаро–Вінклера використовує оцінку довжини префікса , що дає більш сприятливі оцінки рядкам, що з самого початку відповідають заданій довжині префікса .
Чим менша відстань Джаро–Вінклера для двох рядків, тим більш подібними є рядки. Оцінка нормується таким чином, що 1 означає точну відповідність, а 0 означає відсутність будь-якої подібності. Подібність Джаро — Вінклера дає протилежні результати.
Хоча її часто називають метрикою відстані, відстань Яро–Вінклера не є метрикою в математичному розумінні, оскільки вона не виконує нерівність трикутника.
Визначення
Подібність Джаро
Подібність Джаро з двох заданих рядків і визначається як
Тут:
- - довжина рядка ;
- - кількість співпадінь (див. нижче);
- - кількість транспозицій (див. нижче).
Два символи від і відповідно, вважаються співпадінням лише в тому випадку, якщо вони однакові і розташовані не далі, ніж один від одного.
Кожен символ порівнюється з усіма відповідними символами в . Кількість відповідних (але в різному порядку) символів, розділених на 2, визначає кількість транспозицій. Наприклад, при порівнянні «CRATE» з «TRACE» лише символи «R», «A», «E» є співпадіннями, тобто Незважаючи на те, що «C» та «T» з'являються в обох рядках, вони розташовані далі один від одного, ніж 1 (результат ). Отже, . Якщо порівнювати «DwAyNE» та «DuANE», то тут співпадіння уже розташовані в тому самому порядку, тож транспозиції відсутні.
Подібність Джаро — Вінклера
Подібність Джаро — Вінклера використовує оцінку префікса що дає більш сприятливі оцінки рядкам, які з самого початку відповідають заданій довжині префікса . Дано два рядки і . Їхня подібність Джаро-Вінклера визначається як:
де:
- — подібність Джаро для рядків і
- — довжина загального префіксу на початку рядка — максимум до 4 символів
- є сталим коефіцієнтом масштабування того, наскільки оцінка коригується вгору за наявність загальних префіксів. не повинен перевищувати 0,25 (тобто 1/4, причому 4 - це максимальна довжина префікса, що розглядається), інакше подібність може стати більшою за 1. Стандартним значенням цієї константи у роботі Вінклера є .
Відстань Джаро — Вінклера визначається як .
Хоча її часто називають метрикою, відстань Джаро — Вінклера не є метрикою в математичному розумінні, оскільки вона не підпорядковується нерівності трикутника. Відстань Джаро — Вінклера також не відповідає аксіомі ідентичності .
Взаємозв'язок з іншими метриками відстані редагування
Є й інші популярні міри , які обчислюються з використанням іншого набору допустимих операцій редагування. Наприклад,
- відстань Левенштейна дозволяє видалення, вставлення та заміну;
- дозволяє всталення, видалення, заміну та транспонування двох сусідніх символів;
- найдовша загальна відстань підпослідовності (LCS) дозволяє лише вставлення та видалення, але не заміну;
- відстань Геммінга допускає лише заміну, отже, вона використовується лише для рядків однакової довжини.
зазвичай визначається як параметризована метрика, обчислена з певним набором дозволених операцій редагування, і кожній операції присвоюється вартість (можливо, нескінченна). Це додатково узагальнюється алгоритмами вирівнювання послідовностей ДНК, такими як алгоритм , які роблять вартість операції залежною від того, де вона застосовується.
Див. також
- Зв'язані записи
- Перепис населення
Виноски
- . RichardMinerich.com. Архів оригіналу за 31 грудня 2019. Процитовано 12 червня 2017.
Список літератури
- Cohen, W. W.; Ravikumar, P.; Fienberg, S. E. (2003). (PDF). KDD Workshop on Data Cleaning and Object Consolidation. 3: 73—8. Архів оригіналу (PDF) за 6 травня 2021. Процитовано 16 квітня 2021.
- (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.
- (1990). (PDF). Proceedings of the Section on Survey Research Methods. American Statistical Association: 354—359. Архів оригіналу (PDF) за 16 квітня 2021. Процитовано 16 квітня 2021.
- (2006). (PDF). Research Report Series, RRS. Архів оригіналу (PDF) за 6 травня 2021. Процитовано 16 квітня 2021.
Зовнішні посилання
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informatici ta statistici podibnist Dzharo Vinklera ce sho vimiryuye mizh dvoma poslidovnostyami Ye modifikaciyeyu metriki podibnosti Dzharo 1989 zaproponovanoyu u 1990 roci Vidstan Dzharo Vinklera vikoristovuye ocinku dovzhini prefiksa p displaystyle p sho daye bilsh spriyatlivi ocinki ryadkam sho z samogo pochatku vidpovidayut zadanij dovzhini prefiksa ℓ displaystyle ell Chim mensha vidstan Dzharo Vinklera dlya dvoh ryadkiv tim bilsh podibnimi ye ryadki Ocinka normuyetsya takim chinom sho 1 oznachaye tochnu vidpovidnist a 0 oznachaye vidsutnist bud yakoyi podibnosti Podibnist Dzharo Vinklera daye protilezhni rezultati Hocha yiyi chasto nazivayut metrikoyu vidstani vidstan Yaro Vinklera ne ye metrikoyu v matematichnomu rozuminni oskilki vona ne vikonuye nerivnist trikutnika ViznachennyaPodibnist Dzharo Podibnist Dzharo s i m j displaystyle sim j z dvoh zadanih ryadkiv s 1 displaystyle s 1 i s 2 displaystyle s 2 viznachayetsya yak s i m j 0 yaksho m 0 1 3 m s 1 m s 2 m t m v inshomu razi displaystyle sim j left begin array l l 0 amp text yaksho m 0 frac 1 3 left frac m s 1 frac m s 2 frac m t m right amp text v inshomu razi end array right Tut s i displaystyle s i dovzhina ryadka s i displaystyle s i m displaystyle m kilkist spivpadin div nizhche t displaystyle t kilkist transpozicij div nizhche Dva simvoli vid s 1 displaystyle s 1 i s 2 displaystyle s 2 vidpovidno vvazhayutsya spivpadinnyam lishe v tomu vipadku yaksho voni odnakovi i roztashovani ne dali nizh max s 1 s 2 2 1 displaystyle left lfloor frac max s 1 s 2 2 right rfloor 1 odin vid odnogo Kozhen simvol s 1 displaystyle s 1 porivnyuyetsya z usima vidpovidnimi simvolami v s 2 displaystyle s 2 Kilkist vidpovidnih ale v riznomu poryadku simvoliv rozdilenih na 2 viznachaye kilkist transpozicij Napriklad pri porivnyanni CRATE z TRACE lishe simvoli R A E ye spivpadinnyami tobto m 3 displaystyle m 3 Nezvazhayuchi na te sho C ta T z yavlyayutsya v oboh ryadkah voni roztashovani dali odin vid odnogo nizh 1 rezultat 5 2 1 displaystyle lfloor tfrac 5 2 rfloor 1 Otzhe t 0 displaystyle t 0 Yaksho porivnyuvati DwAyNE ta DuANE to tut spivpadinnya uzhe roztashovani v tomu samomu poryadku tozh transpoziciyi vidsutni Podibnist Dzharo Vinklera Podibnist Dzharo Vinklera vikoristovuye ocinku prefiksa p displaystyle p sho daye bilsh spriyatlivi ocinki ryadkam yaki z samogo pochatku vidpovidayut zadanij dovzhini prefiksa ℓ displaystyle ell Dano dva ryadki s 1 displaystyle s 1 i s 2 displaystyle s 2 Yihnya podibnist Dzharo Vinklera s i m w displaystyle sim w viznachayetsya yak s i m w s i m j ℓ p 1 s i m j displaystyle sim w sim j ell p 1 sim j de s i m j displaystyle sim j podibnist Dzharo dlya ryadkiv s 1 displaystyle s 1 i s 2 displaystyle s 2 ℓ displaystyle ell dovzhina zagalnogo prefiksu na pochatku ryadka maksimum do 4 simvoliv p displaystyle p ye stalim koeficiyentom masshtabuvannya togo naskilki ocinka koriguyetsya vgoru za nayavnist zagalnih prefiksiv p displaystyle p ne povinen perevishuvati 0 25 tobto 1 4 prichomu 4 ce maksimalna dovzhina prefiksa sho rozglyadayetsya inakshe podibnist mozhe stati bilshoyu za 1 Standartnim znachennyam ciyeyi konstanti u roboti Vinklera ye p 0 1 displaystyle p 0 1 Vidstan Dzharo Vinklera d w displaystyle d w viznachayetsya yak d w 1 s i m w displaystyle d w 1 sim w Hocha yiyi chasto nazivayut metrikoyu vidstan Dzharo Vinklera ne ye metrikoyu v matematichnomu rozuminni oskilki vona ne pidporyadkovuyetsya nerivnosti trikutnika Vidstan Dzharo Vinklera takozh ne vidpovidaye aksiomi identichnosti d x y 0 x y displaystyle d x y 0 leftrightarrow x y Vzayemozv yazok z inshimi metrikami vidstani redaguvannyaYe j inshi populyarni miri yaki obchislyuyutsya z vikoristannyam inshogo naboru dopustimih operacij redaguvannya Napriklad vidstan Levenshtejna dozvolyaye vidalennya vstavlennya ta zaminu dozvolyaye vstalennya vidalennya zaminu ta transponuvannya dvoh susidnih simvoliv najdovsha zagalna vidstan pidposlidovnosti LCS dozvolyaye lishe vstavlennya ta vidalennya ale ne zaminu vidstan Gemminga dopuskaye lishe zaminu otzhe vona vikoristovuyetsya lishe dlya ryadkiv odnakovoyi dovzhini zazvichaj viznachayetsya yak parametrizovana metrika obchislena z pevnim naborom dozvolenih operacij redaguvannya i kozhnij operaciyi prisvoyuyetsya vartist mozhlivo neskinchenna Ce dodatkovo uzagalnyuyetsya algoritmami virivnyuvannya poslidovnostej DNK takimi yak algoritm yaki roblyat vartist operaciyi zalezhnoyu vid togo de vona zastosovuyetsya Div takozhZv yazani zapisi Perepis naselennyaVinoski RichardMinerich com Arhiv originalu za 31 grudnya 2019 Procitovano 12 chervnya 2017 Spisok literaturiCohen W W Ravikumar P Fienberg S E 2003 PDF KDD Workshop on Data Cleaning and Object Consolidation 3 73 8 Arhiv originalu PDF za 6 travnya 2021 Procitovano 16 kvitnya 2021 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 1990 PDF Proceedings of the Section on Survey Research Methods American Statistical Association 354 359 Arhiv originalu PDF za 16 kvitnya 2021 Procitovano 16 kvitnya 2021 2006 PDF Research Report Series RRS Arhiv originalu PDF za 6 travnya 2021 Procitovano 16 kvitnya 2021 Zovnishni posilannya