Sztring hasonlósági metrikák

A sztring hasonlósági metrikák két vagy több sztring közötti távolságot/hasonlóságot hivatottak mérni, számszerűsíteni különböző metrikus terekben. Egy sztring akár egy teljes dokumentum is lehet, így a sztring hasonlósági metrikák adott esetekben dokumentumok összehasonlítására is alkalmasak lehetnek, ez esetben azonban alkalmazásuk nem minden esetben célszerű. A sztring hasonlósági metrikákat (string linkage methods, record linkage methods) elsősorban a kezdetekben arra dolgozták ki, hogy adott relációs adatbázis rekordjai közötti hasonlóság kimutatható legyen. Az ilyen rekord hasonlósági metrikák alkalmazása révén lehetséges például eltérő módon felvitt, azonban ugyan azt az információt tároló rekordok összevonása, azáltal eltérő adatbázisok teljes migrációja is. Példakét tekinthetjük azt az esetet, amikor két bank igyekszik lakossági ügyfeleket tartalmazó adatbázisaik egyesítésére, és az egyik bank az ügyfelek címét "| teljes_név | H-IRSZ | Város, utca, házszám |", míg a másik bank "| vezetéknév | keresznév | utca | házszám | város | IRSZ" formában tárolja. Ekkor a "| Kis Géza | H-6000 | Kecskemét, Petőfi Sándor u. 5. II/2" rekord ugyan az, mint a "| Kiss | Géza | Petőfi S. utca | 5.2.2 | Kecskemét | 6000 |" rekord a másik bank adatbázisában. Szövegsztringek egymáshoz képesti összehasonlítása akkor is fontossá válhat, ha pl. ki szeretnénk szűrni a helyesírási hibákból adódó zajt vagy fel szeretnénk oldani rövidítéseket, vagy akár két protein lánc hasonlóságát szeretnénk kvantitatíve kimutatni. Ebben az esetben ugyanis ezen sztringek egymáshoz képesti távolsága (pl. egy helyesen leírt szó és ugyan azon szó helyesírási hibával) közti távolság kicsi lesz, míg teljesen más szavaktól mért távolságuk értelem szerűen nagy. A szövegbányászat elemi eszköztárai közé sorolhatóak ezek a metrikus módszerek. A legismertebb szöveges sztring metrikák az alábbiak.

• Hamming távolság
• Levenshtein távolság
• Needleman-Wunch távolság (Sellers algoritmus)
• Smith-Waterman távolság
• Gotoh (Smith-Waterman-Gotoh) távolság
• Blokk távolság / L1 távolság / Manhattan távolság
• Monge Elkan távolság
• Jaro távolság
• Jaro Winkler távolság
• Soundex távolság
• Egyezőség koefficiens
• Dice koefficiens
• Jaccard hasonlóság (Jaccard koefficiens vagy Tanimoto koefficiens)
• Átfedés koefficiens
• Euklidészi vagy L2 távolság
• Minkowski távolság
• Tchebyschev távolság
• Canberra távolság
• Koszinusz távolság
• Szórás alapú távolság
• Hellinger távolság (Bhattacharyya távolság)
• Információs sugár (Jensen-Shannon divergencia)
• Harmonikus átlag
• Ferdeség
• Névcsere valószínűség
• Tau metrika
• Fellegi és Sunters (SFS) távolság
• TFIDF súlyozás
• N-gram módszer
• Ukkonen algoritmusa
• Mahalanobis távolság
• Fogalmi hasonlósági mértékek.

Vázsonyi Miklós