Langste gemeenschappelijke deelrij (LCS)
Als je twee versies van een bestand vergelijkt, vormen de regels die niet veranderd zijn een gemeenschappelijke deelrij van beide. Als je de langste vindt, weet je precies wat er is toegevoegd en wat er is verwijderd. Hetzelfde idee legt DNA-strengen naast elkaar en stelt spellingcorrecties voor, en het wordt opgelost met een van de elegantste tabellen uit de informatica.
Het probleem
Een deelrij van een woord houdt een deel van zijn letters in de oorspronkelijke volgorde: ACE is een deelrij van ABCDE, maar EA niet. Een gemeenschappelijke deelrij van twee woorden is een deelrij van allebei, en het probleem is de langste te vinden. Een woord van lengte n heeft 2ⁿ deelrijen, dus ze allemaal proberen is bij meer dan een paar letters hopeloos.
De tabel
Stel dat len[i][j] de lengte is van de langste gemeenschappelijke deelrij van de eerste i letters van het ene woord en de eerste j letters van het andere. Een leeg woord heeft niets gemeen met wat dan ook, dus de eerste rij en kolom zijn 0. Als letter i gelijk is aan letter j, is len[i][j] = len[i − 1][j − 1] + 1: de overeenkomst verlengt wat ervoor kwam. Zo niet, dan is len[i][j] de grootste van len[i − 1][j] en len[i][j − 1]: laat een van de twee letters vallen en houd het betere resultaat.
Een voorbeeld
Vergelijk ABCBDAB met BDCABA. De eerste letter van het tweede woord, B, komt overeen met de B in rij 2; de C in de derde kolom komt overeen met rij 3, enzovoort, en elke overeenkomst telt één op bij de cel linksboven. De cel rechtsonder eindigt op 4. Teruglezen vanaf daar geeft BCBA, maar BCAB en BDAB zijn even lang: een langste gemeenschappelijke deelrij hoeft niet uniek te zijn.
Het antwoord teruglezen
Begin in de cel rechtsonder. Als de letters van zijn rij en kolom overeenkomen, hoort die letter bij het antwoord: noteer hem en ga schuin naar linksboven. Ga anders naar de buur, erboven of links, met de grootste waarde, want daar heeft de cel zijn waarde vandaan. Stop bij de eerste rij of kolom. De genoteerde letters, omgedraaid, vormen de deelrij.
Geschiedenis en toepassingen
De tabelmethode werd rond 1970 onafhankelijk door verschillende mensen gevonden, onder wie Robert Wagner en Michael Fischer, wier artikel uit 1974 de nauw verwante bewerkingsafstand oploste. In 1975 liet Dan Hirschberg zien hoe je de deelrij met veel minder geheugen vindt, en in 1976 bouwden James Hunt en Douglas McIlroy het programma Unix diff op langste gemeenschappelijke deelrijen van regels. Biologen gebruiken hetzelfde idee, met scores, om DNA- en eiwitsequenties uit te lijnen.
Ontdek het zelf
Open de app en druk op Stap. De twee letters die vergeleken worden lichten op in de koppen; bij een overeenkomst wordt de blauwe cel linksboven gelezen, bij een verschil de twee blauwe cellen erboven en links. Als de tabel vol is, klimt het oranje pad terug vanuit de hoek en verschijnen de letters van het antwoord onder de tabel.
Veelgestelde vragen
Hoeveel tijd en geheugen heeft het LCS-algoritme nodig?
O(m·n) tijd voor woorden met lengtes m en n. De volledige tabel heeft ook O(m·n) geheugen nodig om het antwoord terug te lezen; Dan Hirschberg liet in 1975 zien hoe je de deelrij zelf vindt met maar O(min(m, n)) geheugen.
Hoe gebruikt diff de langste gemeenschappelijke deelrij?
Het behandelt elke regel van een bestand als één symbool en zoekt een langste gemeenschappelijke deelrij van de regels van de twee bestanden. Regels in die deelrij zijn ongewijzigd; de overige regels van het oude bestand zijn verwijderd, en de overige regels van het nieuwe bestand zijn toegevoegd.
En bij drie of meer woorden?
De tabel krijgt één dimensie per woord, dus drie woorden van lengte n hebben n³ cellen nodig. Voor een willekeurig aantal woorden is het probleem NP-moeilijk.
Hoe hangt LCS samen met de bewerkingsafstand?
Als alleen invoegen en verwijderen zijn toegestaan, is de bewerkingsafstand van twee woorden hun totale lengte min twee keer de lengte van hun langste gemeenschappelijke deelrij. Sta je ook vervangen toe, dan krijg je de Levenshtein-afstand, die met een heel vergelijkbare tabel wordt berekend.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer de langste gemeenschappelijke deelrij