- Wordt gevuld
- Wordt gelezen
- Antwoord
Bewerkingsafstand (Levenshteinafstand)
Hoeveel wijzigingen van één letter maken van kitten het woord sitting? Drie: vervang k door s, vervang e door i en voeg een g toe. Dat getal is de bewerkingsafstand. Zo rangschikken spellingcontroles hun suggesties en vergelijken biologen genen. Typ twee woorden en zie hoe een tabel het vindt. Druk op Afspelen om de tabel te zien vollopen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Typ twee woorden: het eerste staat langs de linkerkant van de tabel, het tweede langs de bovenkant. Elke cel bevat het kleinste aantal bewerkingen dat de letters tot en met zijn rij verandert in de letters tot en met zijn kolom. Aan het eind worden de bewerkingen teruggelezen vanaf de cel rechtsonder. Nieuw voorbeeld kiest een ander woordpaar. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.
Hoe het werkt
- Typ twee woorden: het eerste staat langs de linkerkant van de tabel, het tweede langs de bovenkant.
- Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen.
- Zie hoe elke cel de goedkoopste van zijn drie buren neemt, en zie daarna hoe de bewerkingen in oranje worden teruggelezen.
Hoe de tabel werkt
Een cel bevat het kleinste aantal bewerkingen dat de letters van het eerste woord tot en met zijn rij verandert in de letters van het tweede woord tot en met zijn kolom. De eerste rij telt invoegingen, die het tweede woord uit het niets opbouwen, en de eerste kolom telt verwijderingen. Als de twee letters van een cel gelijk zijn, neemt de cel de cel linksboven over: er is geen bewerking nodig. Anders is hij één meer dan de kleinste van drie buren: linksboven voor vervangen, erboven voor verwijderen en links voor invoegen.
De bewerkingen teruglezen
De cel rechtsonder is de bewerkingsafstand. Vanaf daar zoekt de app uit van welke buur de waarde van de cel kwam en stapt erheen: schuin voor een behouden of vervangen letter, omhoog voor een verwijderde, naar links voor een ingevoegde. Gelezen vanaf linksboven vormen de stappen een kortste lijst van bewerkingen, die onder de tabel staat: een gewone letter blijft behouden, k→s is een vervanging, −e een verwijdering en +g een invoeging.
Veelgestelde vragen
Wat is de Levenshteinafstand?
Een andere naam voor deze bewerkingsafstand: het kleinste aantal invoegingen, verwijderingen en vervangingen van één letter dat de ene string in de andere verandert. Hij is genoemd naar Vladimir Levenshtein, die hem in 1965 beschreef.
Wat is de bewerkingsafstand tussen kitten en sitting?
3: vervang k door s, vervang e door i en voeg aan het eind g in. De tabel laat zien dat er geen kortere lijst van bewerkingen bestaat.
Hoe snel is het algoritme voor de bewerkingsafstand?
Voor woorden met lengte m en n heeft de tabel (m + 1)·(n + 1) cellen, die elk in één stap worden gevuld, dus het kost O(m·n) tijd. Als je alleen de afstand nodig hebt, zijn twee rijen van de tabel genoeg.
Welke andere bewerkingsafstanden zijn er?
De Damerau–Levenshteinafstand telt ook het verwisselen van twee naburige letters als één bewerking, wat goed past bij typefouten. De Hammingafstand staat alleen vervangingen toe en werkt voor strings van gelijke lengte. De LCS-afstand staat alleen invoegingen en verwijderingen toe.
Wordt er iets verstuurd?
Nee. Alles wordt in je browser berekend, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor