Zobecněný příponový strom - Generalized suffix tree

Příponový strom pro řetězce ABAB a BABA. Příponové odkazy nezobrazeno.

v počítačová věda, a generalizovaný příponový strom je příponový strom pro sadu struny. Vzhledem k sadě řetězců ${ displaystyle D = S_ {1}, S_ {2}, tečky, S_ {d}}$ celkové délky ${ displaystyle n}$ , to je Patricia strom obsahující vše ${ displaystyle n}$ přípony strun. Většinou se používá v bioinformatika.^[1]

Funkčnost

Může být zabudován ${ displaystyle Theta (n)}$ čas a prostor a lze je použít k vyhledání všech ${ displaystyle z}$ výskyty řetězce ${ displaystyle P}$ délky ${ displaystyle m}$ v ${ displaystyle O (m + z)}$ čas, který je asymptoticky optimální (za předpokladu, že velikost abecedy je konstantní^[2]^:119).

Při konstrukci takového stromu by měl být každý řetězec vyplněn jedinečným symbolem (nebo řetězcem) značky mimo abecedu, aby se zajistilo, že žádná přípona není podřetězcem jiného, což zaručuje, že každá přípona je reprezentována jedinečným uzlem listu.

Algoritmy pro konstrukci GST zahrnují Ukkonenův algoritmus (1995) a McCreightův algoritmus (1976).

Příklad

Strom přípon pro řetězce ABAB a BABA je zobrazen na obrázku výše. Jsou polstrovány jedinečnými ukončovacími řetězci $0 a $1. Čísla v uzlech listu jsou číslo řetězce a počáteční pozice. Všimněte si, jak přechod zleva doprava uzlů listu odpovídá seřazenému pořadí přípon. Terminátory mohou být řetězce nebo jedinečné jednotlivé symboly. Hrany zapnuté $ z kořene jsou v tomto příkladu vynechány.

Alternativy

Alternativou k vytvoření stromu generalizovaných přípon je zřetězení řetězců a sestavení regulárního příponový strom nebo pole přípon pro výsledný řetězec. Když se po hledání vyhodnotí zásahy, globální pozice se mapují na dokumenty a místní pozice pomocí nějakého algoritmu a / nebo datové struktury, jako je binární vyhledávání v počátečních / koncových pozicích dokumentů.

Reference

^ Paul Bieganski; John Riedl; John Carlis; Ernest F. Retzel (1994). "Generalizované stromy přípon pro data biologické sekvence". Biotechnology Computing, Sborník příspěvků z dvacáté sedmé mezinárodní konference na Havaji dne. str. 35–44. doi:10.1109 / HICSS.1994.323593.
^ 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 978-0-521-58519-4.

externí odkazy

Média související s Zobecněný příponový strom na Wikimedia Commons
C implementace stromu Generalized Suffix Tree pro dva řetězce

[BRCR-1] Paul Bieganski; John Riedl; John Carlis; Ernest F. Retzel (1994). "Generalizované stromy přípon pro data biologické sekvence". Biotechnology Computing, Sborník příspěvků z dvacáté sedmé mezinárodní konference na Havaji dne. str. 35–44. doi:10.1109 / HICSS.1994.323593.

[Gus97-2] 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 978-0-521-58519-4.

[1]

[2]

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
Sekvenční zarovnání	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 Porovnávání vzorů Shoda komprimovaného vzoru Nejdelší společná posloupnost Nejdelší běžný podřetězec Těžba sekvenčních vzorů Třídění