Jaro i Jaro-Winkler mjere sličnosti riječi

2009-01-11 | PHP, JaroWinkler

Poželjna funkcionalnost svakog programa jest pomoć pri pogreškama, a pogreške u pisanju neke riječi, da li iz neznanja ili čiste zabune, česta su pojava. Kako pretpostaviti što je korisnik htio napisati?

Ovakvo se pitanje često viđa kod alata za provjeru teksta (eng. spellchecker) ili recimo kod korištenja tražilice Google, gdje vam, kada napišete neispravan pojam tražilica, ponudi "Did you mean ..." sa sličnim pojmom.

Jedno od rješenja, a ujedno i jedino koje ću ovdje opisati, jest provjera sličnosti pomoću Jaro ili Jaro-Winkler udaljenosti. Imena su dobili po američkim znanstvenicima Matt Jarou i William E. Winkleru. Prvotna primijena bila je uspoređivanje prezimena za potrebe američke administracije.

Jaro mjera sličnosti

Neka su zadane dvije riječi s = a1a2...ak i t = b1b2...bl. Kažemo da je znak ai u s pridružen t ako postoji bj=ai u t takav da vrijedi i-H < j < i+H, gdje je

H = min( |s| ,|t| ) / 2

(|s| označava broj slova u riječi s). Neka su s'=a'1a'2...a'k' znakovi u s pridruženi t i neka su t' = b'1b'2...b'l' znakovi u t pridruženi s (poredani u redoslijedu pojavljivanja u riječi s, odnosno t). Definirajmo sada transpoziciju za s' i t' kao poziciju i takvu da vrijedi a'i≠b'i. Neka je Ts',t' broj transpozijcija za s' i t' podijeljen sa dva. Jaro metrika za riječi s i t dana je s

Jaro-Winkler mjera sličnosti

Jaro-Winkler je proširenje Jaro mjere sličnosti, rad William E. Winklera objavljen 1999. godine. Istraživanjem se pokazalo da prefiks ima veliku ulogu u sličnosti riječi pa je William E. Winkler pomoću Jaro mjere sličnosti definirao Jaro-Winkler mjeru sličnosti na sljedeći način:

JaroWinkler(s,t) = Jaro(s,t) + 
    (prefixLength * PREFIXSCALE * ( 1.0 - Jaro(s,t) )),

gdje je prefixLength duljina zajedničkog prefixa između s i t te PREFIXSCALE konstantan realan broj kojim ćemo povećati ukupan rezulat. Očito je da će rezultati Jaro-Winkler i Jaro mjere sličnosti biti jednaki ako riječi s i t nemaju zajednički prefiks. Jaro-Winkler mjera sličnosti kao rezultat vraća realan broj, gdje veći broj predstavlja veću sličnost.

Implementacija

Izvorna implementacija, iz rada [3], u C programskom jeziku može se skinuti ovdje. Osobno sam još davne 2005., za potrebe određenog projekta, implementirao metode u PHPu pod uslovima GPL licence. Dakle, ukoliko vas ne smeta GPL licenca, slobodno skinite i koristite

Napomena

Dio teksta besramno je prepisan od članka [1] kojeg sam koautor. Za primjere pogledajte [1] ili [2], dok više teorije možete pronaći u [3]. Usporedbe s nekim drugim mjerama sličnosti pročitajte u [4].

Reference

  1. Anamari Nakić, Ivo Ugrina: Internet baza matematičkih pojmova e-Ghetaldus, Hrvatski matematički elektronički časopis "math.e", 2005.
  2. Wikipedia: Jaro-Winkler
  3. Winkler, W. E.: The state of record linkage and current research problems, Statistics of Income Division, Internal Revenue Service Publication R99/04.
  4. William W. Cohen, Pradeep Ravikumar, Stephen E. Fienberg: A comparison of string distance metrics for name-matching tasks, 2003.