- Bliver fyldt
- Læses
- Svar
Redigeringsafstand (Levenshtein-afstand)
Hvor mange ændringer af ét bogstav gør kitten til sitting? Tre: Erstat k med s, erstat e med i, og tilføj et g. Det tal er redigeringsafstanden, og det er sådan, stavekontroller rangerer forslag, og biologer sammenligner gener. Skriv to ord, og se en tabel finde den. Tryk på Afspil for at se tabellen blive udfyldt, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Skriv to ord: Det første står ned langs venstre side af tabellen, det andet hen over toppen. Hver celle indeholder det mindste antal ændringer, der gør bogstaverne til og med dens række til bogstaverne til og med dens kolonne. Til sidst læses ændringerne baglæns fra cellen nederst til højre. Nyt eksempel vælger et andet ordpar. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.
Sådan virker det
- Skriv to ord: Det første står ned langs venstre side af tabellen, det andet hen over toppen.
- Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst.
- Se hver celle tage den billigste af sine tre naboer, og se derefter ændringerne blive læst baglæns i orange.
Sådan virker tabellen
En celle indeholder det mindste antal ændringer, der gør det første ords bogstaver til og med dens række til det andet ords bogstaver til og med dens kolonne. Den første række tæller indsættelser, der bygger det andet ord op fra ingenting, og den første kolonne tæller sletninger. Hvis cellens to bogstaver er ens, kopierer den cellen oppe til venstre: Der skal ingen ændring til. Ellers er den én mere end den mindste af tre naboer: oppe til venstre for en erstatning, ovenover for en sletning og til venstre for en indsættelse.
Læs ændringerne baglæns
Cellen nederst til højre er redigeringsafstanden. Derfra finder appen ud af, hvilken nabo cellens værdi kom fra, og går dertil: diagonalt for et bevaret eller erstattet bogstav, op for et slettet og til venstre for et indsat. Læst fra øverst til venstre giver trinene en korteste liste af ændringer, som vises under tabellen: Et almindeligt bogstav er bevaret, k→s er en erstatning, −e en sletning og +g en indsættelse.
Ofte stillede spørgsmål
Hvad er Levenshtein-afstanden?
Et andet navn for denne redigeringsafstand: det mindste antal indsættelser, sletninger og erstatninger af ét bogstav, der gør én streng til en anden. Den er opkaldt efter Vladimir Levenshtein, som beskrev den i 1965.
Hvad er redigeringsafstanden mellem kitten og sitting?
3: Erstat k med s, erstat e med i, og indsæt g til sidst. Tabellen viser, at der ikke findes nogen kortere liste af ændringer.
Hvor hurtig er algoritmen for redigeringsafstand?
For ord med længderne m og n har tabellen (m + 1)·(n + 1) celler, som hver udfyldes i ét trin, så det tager O(m·n) tid. Hvis man kun skal bruge afstanden, er to rækker af tabellen nok.
Hvilke andre redigeringsafstande findes der?
Damerau–Levenshtein-afstanden tæller også det at bytte om på to nabobogstaver som én ændring, hvilket passer godt til tastefejl. Hamming-afstanden tillader kun erstatninger og virker for strenge af samme længde. LCS-afstanden tillader kun indsættelser og sletninger.
Bliver der sendt noget nogen steder hen?
Nej. Alt beregnes i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Gå til Editor