- Fylls
- Läses
- Svar
Längsta gemensamma delsekvens (LCS)
Vilka bokstäver har två ord gemensamt, i samma ordning? Den längsta gemensamma delsekvensen svarar på det, och diff-verktyg, stavningskontroller och DNA-jämförelser bygger på den. Skriv två ord och se en tabell med deras bokstäver fyllas, och följ sedan svaret tillbaka från hörnet. Tryck på Spela för att se tabellen fyllas, 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 nedåt längs tabellens sida, det andra längs överkanten. Varje cell innehåller längden på den längsta gemensamma delsekvensen av bokstäverna till och med dess rad och kolumn. Till sist läses bokstäverna tillbaka 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
- Skriv två ord: det första står nedåt längs tabellens sida, det andra längs överkanten.
- 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.
- Se varje cell jämföra sina två bokstäver, och följ sedan den orange stigen tillbaka från hörnet för att läsa av svaret.
Så fungerar tabellen
En cell innehåller längden på den längsta gemensamma delsekvensen av det första ordets bokstäver till och med dess rad och det andra ordets bokstäver till och med dess kolumn. Raden och kolumnen märkta – står för ett tomt ord, så de är 0. Om cellens två bokstäver är lika är cellen ett mer än cellen snett upp till vänster. Om de skiljer sig ingår en av de två bokstäverna inte i svaret, så cellen tar det största av cellen ovanför och cellen till vänster.
Läsa tillbaka bokstäverna
Cellen längst ned till höger är svarets längd. Börja där för att hitta bokstäverna: där de två bokstäverna matchar ingår den bokstaven i delsekvensen, och du går snett upp till vänster; annars går du till den största av cellen ovanför och cellen till vänster. Bokstäverna du samlar på vägen, lästa baklänges, är en längsta gemensam delsekvens. Det kan finnas andra av samma längd; tillbakaläsningen hittar en av dem.
Ofta ställda frågor
Vad är skillnaden mellan en delsekvens och en delsträng?
En delsträng är en följd av bokstäver som står intill varandra, som ACE i RACER. En delsekvens behåller ordningen men får hoppa över bokstäver, så ACE är också en delsekvens av ABCDE. Den längsta gemensamma delsträngen är ett annat problem med en liknande tabell.
Hur snabb är LCS-algoritmen?
För ord med längderna m och n har tabellen m·n celler, som var och en fylls i ett steg, så arbetet är O(m·n). För två texter på 10 000 rader blir det 100 miljoner celler, och därför använder diff-verktyg smartare metoder som bygger på samma idé.
Är den längsta gemensamma delsekvensen unik?
Nej. ABCBDAB och BDCABA har tre olika gemensamma delsekvenser av längd 4: BCBA, BCAB och BDAB. Tabellen ger längden; tillbakaläsningen väljer en av dem.
Säger LCS hur lika två ord är?
Delvis. Två ord med längderna m och n och en längsta gemensam delsekvens av längd k kan göras om till varandra genom att ta bort m − k bokstäver och lägga till n − k. Redigeringsavståndet, som också tillåter att en bokstav byts ut, är ofta ett bättre mått.
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