Vzdálenost Jaro – Winkler - Jaro–Winkler distance

v počítačová věda a statistika, Vzdálenost Jaro – Winkler je řetězec metrický měření an upravit vzdálenost mezi dvěma sekvencemi. Jedná se o variantu, kterou v roce 1990 navrhl William E. Winkler z Jaro vzdálenost metrický (1989, Matthew A. Jaro ).

Vzdálenost Jaro – Winkler používá a předpona měřítko ${displaystyle p}$ což dává příznivější hodnocení řetězcům, které se shodují od začátku s nastavenou délkou předpony ${displaystyle ell}$.

Čím nižší je vzdálenost Jaro – Winkler pro dva řetězce, tím více jsou řetězce podobné. Skóre je normalizováno tak, že 0 znamená přesnou shodu a 1 znamená, že neexistuje podobnost. The Jaro – Winklerova podobnost je inverze (1 - vzdálenost Jaro – Winkler).

Ačkoli se často označuje jako a vzdálenost metrická, vzdálenost Jaro – Winkler není a metrický v matematickém smyslu tohoto pojmu, protože se neřídí nerovnost trojúhelníku.

Definice

Jaro Podobnost

Jaro podobnost ${displaystyle sim_ {j}}$ dvou daných řetězců ${displaystyle s_ {1}}$ a ${displaystyle s_ {2}}$ je

${displaystyle sim_ {j} = left {{egin {array} {ll} 0 & {ext {if}} m = 0 {frac {1} {3}} left ({frac {m} {| s_ {1} |}} + {frac {m} {| s_ {2} |}} + {frac {mt} {m}} ight) & {ext {jinak}} end {array}} ight.}$

Kde:

• ${displaystyle | s_ {i} |}$ je délka řetězce ${displaystyle s_ {i}}$;
• ${displaystyle m}$ je počet odpovídající znaky (viz. níže);
• ${displaystyle t}$ je poloviční počet transpozice (viz. níže).

Dvě postavy z ${displaystyle s_ {1}}$ a ${displaystyle s_ {2}}$ jsou respektovány vhodný pouze pokud jsou stejné a ne dále než ${displaystyle leftlfloor {frac {max (| s_ {1} |, | s_ {2} |)} {2}} ightfloor -1}$ znaky od sebe.

Každá postava ${displaystyle s_ {1}}$ je porovnáván se všemi odpovídajícími znaky v ${displaystyle s_ {2}}$. Počet shodných (ale odlišných pořadí sekvencí) znaků děleno 2 definuje počet transpoziceNapříklad při porovnávání CRATE s TRACE jsou odpovídající znaky pouze „R“ „A“ „E“, tj. M = 3. Ačkoli se „C“, „T“ objevují v obou řetězcích, jsou od sebe dále než 1 (výsledek ${displaystyle lfloor {frac {5} {2}} patro -1}$). Proto t = 0. V DwAyNE versus DuANE jsou shodná písmena již ve stejném pořadí D-A-N-E, takže nejsou nutné žádné transpozice.

Podobnost Jaro – Winkler

Podobnost Jaro – Winkler používá a předpona měřítko ${displaystyle p}$ což dává příznivější hodnocení řetězcům, které se shodují od začátku s nastavenou délkou předpony ${displaystyle ell}$. Vzhledem k tomu, dva řetězce ${displaystyle s_ {1}}$ a ${displaystyle s_ {2}}$, jejich podoba Jaro – Winkler ${displaystyle sim_ {w}}$ je:

${displaystyle sim_ {w} = sim_ {j} + ell p (1-sim_ {j}),}$

kde:

• ${displaystyle sim_ {j}}$ je Jarova podobnost pro řetězce ${displaystyle s_ {1}}$ a ${displaystyle s_ {2}}$
• ${displaystyle ell}$ je délka běžné předpony na začátku řetězce, maximálně 4 znaky
• ${displaystyle p}$ je konstanta měřítko o kolik je skóre upraveno směrem nahoru, protože má společné předpony. ${displaystyle p}$ by neměla přesáhnout 0,25 (tj. 1/4, přičemž 4 je maximální uvažovaná délka předpony), jinak by podobnost mohla být větší než 1. Standardní hodnota této konstanty ve Winklerově díle je ${displaystyle p = 0,1}$

Vzdálenost Jaro-Winkler ${displaystyle d_ {w}}$ je definován jako ${displaystyle d_ {w} = 1-sim_ {w}}$.

Ačkoli se často označuje jako a vzdálenost metrická, vzdálenost Jaro – Winkler není a metrický v matematickém smyslu tohoto pojmu, protože se neřídí nerovnost trojúhelníku.^[1] Vzdálenost Jaro-Winkler také nesplňuje axiom identity ${displaystyle d (x, y) = 0leva doprava šipka x = y}$.

Vztah k dalším úpravám metrik vzdálenosti

Existují i ​​další populární opatření upravit vzdálenost, které se počítají pomocí jiné sady povolených editačních operací. Například,

• the Levenshteinova vzdálenost umožňuje odstranění, vložení a nahrazení;
• the Vzdálenost Damerau – Levenshtein umožňuje vkládání, mazání, nahrazování a transpozice dvou sousedních znaků;
• the nejdelší společná posloupnost (LCS) vzdálenost umožňuje pouze vkládání a mazání, nikoli substituci;
• the Hammingova vzdálenost umožňuje pouze substituci, proto se vztahuje pouze na řetězce stejné délky.

Upravit vzdálenost je obvykle definována jako parametrizovatelná metrika počítaná se specifickou sadou povolených editačních operací a každé operaci je přiřazena cena (možná nekonečná). To je dále generalizováno DNA zarovnání sekvence algoritmy jako např Smith – Watermanův algoritmus, díky nimž náklady na operaci závisí na tom, kde se použije.

Viz také

• Zaznamenejte propojení
• Sčítání lidu

Poznámky pod čarou

Reference

• Cohen, W. W .; Ravikumar, P .; Fienberg, S.E. (2003). „Srovnání metrik vzdálenosti řetězce pro úkoly shodující se s názvy“ (PDF). Workshop KDD o čištění dat a konsolidaci objektů. 3: 73–8.
• Jaro, M. A. (1989). „Pokroky v metodice rekordních vazeb, jak byly použity při sčítání lidu z Tampy na Floridě v roce 1985“. Journal of the American Statistical Association. 84 (406): 414–20. doi:10.1080/01621459.1989.10478785.
• Jaro, M. A. (1995). Msgstr "Pravděpodobné propojení velkého datového souboru veřejného zdraví". Statistika v medicíně. 14 (5–7): 491–8. doi:10.1002 / sim.4780140510. PMID  7792443.
• Winkler, W. E. (1990). „Metriky komparátoru řetězců a vylepšená pravidla rozhodování v modelu Fellegi-Sunter modelu propojení záznamů“ (PDF). Sborník části věnované metodám průzkumného výzkumu. Americká statistická asociace: 354–359.

• Winkler, W. E. (2006). „Přehled propojení záznamů a aktuální směry výzkumu“ (PDF). Řada výzkumných zpráv, RRS.

externí odkazy

• strcmp.c - původní implementace C autorem algoritmu