Levenshtein-afstand
De Levenshtein-afstand is een maat die aangeeft hoeveel elementaire bewerkingen nodig zijn om de ene tekenreeks in de andere om te zetten. Daarbij zijn drie bewerkingen toegestaan:
- een teken invoegen;
- een teken verwijderen;
- een teken vervangen.
De Levenshtein-afstand wordt veel gebruikt in informatica en computationele taalkunde, vooral in toepassingen zoals spellingscontrole, zoekmachines, automatische correctie en patroonherkenning. Het algoritme maakt het mogelijk om te bepalen hoe sterk twee woorden of tekenreeksen op elkaar lijken.
Wanneer een gebruiker bijvoorbeeld een woord verkeerd typt, kan een spellingscontrole met behulp van de Levenshtein-afstand snel bepalen welke correcte woorden het dichtst bij de foutieve invoer liggen.
De berekening gebeurt met een matrix waarin elke cel de minimale kost bevat om een prefix van de eerste tekenreeks om te zetten in een prefix van de tweede tekenreeks. Door de matrix systematisch op te vullen, wordt stap voor stap het kleinste aantal noodzakelijke bewerkingen bepaald.
In tegenstelling tot de Hamming-afstand kan de Levenshtein-afstand ook worden toegepast op tekenreeksen met verschillende lengtes.
Een concreet voorbeeld
Beschouw de tekenreeksen \( s \) en \( t \):
$$ s = "kitten" $$
$$ t = "sitting" $$
We willen bepalen hoeveel bewerkingen nodig zijn om "kitten" om te zetten in "sitting".
- Vervanging
Vervang \( k \) door \( s \): $$ "kitten" \rightarrow "sitten" $$ - Vervanging
Vervang \( e \) door \( i \): $$ "sitten" \rightarrow "sittin" $$ - Invoeging
Voeg een \( g \) toe aan het einde van de tekenreeks: $$ "sittin" \rightarrow "sitting" $$
Er zijn dus drie bewerkingen nodig: twee vervangingen en één invoeging. De Levenshtein-afstand tussen "kitten" en "sitting" is daarom gelijk aan 3.
Om dit proces formeel te beschrijven construeren we een matrix met dimensies \( (m+1) \times (n+1) \), waarbij \( m \) de lengte van "kitten" voorstelt (6) en \( n \) de lengte van "sitting" (7).
Er wordt een extra rij en kolom toegevoegd om ook transformaties van en naar de lege tekenreeks te kunnen weergeven.
| "" | s | i | t | t | i | n | g | |
|---|---|---|---|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| k | 1 | |||||||
| i | 2 | |||||||
| t | 3 | |||||||
| t | 4 | |||||||
| e | 5 | |||||||
| n | 6 |
De cel \( (0, j) \) stelt de kost voor om een lege tekenreeks om te zetten in het prefix van "sitting" met lengte \( j \). Deze kost stijgt lineair van 0 tot 7.
Omgekeerd geeft de cel \( (i, 0) \) de kost weer om het prefix van "kitten" met lengte \( i \) om te zetten in een lege tekenreeks. Ook hier loopt de kost lineair op van 0 tot 6.
Voor elke cel \( (i, j) \) wordt de minimale kost bepaald door drie mogelijke bewerkingen te vergelijken:
- een teken verwijderen uit "kitten" (kost van de bovenliggende cel, \( +1 \));
- een teken invoegen in "kitten" (kost van de linker cel, \( +1 \));
- een teken vervangen (kost van de diagonale cel); wanneer beide tekens identiek zijn, wordt geen extra kost toegevoegd.
Daarna wordt de matrix stap voor stap ingevuld:
| "" | s | i | t | t | i | n | g | |
|---|---|---|---|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| k | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| i | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| t | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| t | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| e | 5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
| n | 6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |
Een lege tekenreeks omzetten in "s", "si", "sit" enzovoort vereist telkens één extra bewerking voor elk toegevoegd teken.
Op dezelfde manier neemt de kost voor het omzetten van "k", "ki", "kit" enzovoort naar een lege tekenreeks telkens met één eenheid toe voor ieder verwijderd teken.
- De cel (1,1) geeft de kost weer om "k" te vervangen door "s". Die kost is gelijk aan 1, omdat slechts één vervanging nodig is.
- De cel (2,2) komt overeen met de kost om "ki" om te zetten in "si". Die blijft gelijk aan 1, omdat het tweede teken (i) identiek is.
- De cel (3,3) stelt de kost voor om "kit" om te zetten in "sit". Ook hier blijft de kost gelijk aan 1, aangezien de derde letter (t) niet verandert.
- De cel (4,4) geeft de kost aan om "kitt" om te zetten in "sitt". De kost blijft opnieuw gelijk aan 1, omdat ook het vierde teken (t) identiek blijft.
- De cel (5,5) heeft een kost van 2 voor de omzetting van "kitte" naar "sitti", als gevolg van de vervanging \( e \rightarrow i \).
- De cel (6,6) geeft de kost weer om "kitten" om te zetten in "sittin". Die blijft gelijk aan 2, omdat het laatste teken (n) hetzelfde is.
- De cel (6,7) toont een totale kost van 3 om "kitten" om te zetten in "sitting", waarbij aan het einde een \( g \) wordt toegevoegd.
Zo bereiken we uiteindelijk de eindcel van de matrix, waarin de totale cumulatieve kost wordt weergegeven.
De cel rechtsonder \( (6,7) \) bevat de minimale kost om "kitten" om te zetten in "sitting": een totale kost van 3.
Dit resultaat komt exact overeen met de berekende Levenshtein-afstand: twee vervangingen en één invoeging.
Topologie geïnduceerd door de Levenshtein-afstand
De Levenshtein-afstand induceert een metrische ruimtestructuur op de verzameling van tekenreeksen, net zoals de Hamming-afstand. Dat komt doordat zij voldoet aan de fundamentele eigenschappen van een metriek.
- Niet-negativiteit: De Levenshtein-afstand tussen twee tekenreeksen \( x \) en \( y \) is altijd groter dan of gelijk aan nul. Bovendien geldt \( D_L(x, y) = 0 \) dan en slechts dan als \( x = y \). Er zijn dus geen bewerkingen nodig om een tekenreeks in zichzelf om te zetten.
- Symmetrie: De Levenshtein-afstand is symmetrisch, dus \( D_L(x, y) = D_L(y, x) \). Het aantal bewerkingen dat nodig is om van \( x \) naar \( y \) te gaan, is hetzelfde als het aantal bewerkingen om van \( y \) naar \( x \) te gaan.
- Driehoeksongelijkheid: Er geldt altijd \( D_L(x, z) \leq D_L(x, y) + D_L(y, z) \). De directe afstand tussen \( x \) en \( z \) is dus nooit groter dan de som van de afstanden via een tussenliggende tekenreeks \( y \).
Dankzij deze eigenschappen definieert de Levenshtein-afstand een metrische ruimte op de verzameling van tekenreeksen.
Omdat het om een geldige metriek gaat, kan men ook een geïnduceerde metrische topologie definiëren.
Voor een straal \( r \) en een tekenreeks \( x \) noemt men de open bol met middelpunt \( x \) de verzameling van alle tekenreeksen \( y \) waarvoor de afstand tot \( x \) strikt kleiner is dan \( r \):
$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$
De verzameling van al deze open bollen vormt een basis voor de geïnduceerde topologie.
Dit formele kader is bijzonder nuttig in toepassingen waarin de "nabijheid" tussen woorden of tekenreeksen belangrijk is. In automatische spellingscorrectiesystemen kan een woord met een kleine Levenshtein-afstand tot een woordenboekterm bijvoorbeeld als mogelijke correctie worden voorgesteld.
Vanuit dit perspectief kunnen tekenreeksen worden beschouwd als punten in een metrische ruimte, terwijl de geïnduceerde topologie wordt gebruikt om hun onderlinge nabijheid formeel te analyseren.
Voorbeeld
Beschouw de verzameling \( X \), bestaande uit tekenreeksen van drie tekens:
$$ X = \{"cat", "bat", "cut"\} $$
We definiëren een basis van de topologie door open bollen met straal \( r = 2 \) te nemen, gecentreerd rond elk element van \( X \):
$$ B(x, r) = \{ y \mid D_L(x, y) < r \} $$
Elke open bol bevat alle tekenreeksen die volgens de Levenshtein-afstand slechts in één teken verschillen van de centrale tekenreeks.
Opmerking: Bij een straal \( r = 2 \) worden alleen tekenreeksen opgenomen waarvan de afstand strikt kleiner is dan 2. Dus $$ B(x, 2) = \{ y \mid D_L(x, y) < 2 \} $$ Om een gesloten verzameling te definiëren die ook de randpunten bevat, gebruikt men de niet-strikte ongelijkheid: $$ C(x, 2) = \{ y \mid D_L(x, y) \le 2 \} $$
Laten we nu de open bollen met straal \( 2 \) bekijken, gecentreerd rond elk element van \( X \):
- Open bol met middelpunt "cat" $$ B("cat", 2) = \{"cat", "bat"\} $$ Deze tekenreeksen kunnen in elkaar worden omgezet door één enkele tekenvervanging.
- Open bol met middelpunt "bat" $$ B("bat", 2) = \{"bat", "cat"\} $$ Deze bol bevat alle tekenreeksen die met één enkele bewerking in "bat" kunnen worden omgezet.
- Open bol met middelpunt "cut" $$ B("cut", 2) = \{"cut"\} $$ Geen enkele andere tekenreeks uit \( X \) bevindt zich op afstand 1 van "cut". Daarom bevat deze bol uitsluitend de tekenreeks zelf.
De verzamelingen \( B("cat", 2) \), \( B("bat", 2) \) en \( B("cut", 2) \) vormen een basis van de topologie die door de Levenshtein-afstand wordt geïnduceerd bij straal \( r = 2 \).
Vanuit deze basis kunnen alle andere open verzamelingen worden opgebouwd als willekeurige unies van deze open bollen.
De unie van \( B("bat", 2) \) en \( B("cut", 2) \) is bijvoorbeeld:
$$ B("bat", 2) \cup B("cut", 2) $$
Aangezien \( B("bat", 2) = \{"cat", "bat"\} \) en \( B("cut", 2) = \{"cut"\} \), verkrijgen we:
$$ B("bat", 2) \cup B("cut", 2) = \{"cat", "bat"\} \cup \{"cut"\} $$
$$ B("bat", 2) \cup B("cut", 2) = \{"cat", "bat", "cut"\} $$
Deze verzameling is dus eveneens een open verzameling binnen de geïnduceerde topologie.
Zo verkrijgen we op \( X \) een metrische topologie die door de Levenshtein-afstand wordt geïnduceerd, waarbij elke open verzameling kan worden geschreven als een unie van deze basiselementen.
Enzovoort.
