Nejdelší běžný problém s podřetězcem - Longest common substring problem

v počítačová věda, nejdelší běžný problém s podřetězcem je najít nejdelší tětiva (nebo řetězce), což je a podřetězec (nebo jsou podřetězce) dvou nebo více řetězců.

Příklad

Nejdelší běžný podřetězec řetězců „ABABC“, „BABCA“ a „ABCBA“ je řetězec „ABC“ o délce 3. Další běžné podřetězce jsou „A“, „AB“, „B“, „BA“, „BC“ a „C“.

  ABABC ||| BABCA ||| ABCBA

Definice problému

Vzhledem k tomu, dva řetězce, ${ displaystyle S}$ délky ${ displaystyle m}$ a ${ displaystyle T}$ délky ${ displaystyle n}$ , najděte nejdelší řetězec, který je podřetězcem obou ${ displaystyle S}$ a ${ displaystyle T}$ .

Zobecněním je k-společný dílčí problém. Vzhledem k sadě řetězců ${ displaystyle S = {S_ {1}, ..., S_ {K} }}$ , kde ${ displaystyle | S_ {i} | = n_ {i}}$ a ${ displaystyle Sigma n_ {i} = N}$ . Najít pro každého ${ displaystyle 2 leq k leq K}$ , nejdelší řetězce, které se vyskytují jako podřetězce alespoň ${ displaystyle k}$ struny.

Algoritmy

Lze najít délky a počáteční pozice nejdelších běžných podřetězců ${ displaystyle S}$ a ${ displaystyle T}$ v ${ displaystyle Theta (n + m)}$ čas pomocí a generalizovaný příponový strom. Najít je dynamické programování náklady ${ displaystyle Theta (nm)}$ . Řešení zobecněného problému trvá ${ displaystyle Theta (n_ {1} + ... + n_ {K})}$ prostor a ${ displaystyle Theta (n_ {1}}$ ·...· ${ displaystyle n_ {K})}$ čas s dynamické programování a vzít ${ displaystyle Theta (N * K)}$ čas s generalizovaný příponový strom.

Příponový strom

Zobecněný příponový strom pro řetězce „ABAB“, „BABA“ a „ABBA“ číslované 0, 1 a 2.

Nejdelší běžné podřetězce sady řetězců lze najít sestavením a generalizovaný příponový strom pro řetězce a poté najít nejhlubší vnitřní uzly, které mají listové uzly ze všech řetězců v podstromu pod ním. Na obrázku vpravo je strom přípon pro řetězce „ABAB“, „BABA“ a „ABBA“, vyplněné jedinečnými zakončovacími řetězci, které se stanou „ABAB $ 0“, „BABA $ 1“ a „ABBA $ 2“. Všechny uzly představující „A“, „B“, „AB“ a „BA“ mají potomky všech řetězců s čísly 0, 1 a 2.

Vytvoření stromu přípon trvá ${ displaystyle Theta (N)}$ čas (pokud je velikost abecedy konstantní). Pokud je strom procházen zdola nahoru bitovým vektorem, který říká, které řetězce jsou vidět pod každým uzlem, lze problém k-společný podřetězec vyřešit v ${ displaystyle Theta (NK)}$ čas. Pokud je strom přípon připraven na konstantní čas nejnižší společný předek vyhledávání, to lze vyřešit v ${ displaystyle Theta (N)}$ čas.^[1]

Pseudo kód

Následující pseudokód najde sadu nejdelších běžných podřetězců mezi dvěma řetězci s dynamickým programováním:

funkce LCSubstr (S [l..r], T [l..n]) L: = pole(1..r, 1..n) z: = 0 ret: = {} pro i: = 1..r pro j: = 1..n -li S [i] = T [j] -li i = 1 nebo j = 1 L [i, j]: = 1 jiný                    L [i, j]: = L [i - 1, j - 1] + 1 -li L [i, j]> z z: = L [i, j] ret: = {S [i - z + 1..i]} jiný -li L [i, j] = z ret: = ret ∪ {S [i - z + 1..i]} jiný                L [i, j]: = 0 vrátit se ret

Tento algoritmus běží ${ displaystyle O (nr)}$ čas. Proměnná z se používá k uchování délky dosud nejdelšího běžného podřetězce. Sada ret se používá k držení sady řetězců, které jsou dlouhé z. Sada ret lze efektivně uložit pouhým uložením indexu i, což je poslední znak nejdelšího běžného podřetězce (o velikosti z) místo S [i-z + 1..i]. Tedy všechny nejdelší běžné podřetězce budou pro každé i in ret, S [(ret [i] -z) .. (ret [i])].

Následující triky lze použít ke snížení využití paměti implementace:

Ponechejte pouze poslední a aktuální řádek tabulky DP, abyste ušetřili paměť ( ${ displaystyle O ( min (r, n))}$ namísto ${ displaystyle O (nr)}$ )
V řádcích ukládejte pouze nenulové hodnoty. To lze provést pomocí hash tabulek místo polí. To je užitečné pro velké abecedy.

Viz také

Deduplikace dat
Nejdelší palindromický podřetězec
n-gram, všechny možné podřetězce délky n které jsou obsaženy v řetězci
Detekce plagiátorství

Reference

^ Gusfield, Dan (1999) [1997]. Algoritmy řetězců, stromů a sekvencí: Počítačová věda a výpočetní biologie. USA: Cambridge University Press. ISBN 0-521-58519-8.

externí odkazy

[Gus97-1] Gusfield, Dan (1999) [1997]. Algoritmy řetězců, stromů a sekvencí: Počítačová věda a výpočetní biologie. USA: Cambridge University Press. ISBN 0-521-58519-8.

[1]

Struny
Řetězcová metrika	Přibližná shoda řetězce Bitapový algoritmus Vzdálenost Damerau – Levenshtein Upravit vzdálenost Gestaltová shoda Hammingova vzdálenost Vzdálenost Jaro – Winkler Lee vzdálenost Levenshtein automat Levenshteinova vzdálenost Wagner – Fischerův algoritmus
Algoritmus prohledávání řetězců	Algoritmus Apostolico – Giancarlo Algoritmus vyhledávání řetězců Boyer – Moore Algoritmus Boyer – Moore – Horspool Algoritmus Knuth – Morris – Pratt Algoritmus Rabin – Karp
Vyhledávání více řetězců	Aho – Corasick Algoritmus Commentz-Walter
Regulární výraz	Porovnání motorů s regulárním výrazem Pravidelná gramatika Thompsonova konstrukce Nedeterministický konečný automat
Zarovnání sekvence	Hirschbergův algoritmus Algoritmus Needleman – Wunsch Smith – Watermanův algoritmus
Datová struktura	DAFSA Pole přípon Příponový automat Příponový strom Zobecněný příponový strom Lano Ternární vyhledávací strom Trie
jiný	Analýza Shoda vzoru Shoda komprimovaného vzoru Nejdelší společná posloupnost Nejdelší běžný podřetězec Těžba sekvenčních vzorů Třídění