De Levenshteinafstand of bewerkingsafstand tussen twee strings is de minimale hoeveelheid bewerkingen die nodig is om de ene string in de andere te veranderen, waarbij de mogelijke bewerkingen zijn:
Deze afstandsmetriek is genoemd naar Vladimir Levenshtein, die er in 1965 een artikel aan wijdde. Dit algoritme wordt bijvoorbeeld gebruikt in spellingscorrectie, waar de computer moet gaan zoeken in een woordenboek naar bestaande woorden die minimale Levenshteinafstand hebben met een woord dat de gebruiker heeft geschreven. Zo zal een spellingscorrectie bijvoorbeeld het woord fuck kunnen corrigeren naar duck, omdat dit woord het meest lijkt op het geschreven woord en de gebruiker dus allicht per ongeluk gewoon een f heeft getypt waar er een d moest staan.
Formeel is de Levenshteinafstand als volgt gedefinieerd voor twee tekenreeksen \(s\) en \(t\):
$$ d(s, t) = \begin{cases} |s| & \text{als \(t\) leeg is,}\\ |t| & \text{als \(s\) leeg is,}\\ d(\mathrm{rest}(s), \mathrm{rest}(t)) & \text{als \( s_0 = t_0 \),}\\ 1 + \min\begin{cases} d(\mathrm{rest}(s), t),\\ d(s, \mathrm{rest}(t)),\\ d(\mathrm{rest}(s), \mathrm{rest}(t)) \end{cases} & \text{anders.} \end{cases} $$
Hier gebruiken we \(|s|\) om de lengte van de string \(s\) aan te duiden. We indexeren strings met subscripts, bijvoorbeeld \(s_0\) komt overeen met het eerste teken van \(s\). Met \(\mathrm{rest}(s)\) bedoelen we de string gevormd door het eerste teken van \(s\) weg te laten. Als we dus \(d(s, t)\) moeten berekenen, redeneren we als volgt:
Als het eerste teken van \(s\) niet gelijk is aan het eerste teken van \(t\), dan hebben we sowieso minstens één operatie nodig om \(s\) om te zetten naar \(t\) en rekenen we dus sowieso kost 1 aan. Welke operatie dit precies is, hangt af wat er het goedkoopst is:
We nemen dus het minimum over de kosten geassocieerd met deze drie operaties. Je kan deze formule voor de Levenshteinafstand direct implementeren in een naïeve recursieve strategie:
def lev(s, t):
if len(s) == 0:
return len(t)
elif len(t) == 0:
return len(s)
elif s[0] == t[0]:
return lev(s[1:], t[1:])
else:
return 1 + min([
lev(s[1:], t),
lev(s, t[1:]),
lev(s[1:], t[1:])
])
Dat is echter niet efficiënt: deze implementatie gaat dezelfde waarden heel vaak herberekenen. Om dit te vermijden, maken we gebruik van een andere heel belangrijke programmeertechniek: dynamisch programmeren. Dit is een techniek die heel vaak gebruikt wordt om recursieve algoritmen efficiënter te maken, door ze om te zetten naar een vorm waar recursie overbodig wordt. We doen dit door een tabel bij te houden van waarden die al berekend zijn, en halen deze waarden gewoon opnieuw op wanneer we ze nodig hebben in plaats van onze functie opnieuw op te roepen en de waarden telkens te herberekenen. Op die manier kunnen we heel veel dubbel werk vermijden.
Neem bijvoorbeeld de tekenreeksen kitten en sitting. We stellen een tabel op gebaseerd op deze strings:
| k | i | t | t | e | n | ||
|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| s | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| i | 2 | 2 | 1 | 2 | 3 | 4 | 5 |
| t | 3 | 3 | 2 | 1 | 2 | 3 | 4 |
| t | 4 | 4 | 3 | 2 | 1 | 2 | 3 |
| i | 5 | 5 | 4 | 3 | 2 | 2 | 3 |
| n | 6 | 6 | 5 | 4 | 3 | 3 | 2 |
| g | 7 | 7 | 6 | 5 | 4 | 4 | 3 |
Hier hebben we horizontaal de string kitten geschreven en verticaal de string sitting, met voor beide strings een extra witruimte in het begin. De getallen in de tabel zijn de Levenshteinafstanden voor delen van de originele strings. Specifiek bevat rij i, kolom j van deze tabel de Levenshteinafstand d(s[:i], t[:j]), waar s = 'sitting' en t = 'kitten' in dit geval. Hieruit volgt dat het getal helemaal rechtsonderaan (gemarkeerd in het blauw) de Levenshteinafstand geeft voor de volledige strings (in dit geval 3).
Het is veel efficiënter om de Levenshteinafstand uit te rekenen door eerst deze tabel op te stellen en dan het antwoord af te lezen rechtsonderaan dan via de recursieve aanpak te werken uit het voorbeeld hierboven. Dit komt doordat je dankzij deze tabel nooit waarden opnieuw zult herberekenen: als je van links naar rechts en van boven naar onder werkt in deze tabel, heb je altijd alle waarden reeds berekend die je nodig hebt voor de volgende cel in te vullen en hoef je jouw functie dus niet recursief aan te roepen. Specifiek definiëren we deze tabel als volgt. We maken een matrix L in Python en berekenen
L[i][j] = min([
L[i-1][j] + 1,
L[i][j-1] + 1,
L[i-1][j-1] + c
])
waar c = 1 als s[i] != t[j] en anders c = 0. Door i te laten lopen van 0 tot len(s) en j te laten lopen van 0 tot len(t), vullen we de tabel cel per cel in puur op basis van waarden die al berekend zijn. Merk op dat, ongeacht wat de strings s en t precies zijn, je altijd al een deel van de tabel kunt invullen: de volledige eerste rij en de volledige eerste kolom bevatten gewoon de getallen van 0 tot en met de lengte van de overeenkomstige string. De eerste rij komt namelijk overeen met d('', t[:0]), d('', t[:1]), d('', t[:2]) enzovoort, en analoog voor de eerste kolom. Aangezien een van de twee argumenten hier leeg is, is de Levenshteinafstand gewoon de lengte van de niet-lege string. Als je dus start met de implementatie, is het eerste wat je doet deze tabel aanmaken en invullen met de waarden die je sowieso al kent. Daarna vul je de rest van de waarden één voor één in, waarbij je van links naar rechts en van boven naar onder werkt. Je begint dus met:
L[i][0] = i # voor alle i in range(len(s))
L[0][j] = j # voor alle j in range(len(t))
Stel bijvoorbeeld dat we de waarde uit rij 1, kolom 2 (te tellen vanaf nul natuurlijk) willen berekenen, die gemarkeerd is in het geel. Dit komt overeen met d('s', 'ki'). We vullen nu in:
L[1][2] = min([
L[0][2] + 1,
L[1][1] + 1,
L[0][1] + c
])
In dit geval is 's' != 'i', dus is c = 1. De waarden L[0][2], L[1][1] en L[0][1] kennen we al: het zijn de cellen gemarkeerd in het zwart die we reeds ingevuld hebben in vorige iteraties. Hieruit volgt
L[1][2] = min([
2 + 1,
1 + 1,
1 + 1
]) = 2
Dit algoritme moet hoogstens len(s) + len(t) + len(s) * len(t) iteraties doen, in tegenstelling tot de naïeve recursieve implementatie die in het slechtste geval een exponentieel aantal iteraties zal uitvoeren.
Implementeer het dynamisch algoritme voor de Levenshteinafstand. Het algoritme leest twee strings s en t als invoer en geeft de Levenshteinafstand d(s,t) terug als uitvoer.
Invoer:
kitten
sitting
Uitvoer:
3