Fyldte celler
Ens par
Længste indtil nu

  • Bliver fyldt
  • Læses
  • Svar

Mere om den længste fælles delsekvens

Længste fælles delsekvens (LCS)

Hvilke bogstaver har to ord til fælles i samme rækkefølge? Den længste fælles delsekvens svarer på det, og diff-værktøjer, stavekontroller og DNA-sammenligninger bygger på den. Skriv to ord, se en tabel med deres bogstaver blive fyldt, og følg så svaret tilbage fra hjørnet. Tryk på Afspil for at se tabellen blive fyldt, 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 siden af tabellen, det andet hen langs toppen. Hver celle indeholder længden af den længste fælles delsekvens af bogstaverne til og med dens række og kolonne. Til sidst læses bogstaverne tilbage 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

  1. Skriv to ord: det første står ned langs siden af tabellen, det andet hen langs toppen.
  2. 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.
  3. Se hver celle sammenligne sine to bogstaver, og følg derefter den orange sti tilbage fra hjørnet for at aflæse svaret.

Sådan virker tabellen

En celle indeholder længden af den længste fælles delsekvens af det første ords bogstaver til og med dens række og det andet ords bogstaver til og med dens kolonne. Rækken og kolonnen markeret med – står for et tomt ord, så de er 0. Hvis cellens to bogstaver er ens, er cellen én større end cellen skråt op til venstre. Hvis de er forskellige, er det ene af de to bogstaver ikke med i svaret, så cellen tager den største af cellen ovenover og cellen til venstre.

Læs bogstaverne tilbage

Cellen nederst til højre er længden af svaret. Begynd der for at finde bogstaverne: hvor de to bogstaver er ens, er det bogstav med i delsekvensen, og du går skråt op til venstre; ellers går du til den største af cellen ovenover og cellen til venstre. Bogstaverne, du samler undervejs, læst baglæns, er en længste fælles delsekvens. Der kan være andre af samme længde; tilbagelæsningen finder én af dem.

Ofte stillede spørgsmål

Hvad er forskellen på en delsekvens og en delstreng?

En delstreng er en række bogstaver, der står lige efter hinanden, som ACE i RACER. En delsekvens bevarer rækkefølgen, men må springe bogstaver over, så ACE er også en delsekvens af ABCDE. Den længste fælles delstreng er et andet problem med en lignende tabel.

Hvor hurtig er LCS-algoritmen?

For ord med længderne m og n har tabellen m·n celler, som hver udfyldes i ét trin, så arbejdet er O(m·n). For to tekster på 10.000 linjer er det 100 millioner celler, og derfor bruger diff-værktøjer smartere metoder, der bygger på samme idé.

Er den længste fælles delsekvens entydig?

Nej. ABCBDAB og BDCABA har tre forskellige fælles delsekvenser af længde 4: BCBA, BCAB og BDAB. Tabellen giver længden; tilbagelæsningen vælger én af dem.

Fortæller LCS, hvor ens to ord er?

Delvist. To ord med længderne m og n og en længste fælles delsekvens af længde k kan laves om til hinanden ved at slette m − k bogstaver og indsætte n − k. Redigeringsafstanden, som også tillader at erstatte et bogstav, er ofte et bedre mål.

Bliver noget sendt nogen steder hen?

Nej. Alt beregnes i din browser, og dine seneste indstillinger bliver 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