Fyllda celler
Redigeringsavstånd
Behållna bokstäver

  • Fylls
  • Läses
  • Svar

Mer om redigeringsavståndet

Redigeringsavstånd (Levenshteinavstånd)

Hur många ändringar av en enda bokstav gör kitten till sitting? Tre: ersätt k med s, ersätt e med i och lägg till ett g. Det talet är redigeringsavståndet, och det är så stavningskontroller rangordnar förslag och biologer jämför gener. Skriv två ord och se en tabell räkna ut det. Tryck på Spela för att se tabellen fyllas i, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Skriv två ord: det första står längs tabellens vänstra sida, det andra längs överkanten. Varje cell innehåller det minsta antalet ändringar som gör bokstäverna till och med dess rad till bokstäverna till och med dess kolumn. Till sist läses ändringarna baklänges från cellen längst ned till höger. Nytt exempel väljer ett annat ordpar. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Skriv två ord: det första står längs tabellens vänstra sida, det andra längs överkanten.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst.
  3. Se varje cell ta den billigaste av sina tre grannar, och se sedan ändringarna läsas baklänges i orange.

Så fungerar tabellen

En cell innehåller det minsta antalet ändringar som gör det första ordets bokstäver till och med dess rad till det andra ordets bokstäver till och med dess kolumn. Den första raden räknar infogningar, som bygger upp det andra ordet från ingenting, och den första kolumnen räknar borttagningar. Om cellens två bokstäver är lika kopierar den cellen uppe till vänster: ingen ändring behövs. Annars är den ett mer än den minsta av tre grannar: uppe till vänster för en ersättning, ovanför för en borttagning och till vänster för en infogning.

Läsa ändringarna baklänges

Cellen längst ned till höger är redigeringsavståndet. Därifrån tar appen reda på vilken granne cellens värde kom från och går dit: diagonalt för en behållen eller ersatt bokstav, uppåt för en borttagen och åt vänster för en infogad. Lästa från övre vänstra hörnet bildar stegen en kortaste lista med ändringar, som visas under tabellen: en vanlig bokstav behålls, k→s är en ersättning, −e en borttagning och +g en infogning.

Ofta ställda frågor

Vad är Levenshteinavstånd?

Ett annat namn på det här redigeringsavståndet: det minsta antalet infogningar, borttagningar och ersättningar av en enda bokstav som gör en sträng till en annan. Det är uppkallat efter Vladimir Levenshtein, som beskrev det 1965.

Vad är redigeringsavståndet mellan kitten och sitting?

3: ersätt k med s, ersätt e med i och infoga g i slutet. Tabellen visar att det inte finns någon kortare lista med ändringar.

Hur snabb är algoritmen för redigeringsavstånd?

För ord med längderna m och n har tabellen (m + 1)·(n + 1) celler, som var och en fylls i ett steg, så det tar O(m·n) tid. Om man bara behöver avståndet räcker två rader av tabellen.

Vilka andra redigeringsavstånd finns det?

Damerau–Levenshteinavståndet räknar också ett byte av två intilliggande bokstäver som en ändring, vilket passar bra för skrivfel. Hammingavståndet tillåter bara ersättningar och fungerar för strängar av samma längd. LCS-avståndet tillåter bara infogningar och borttagningar.

Skickas något någonstans?

Nej. Allt räknas ut i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Gå till Editor