Levenšteinin etäisyys

25 June 2008

Pieni nörtti sisimmässä heräsi kun tuli satunnaisen surffailun aikana törmättyä algoritmiin josta ei ole kuullut.

Levenšteinin etäisyys kuvaa pienintä määrää operaatioita jolla toinen merkkijono voidaan muuttaa toiseksi. Eli algoritmista on hyötyä silloin kun pitää selvittää miten lähellä toisiaan annetut merkkijonot ovat. Algoritmin kehitti Vladimir Levenshtein vuonna 1965.

Nopeasti pohtien tulee kaksi käytännön sovellusta mieleen.

Oikein kirjottamisen tarkoitus, saadaan aikaiseksi google tyyppinen ehdotus että tarkoititko sanaa x. Sekä salasanojen vahvuus testauksessa pystytään kätevästi tarkastamaan kuinka lähellä ehdotettu salasana on nykyistä salasanaa.

Jos kiinnostus heräsi niin lisää tietoa löytyy Englannin kielisestä Wikipediasta sekä PHP ohjeista evenshtein() funktion kohdalta. Valmiita selkeitä toteutuksia muille kielille tältä sivulta.

Kuinkahan paljon erilaisilta kirjoitus virheiltä olisi vältytty jos windowsissa olisi ollut valmiina palikka joka tarkistaa kielen ulkoasun. KDE:ssä vastaava systeemi on ollut ties kuinka kauan.

Posted in Tietokoneet | No comments »