hakank.blogg

« Några fler tankar om vidskeplighet, spel och datorprogram | Main | Skånsk bloggmiddag söndagen 9 oktober, 14.00 restaurang Aten, Malmö (OBS! Klockslag ändrat) »

september 11, 2005

Ordavstånd (edit distances): Levenshtein och Hirschberg med lite extra finesser

Sedan länge har jag varit intresserad av hur lika ord är varandra. Ett sätt är att se hur många operationer som krävs för att transformera det ena ordet till det andra, och på detta vis få "ordavståendet" mellan orden. Se nedan för lite andra skriverier och program i detta och näraliggande ämnen.

Exempel
Ordavståndet mellan ordet håkan och ordet hakank är 2 eftersom det krävs två operationer för att transformera det första ordet till det andra: byt ut "å" till "a" och lägg till ett "k" på slutet. De möjliga operationerna för att omvandla ett ord till ett annat är:
* byt ut (replace)
* lägg till (insert)
* ta bort (delete)

samt "behåll" (keep) som egentligen inte är en operation eftersom ingenting görs. De engelska begreppen används nedan.

Edit distances
Sådana transformationer/jämförelser kallas för (används i) edit distance (googlesökning). En av de mer moderna användningarna är att jämföra två DNA-sekvenser med varandra för att se hur mycket eller på vilket sätt de matchar eller inte matchar, och det ligger mycket forskning (och pengar!) kring att göra ruskigt snabba och bra strängjämförelsemetoder.

Två av de mest kända algoritmerna för sådant är Levenshtein och Hirschberg (namnen från respektive upphovsperson).

Programmet Edit distances
Var lugn, jag tänker inte förklara algoritmerna här. Däremot vore det skoj att visa hur de fungerar och hur de kommer fram till ordavståndet. Detta är gjort i programmet Edit distances, som nu kommer att förklaras lite mer.

Körning av programmet
Låt oss jämföra orden håkan och hakank som nämndes ovan. En körning av programmet ger följande resultat:


...
Operations (graphical):
håkan-
| ||| 
hakank

Explanation:
'-': insert or delete
'|': keep
' ': replace

Long description (string position in parenthesis):
keep 'h' (1)
replace 'å' with 'a' (2)
keep 'k' (3)
keep 'a' (4)
keep 'n' (5)
insert 'k' (6)

Short description (k: keep, i: insert, d: delete, r: replace):
krkkki

It was 2 edit operations:
keep: 4
replace: 1
insert: 1
('keep' is not counted as an operation)


Förklaring
Här förklaras resultatet mer i detalj. Först visas den grafiska representationen av tranformationen:

håkan-
| ||| 
hakank


Ett "-" i den första raden betyder att en bokstav läggs till ("insert") i det andra ordet, dvs det avslutande "k". Tecknet "|" innebär att bokstäverna är samma (operationen "keep") i samma position. Om det är tomt i mellanraden innebär det att man byter ut en bokstav (här att "å" ersätts av "a"). Ett "-" i sista raden innebär att man tar bort en bokstav ("delete").

Efter det visas en "pratversion" av operationerna i korrekt ordning, där talen inom parentes anger radpositionen (eller "operationsnumret" om man så vill). Notera att positionen inte är för orden utan för den sträng som visas i den grafiska representationen.

keep 'h' (1)
replace 'å' with 'a' (2)
keep 'k' (3)
keep 'a' (4)
keep 'n' (5)
insert 'k' (6)


Så kommer en kortversion av operationern med koderna: k: keep, i: insert, d: delete, r: replace:

krkkki


vilket helt enkelt är första bokstäverna i de engelska namnen för operationerna.

Slutligen visas lite statistik där 2:an är det eftersöka ordavståndet. Och som sagt är keep inte någon egentlig operation, så 2 kommer här från antal replace och antal insert (1+1=2).


It was 2 edit operations:
keep: 4
replace: 1
insert: 1


Två algoritmer?
Varför två algoritmer, de ger ju samma resultat? Skoj att du noterat det. Visst, de ger ofta samma resultat, men inte riktigt alltid. T.ex. för jämförelsen mellan " abc e" och "abdec" (notera mellanslagen) så ger Hirschberg följande operationer: dddkkddrki:

   abc  e-
   ||   | 
---ab--dec


medan Levenshtein ger dddkkdrrr, dvs:

   abc  e
   ||    
---ab-dec


De ger olika antal keep-operationer (3 respektive 2), vilket kan vara viktigt. Det är dock samma antal edit distance operationer.

Om man vill man se den exakta skillnaden mellan dessa två operationslistor passar det ju bra att använda programmet för detta.

Tips: Lägg till mellanslag före eller efter
För vissa jämförelser kan det bli väldigt tråkiga operationer, t.ex. kjellerstrand -> hakank.blogg är det i stort sett bara utbyten: drrrrrrrrrrrr. Om man däremot lägger till lite mellanslag före eller efter endera ordet kan man se lite andra mappningar.

Exempel: lägg till ett gäng (t.ex. 13 mellanslag) före "kjellerstrand" så kommer följande mappning.

                          kjellerstrand

                          |   |        

---------------------hakank-.bl-----ogg


Naturligtvis innebär detta att antal operationer inte stämmer med ursprungsjämförelsen, men det är kanske av underordnad betydelse. I och för sig skulle programmet kunna justera för sådant trixande, men det finns alltid risker med sådan intelligens...

Fet credit
En stor fet credit måste göras till Lloyd Allison som kodat Javascript-versionerna av Levenshtein och Hirschberg.

Mitt program använder inte koden rakt av, men den är mer eller mindre strikt konverterad till Perl-kod. Programmet har även vissa finesser som saknas på Allisons sidor, t.ex. prat- och kortversionen av operationerna. Jag har inte brytt mig om att visa riktigt alla Allisons finesser, dvs tracen för Hirschberg.

Se även liknande program och skriverier
Skapa stavfel som råkar använda samma operationer som i ovan nämnda program. Där finns även några andra referernser.
Läsning av förvanskade ord
Nearest words
New Markov words II

Eventuellt relevant är också kategorin: Reguljära uttryck etc.

Lite länkar
Dan Hirschberg, speciellt dennes publikationer
Dan Gusfield: Algorithms on Strings, Trees, and Sequences
Alberto Apostolico, Zvi Galil (ed): Pattern Matching Algorithms.

(Det var det. Nu kan jag fundera lite på Thebes Visualiserad singulärvärdesuppdelning.)

Posted by hakank at september 11, 2005 10:14 EM Posted to Program | Reguljära uttryck etc | Språk

Comments

Posted by: Kristofer at september 12, 2005 02:30 EM

Posted by: hakank at september 13, 2005 07:10 EM

Posted by: jonas at december 12, 2005 09:16 EM

Posted by: hakank at december 12, 2005 10:20 EM