Största vanliga följden
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 juli 2022; kontroller kräver 15 redigeringar .Uppgiften att hitta den längsta gemensamma undersekvensen ( eng. längsta gemensamma undersekvensen , LCS) är uppgiften att hitta en sekvens som är en undersekvens av flera sekvenser (vanligtvis två). Ofta definieras problemet som att hitta alla de största delsekvenserna. Detta är ett klassiskt datavetenskapligt problem , som har tillämpningar, särskilt i textfilsjämförelseproblemet ( diff- verktyget ), såväl som i bioinformatik .
En undersekvens kan erhållas från någon ändlig sekvens om någon uppsättning av dess element (eventuellt tomma) tas bort från den senare. Till exempel är BCDB en undersekvens av sekvensen ABCDDBAB. Vi säger att en sekvens Z är en gemensam undersekvens av sekvenserna X och Y om Z är en undersekvens av både X och Y. Det krävs för två sekvenser X och Y för att hitta en gemensam undersekvens av störst längd. Observera att det kan finnas flera NOP.
Notera! En delsekvens skiljer sig från en delsträng . Till exempel, om det finns en källsekvens "ABCDEF" kommer "ACE" att vara en delsekvens men inte en delsträng och "ABC" kommer att vara både en delsekvens och en delsträng.
Lösning på problemet
Låt oss jämföra två lösningsmetoder: brute-force-sökning och dynamisk programmering .
Fullständig uppräkning
Det finns olika tillvägagångssätt för att lösa detta problem med en fullständig uppräkning - du kan sortera ut alternativ för efterföljande, raderingsalternativ från dessa sekvenser, etc. Men i alla fall kommer programmets gångtid att vara ett polynom i strängarnas längder.
Dynamisk programmeringsmetod
| A | B | C | D | ||
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| D | 0 | ← 0 | ← 0 | ← 0 | ↖ 1 |
| C | 0 | ← 0 | ← 0 | ↖ 1 | ← 1 |
| D | 0 | ← 0 | ← 0 | ↑ 1 | ↖ 2 |
| A | 0 | ↖ 1 | ← 1 | ← 1 | ↑ 2 |
Hitta först längden på den största undersekvensen. Antag att vi letar efter en lösning för fallet (n 1 , n 2 ), där n 1 , n 2 är längden på den första och andra strängen. Låt lösningar redan existera för alla delproblem (m 1 , m 2 ) mindre än det givna. Därefter reduceras uppgiften (n 1 , n 2 ) till mindre deluppgifter enligt följande:
![{\displaystyle f(n_{1},n_{2})=\left\{{\begin{array}{ll}0,&n_{1}=0\eller n_{2}=0\\f(n_ {1}-1,n_{2}-1)+1,&s_{1}[n_{1}]=s_{2}[n_{2}]\\max(f(n_{1}-1, n_{2}),f(n_{1},n_{2}-1)),&s_{1}[n_{1}]\neq s_{2}[n_{2}]\end{array}} \höger.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/247fee8787b87a38bc364638e91965c11181338a)
Låt oss nu återgå till problemet med att konstruera en undersekvens. För att göra detta lägger vi till den befintliga algoritmen ett minne för varje uppgift i deluppgiften genom vilken den löses. Nästa åtgärd, med början från det sista elementet, går vi upp till början längs riktningarna som ges av den första algoritmen och skriver tecknen i varje position. Detta kommer att vara svaret på detta problem.
Algoritmens körtid kommer att vara .
Se även
- Algoritmer på strängar
- Största gemensamma delsträngen
Länkar
- Att hitta den största gemensamma följden . algolist.ru. Hämtad: 15 augusti 2013.
- Algoritm för att hitta längden på den största gemensamma följden . coders.ask-ru.net.
| Strängar | |
|---|---|
| Stränglikhetsmått | |
| Sök efter delsträng | |
| palindromer | |
| Sekvensjustering | |
| Suffixstrukturer | |
| Övrig | |