algorithm
Langste gemeenschappelijke gevolg
Zoeken…
Langste gemeenschappelijke vervolguitleg
Een van de belangrijkste implementaties van Dynamic Programming is het achterhalen van de langste gemeenschappelijke opeenvolging . Laten we eerst enkele basisterminologieën definiëren.
Subsequence:
Een subreeks is een reeks die kan worden afgeleid uit een andere reeks door enkele elementen te verwijderen zonder de volgorde van de resterende elementen te wijzigen. Laten we zeggen dat we een tekenreeks ABC hebben . Als we nul of een of meer dan één teken uit deze tekenreeks wissen, krijgen we de deelreeks van deze tekenreeks. De deelreeksen van tekenreeks ABC zijn dus { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Zelfs als we alle tekens verwijderen, is de lege tekenreeks ook een deelreeks. Om de deelreeks te achterhalen, hebben we voor elke tekens in een string twee opties - ofwel nemen we het karakter, ofwel niet. Dus als de lengte van de string n is , zijn er 2 n deelreeksen van die string.
Langste gemeenschappelijke gevolg:
Zoals de naam al doet vermoeden, is van alle gemeenschappelijke deelreeksen tussen twee strings de langste gemeenschappelijke deelreeks (LCS) die met de maximale lengte. Bijvoorbeeld: de gemeenschappelijke deelreeksen tussen "HELLOM" en "HMLD" zijn "H" , "HL" , "HM" enz. Hier is "HLL" de langste gemeenschappelijke deelreeks met lengte 3.
Brute-Force methode:
We kunnen alle subreeksen van twee strings genereren met behulp van backtracking . Dan kunnen we ze vergelijken om de gemeenschappelijke deelreeksen te ontdekken. Nadat we die met de maximale lengte moeten vinden. We hebben al gezien dat er 2 n deelreeksen van een reeks van lengte n zijn . Het zou jaren duren om het probleem op te lossen als onze n 20-25 kruist.
Dynamische programmeermethode:
Laten we onze methode benaderen met een voorbeeld. Stel dat we twee tekenreeksen abcdaf en acbcf hebben . Laten we deze aangeven met s1 en s2 . Dus de langste gemene deelreeks van deze twee reeksen is "abcf" , die lengte 4 heeft. Nogmaals herinner ik u eraan, de volgordes hoeven niet continu in de reeks te zijn. Om "abcf" te construeren, negeerden we "da" in s1 en "c" in s2 . Hoe komen we hier achter met Dynamic Programming?
We beginnen met een tabel (een 2D-array) met alle tekens van s1 op een rij en alle tekens van s2 in kolom. Hier is de tabel 0-geïndexeerd en plaatsen we de tekens van 1 tot en met. We zullen de tabel voor elke rij van links naar rechts doorkruisen. Onze tafel ziet eruit als:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Hier vertegenwoordigen elke rij en kolom de lengte van de langste gemeenschappelijke deelreeks tussen twee tekenreeksen als we de tekens van die rij en kolom nemen en toevoegen aan het voorvoegsel ervoor. Bijvoorbeeld: Tabel [2] [3] vertegenwoordigt de lengte van de langste gemeenschappelijke deelreeks tussen "ac" en "abc" .
De 0-de kolom geeft de lege deelreeks van s1 weer . Op dezelfde manier vertegenwoordigt de 0-de rij de lege deelreeks van s2 . Als we een lege deelreeks van een string nemen en proberen deze te matchen met een andere string, ongeacht hoe lang de lengte van de tweede substring is, heeft de gemeenschappelijke deelreeks 0 lengte. Dus we kunnen de 0-de rijen en 0-de kolommen vullen met 0'en. We krijgen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Laten we beginnen. Als we tabel [1] [1] vullen, vragen we ons af of we een string a en een andere string a en niets anders hebben, wat is de langste gemeenschappelijke deel hier? De lengte van de LCS is hier 1. Laten we nu eens kijken naar tabel [1] [2] . We hebben string ab en string a . De lengte van de LCS is 1. Zoals u kunt zien, is de rest van de waarden ook 1 voor de eerste rij, omdat deze alleen string a beschouwt met abcd , abcda , abcdaf . Onze tafel ziet er dus uit als:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Voor rij 2, die nu c bevat . Voor tabel [2] [1] hebben we ac aan de ene kant en een aan de andere kant. Dus de lengte van de LCS is 1. Waar hebben we deze 1 vandaan? Vanaf de top, waarbij de LCS duidt een tussen twee subreeksen. Dus wat we zeggen is, als s1 [2] en s2 [1] niet hetzelfde zijn, dan is de lengte van de LCS het maximum van de lengte van de LCS bovenaan of links . Als we de lengte van de LCS bovenaan nemen, geven we aan dat we het huidige teken van s2 niet nemen. Evenzo betekent het nemen van de lengte van de LCS aan de linkerkant dat we het huidige teken van s1 niet nemen om de LCS te maken. We krijgen:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Dus onze eerste formule zal zijn:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Verdergaand, voor tabel [2] [2] hebben we string ab en ac . Omdat c en b niet hetzelfde zijn, plaatsen we hier het maximum van de top of links. In dit geval is het weer 1. Daarna hebben we voor tabel [2] [3] tekenreeks abc en ac . Deze tijd huidige waarden van zowel rij als kolom zijn hetzelfde. Nu zal de lengte van de LCS gelijk zijn aan de maximale lengte van LCS tot nu toe + 1. Hoe krijgen we de maximale lengte van LCS tot nu toe? We controleren de diagonale waarde, die de beste overeenkomst tussen ab en a vertegenwoordigt . Vanuit deze status hebben we voor de huidige waarden nog een teken toegevoegd aan s1 en s2, wat toevallig hetzelfde was. Dus de lengte van LCS zal natuurlijk toenemen. We plaatsen 1 + 1 = 2 in tabel [2] [3] . We krijgen,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Dus onze tweede formule zal zijn:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
We hebben beide gevallen gedefinieerd. Met behulp van deze twee formules kunnen we de hele tabel vullen. Na het vullen van de tabel ziet het er als volgt uit:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
De lengte van de LCS tussen s1 en s2 is tabel [5] [6] = 4 . Hier zijn 5 en 6 respectievelijk de lengte van s2 en s1 . Onze pseudo-code zal zijn:
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
De tijdcomplexiteit voor dit algoritme is: O (mn) waarbij m en n de lengte van elke reeks aangeeft.
Hoe komen we erachter wat de langst voorkomende deelreeks is? We beginnen vanuit de rechteronderhoek. We zullen controleren waar de waarde vandaan komt. Als de waarde uit de diagonaal komt, dat wil zeggen dat tabel [i-1] [j-1] gelijk is aan tabel [i] [j] - 1 , drukken we op s2 [i] of s1 [j] (beide hetzelfde zijn) en diagonaal bewegen. Als de waarde van boven komt, betekent dit dat als Tabel [i-1] [j] gelijk is aan Tabel [i] [j] , we naar de top gaan. Als de waarde van links komt, betekent dit dat als Tabel [i] [j-1] gelijk is aan Tabel [i] [j] , we naar links gaan. Wanneer we de meest linkse of bovenste kolom bereiken, eindigt onze zoekopdracht. Vervolgens halen we de waarden uit de stapel en drukken ze af. De pseudo-code:
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
Op te merken punt: als zowel tabel [i-1] [j] als tabel [i] [j-1] gelijk is aan tabel [i] [j] en tabel [i-1] [j-1] niet gelijk aan Tabel [i] [j] - 1 , er kunnen op dat moment twee LCS zijn. Deze pseudo-code houdt geen rekening met deze situatie. U moet dit recursief oplossen om meerdere LCS's te vinden.
De tijdcomplexiteit voor dit algoritme is: O (max (m, n)) .