Pole přípon - Suffix array

Pole přípon
Typ	Pole
Vynalezl	Manber & Myers (1990)
Časová složitost v velká O notace
	Průměrný	Nejhorší případ
Prostor	${ displaystyle { mathcal {O}} (n)}$	${ displaystyle { mathcal {O}} (n)}$
Konstrukce	${ displaystyle { mathcal {O}} (n)}$	${ displaystyle { mathcal {O}} (n)}$

v počítačová věda, a pole přípon je seřazený pole ze všech přípony a tětiva. Jedná se o datovou strukturu používanou mimo jiné v plnotextových indexech, algoritmech komprese dat a poli bibliometrie.

Pole přípon byla zavedena Manber & Myers (1990) jako jednoduchá prostorově efektivní alternativa k stromy přípon. Byli nezávisle objeveni Gaston Gonnet v roce 1987 pod názvem PAT pole (Gonnet, Baeza-Yates a Snider 1992 ).

Li, Li & Huo (2016) dal první na místě ${ displaystyle { mathcal {O}} (n)}$ Algoritmus konstrukce pole časových přípon, který je optimální jak v čase, tak v prostoru, kde na místě znamená, že algoritmus potřebuje pouze ${ displaystyle { mathcal {O}} (1)}$ další prostor za vstupním řetězcem a polem výstupní přípony.

Vylepšená pole přípon (ESA) jsou pole přípon s dalšími tabulkami, které reprodukují plnou funkčnost stromů přípon se zachováním stejného času a složitosti paměti.^[1]Pole přípony pro podmnožinu všech přípon řetězce se nazývá řídké pole přípon.^[2] Bylo vyvinuto několik pravděpodobnostních algoritmů, které minimalizují využití další paměti, včetně optimálního algoritmu času a paměti.^[3]

Definice

Nechat ${ displaystyle S = S [1] S [2] ... S [n]}$ být ${ textstyle n}$-strunu a nechte ${ displaystyle S [i, j]}$ označte podřetězec z ${ displaystyle S}$ od ${ displaystyle i}$ na ${ displaystyle j}$.

Pole přípony ${ displaystyle A}$ z ${ displaystyle S}$ je nyní definováno jako pole celých čísel poskytujících počáteční pozice přípony z ${ displaystyle S}$ v lexikografický řád. To znamená, záznam ${ displaystyle A [i]}$ obsahuje počáteční pozici ${ displaystyle i}$- nejmenší přípona v ${ displaystyle S}$ a tedy pro všechny ${ displaystyle 1$: ${ displaystyle S [A [i-1], n]$.

Každý přípona z ${ displaystyle S}$ se objeví v ${ displaystyle A}$ přesně jednou. Přípony jsou jednoduché řetězce. Tyto řetězce jsou tříděny (jako v papírovém slovníku), než jsou uloženy jejich počáteční pozice (celočíselné indexy) ${ displaystyle A}$.

Příklad

Zvažte text ${ displaystyle S}$=banán $ indexovat:

i	1	2	3	4	5	6	7
${ displaystyle S [i]}$	b	A	n	A	n	A	$

Text končí zvláštním ověřovacím dopisem $ který je jedinečný a lexikograficky menší než kterýkoli jiný znak. Text má následující přípony:

Tyto přípony lze seřadit vzestupně:

Pole přípony ${ displaystyle A}$ obsahuje počáteční pozice těchto seřazených přípon:

i =	1	2	3	4	5	6	7
${ displaystyle A [i]}$ =	7	6	4	2	1	5	3

Pole přípony s příponami napsanými svisle dole pro přehlednost:

i =	1	2	3	4	5	6	7
${ displaystyle A [i]}$ =	7	6	4	2	1	5	3
1	$	A	A	A	b	n	n
2		$	n	n	A	A	A
3			A	A	n	$	n
4			$	n	A		A
5				A	n		$
6				$	A
7					$

Například ${ displaystyle A [3]}$ obsahuje hodnotu 4, a proto odkazuje na příponu začínající na pozici 4 uvnitř ${ displaystyle S}$, což je přípona ana $.

Korespondence s příponovými stromy

Pole přípon jsou úzce spjata s stromy přípon:

• Pole přípon lze sestavit provedením a průchod první hloubkou stromu přípon. Pole přípon odpovídá listovým štítkům uvedeným v pořadí, v jakém jsou navštíveny během procházení, pokud jsou hrany navštíveny v lexikografickém pořadí podle jejich prvního znaku.
• Strom přípon lze sestavit v lineárním čase pomocí kombinace pole přípon a LCP pole. Popis algoritmu viz odpovídající část v LCP pole článek.

Ukázalo se, že každý algoritmus stromu přípon lze systematicky nahradit algoritmem, který používá pole přípon rozšířené o další informace (například LCP pole ) a řeší stejný problém ve stejné časové složitosti.^[4]Mezi výhody příponových polí oproti stromům přípon patří vylepšené požadavky na prostor, jednodušší algoritmy lineární konstrukce času (např. Ve srovnání s Ukkonenův algoritmus ) a vylepšené umístění mezipaměti.^[5]

Efektivita prostoru

Pole přípon byla zavedena Manber & Myers (1990) za účelem zlepšení prostorových požadavků stromy přípon: Přípona ukládá pole ${ displaystyle n}$ celá čísla. Za předpokladu, že to celé číslo vyžaduje ${ displaystyle 4}$ bajtů, vyžaduje pole přípony ${ displaystyle 4n}$ bajtů celkem. To je podstatně méně než ${ displaystyle 20n}$ bajty, které vyžaduje pečlivá implementace stromu přípon.^[6]

V některých aplikacích však mohou být požadavky na prostor v příponových polích stále příliš vysoké. Analyzováno v bitech, pole přípony vyžaduje ${ displaystyle { mathcal {O}} (n log n)}$ mezeru, zatímco původní text přes abecedu velikosti ${ displaystyle sigma}$ vyžaduje pouze ${ displaystyle { mathcal {O}} (n log sigma)}$ bitů. Pro lidský genom s ${ displaystyle sigma = 4}$ a ${ displaystyle n = 3,4 krát 10 ^ {9}}$ pole přípon by proto zabíralo asi 16krát více paměti než samotný genom.

Tyto nesrovnalosti motivovaly trend směrem k komprimovaná pole přípon a BWT - komprimované fulltextové indexy na bázi, jako je FM index. Tyto datové struktury vyžadují pouze prostor o velikosti textu nebo dokonce menší.

Konstrukční algoritmy

Lze zabudovat strom přípon ${ displaystyle { mathcal {O}} (n)}$ a lze jej převést na pole přípon pomocí procházení hloubkou stromu nejprve také v ${ displaystyle { mathcal {O}} (n)}$, takže existují algoritmy, které dokážou vytvořit pole přípon ${ displaystyle { mathcal {O}} (n)}$.

Naivní přístup ke konstrukci pole přípon je použití a srovnávací algoritmus třídění. Tyto algoritmy vyžadují ${ displaystyle { mathcal {O}} (n log n)}$ srovnání přípon, ale porovnání přípon běží ${ displaystyle { mathcal {O}} (n)}$ čas, takže celková doba běhu tohoto přístupu je ${ displaystyle { mathcal {O}} (n ^ {2} log n)}$.

Pokročilejší algoritmy využívají výhody toho, že přípony, které mají být tříděny, nejsou libovolné řetězce, ale navzájem souvisí. Tyto algoritmy se snaží dosáhnout následujících cílů:^[7]

• minimální asymptotická složitost ${ displaystyle Theta (n)}$
• lehký v prostoru, což znamená, že vedle textu a samotné pole přípony je potřeba malá nebo žádná pracovní paměť
• rychle v praxi

Jedním z prvních algoritmů k dosažení všech cílů je algoritmus SA-IS Nong, Zhang & Chan (2009). Algoritmus je také poměrně jednoduchý (<100 LOC ) a lze je vylepšit tak, aby současně postavily LCP pole.^[8] Algoritmus SA-IS je jedním z nejrychleji známých algoritmů pro konstrukci pole přípon. Opatrně implementace Yuta Mori překonává většinu ostatních lineárních nebo superlineárních konstrukčních přístupů.

Kromě požadavků na čas a prostor se algoritmy pro konstrukci pole přípon liší také podle jejich podporovaných abeceda: konstantní abecedy kde je velikost abecedy vázána konstantou, celočíselné abecedy kde znaky jsou celá čísla v rozsahu v závislosti na ${ displaystyle n}$ a obecné abecedy kde jsou povolena pouze srovnání znaků.^[9]

Většina algoritmů pro konstrukci pole přípon je založena na jednom z následujících přístupů:^[7]

• Zdvojení předpony algoritmy jsou založeny na strategii Karp, Miller & Rosenberg (1972). Cílem je najít předpony, které respektují lexikografické řazení přípon. Posuzovaná délka předpony se zdvojnásobuje v každé iteraci algoritmu, dokud není předpona jedinečná a poskytuje hodnost přidružené přípony.
• Rekurzivní Algoritmy sledují přístup algoritmu konstrukce stromu přípon pomocí Farach (1997) rekurzivně třídit podmnožinu přípon. Tato podmnožina se poté používá k odvození pole přípon zbývajících přípon. Obě tato pole přípon jsou poté sloučena za účelem výpočtu výsledného pole přípony.
• Indukované kopírování algoritmy jsou podobné rekurzivním algoritmům v tom smyslu, že používají již seřazenou podmnožinu k vyvolání rychlého druhu zbývajících přípon. Rozdíl je v tom, že tyto algoritmy upřednostňují iteraci před rekurzí za účelem seřazení vybrané podmnožiny přípon. Průzkum této různorodé skupiny algoritmů sestavil Puglisi, Smyth & Turpin (2007).

Známým rekurzivním algoritmem pro celočíselné abecedy je DC3 / šikmo algoritmus Kärkkäinen & Sanders (2003). Běží v lineárním čase a úspěšně se používá jako základ pro paralelní provoz^[10] a externí paměť^[11] algoritmy konstrukce příponového pole.

Poslední práce od Salson a kol. (2010) navrhuje algoritmus pro aktualizaci pole přípony textu, který byl upraven, místo opětovného sestavení nového pole přípony od začátku. I když teoretická nejhorší časová složitost je ${ displaystyle { mathcal {O}} (n log n)}$, zdá se, že funguje dobře v praxi: experimentální výsledky autorů ukázaly, že jejich implementace polí dynamické přípony je obecně efektivnější než opětovné sestavení, když se uvažuje o vložení přiměřeného počtu písmen do původního textu.

V praxi otevřený zdroj práce, běžně používanou rutinou pro konstrukci pole přípon byl qsufsort, založený na algoritmu Larsson-Sadakane z roku 1999.^[12] Tato rutina byla nahrazena programem DivSufSort od Yuty Mori, „nejrychlejšího známého algoritmu třídění přípon v hlavní paměti“ od roku 2017. Také jej lze upravit tak, aby počítal pole LCP. Používá indukované kopírování v kombinaci s Itoh-Tanaka.^[13]

Aplikace

Pole přípony řetězce lze použít jako index rychle najít každý výskyt podřetězcového vzoru ${ displaystyle P}$ uvnitř řetězce ${ displaystyle S}$. Nalezení každého výskytu vzoru je ekvivalentní nalezení každé přípony, která začíná podřetězcem. Díky lexikografickému uspořádání budou tyto přípony seskupeny do pole přípon a lze je efektivně najít pomocí dvou binární vyhledávání. První vyhledávání vyhledá počáteční pozici intervalu a druhé určuje koncovou pozici:^{[Citace je zapotřebí ]}

n = len(S)def Vyhledávání(P: str) -> Tuple[int, int]:    """    Vrátit indexy (s, r) tak, aby interval A [s: r] (včetně konce    index) představuje všechny přípony S, které začínají vzorem P.    """    # Najít počáteční pozici intervalu    l = 0  # v Pythonu jsou pole indexována od 0    r = n    zatímco l < r:        střední = (l + r) // 2  # rozdělení zaokrouhleno dolů na nejbližší celé číslo        # suffixAt (A [i]) je i-tou nejmenší příponou        -li P > přípona(A[střední]):            l = střední + 1        jiný:            r = střední    s = l        # Najít koncovou pozici intervalu    r = n    zatímco l < r:        střední = (l + r) // 2        -li přípona(A[střední]).začíná s(P):            l = střední + 1        jiný:            r = střední    vrátit se (s, r)

Hledání vzoru podřetězce ${ displaystyle P}$ délky ${ displaystyle m}$ v řetězci ${ displaystyle S}$ délky ${ displaystyle n}$ bere ${ displaystyle { mathcal {O}} (m log n)}$ čas, vzhledem k tomu, že je třeba porovnat jednu příponu srovnání ${ displaystyle m}$ postavy. Manber & Myers (1990) popište, jak lze tuto vazbu vylepšit ${ displaystyle { mathcal {O}} (m + log n)}$ čas pomocí LCP informace. Myšlenka spočívá v tom, že porovnávání vzorů nemusí znovu porovnávat určité znaky, když je již známo, že jsou součástí nejdelší společné předpony vzoru a aktuálního intervalu vyhledávání. Abouelhoda, Kurtz & Ohlebusch (2004) chyba harvtxt: více cílů (2 ×): CITEREFAbouelhodaKurtzOhlebusch2004 (Pomoc) vylepšit vázané ještě dále a dosáhnout doby hledání ${ displaystyle { mathcal {O}} (m)}$ jak je známo z stromy přípon.

K výpočtu lze použít algoritmy třídění podle přípon Burrows – Wheelerova transformace (BWT). The BWT vyžaduje třídění všech cyklických permutací řetězce. Pokud tento řetězec končí zvláštním znakem na konci řetězce, který je lexikograficky menší než všechny ostatní znaky (tj. $), Pak se pořadí seřazeného otočí BWT matice odpovídá pořadí přípon v poli přípon. The BWT lze tedy vypočítat v lineárním čase tak, že nejprve sestrojíme pole přípony textu a poté odvodíme BWT tětiva: ${ displaystyle BWT [i] = S [A [i] -1]}$.

Pole přípon lze také použít k vyhledání podřetězců v příkladový strojový překlad, které vyžadují mnohem méně úložného prostoru než plné frázová tabulka jak se používá v Statistický strojový překlad.

Mnoho dalších aplikací pole přípon vyžaduje LCP pole. Některé z nich jsou podrobně uvedeny v dokumentu aplikační sekce toho druhého.

Poznámky

Reference

• Manber, Udi; Myers, Gene (1990). Pole přípon: nová metoda pro vyhledávání řetězců online. První výroční sympozium ACM-SIAM o diskrétních algoritmech. 319–327.CS1 maint: ref = harv (odkaz)
• Manber, Udi; Myers, Gene (1993). „Pole přípon: nová metoda pro vyhledávání řetězců online“. SIAM Journal on Computing. 22 (5): 935–948. doi:10.1137/0222058. S2CID  5074629.CS1 maint: ref = harv (odkaz)
• Li, Zhize; Li, Jian; Huo, Hongwei (2016). Optimální třídění přípon na místě. Sborník z 25. mezinárodního sympozia o zpracování řetězců a vyhledávání informací (SPIRE). Přednášky z informatiky. 11147. Springer. 268–284. arXiv:1610.08305. doi:10.1007/978-3-030-00479-8_22. ISBN  978-3-030-00478-1.CS1 maint: ref = harv (odkaz)
• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). "Nahrazování stromů přípon příponami rozšířených polí přípon". Journal of Discrete Algorithms. 2 (1): 53–86. doi:10.1016 / S1570-8667 (03) 00065-0.CS1 maint: ref = harv (odkaz)
• Gonnet, G.H; Baeza-Yates, R.A; Snider, T (1992). "Nové indexy pro text: PAT stromy a PAT pole". Načítání informací: Datové struktury a algoritmy.CS1 maint: ref = harv (odkaz)
• Kurtz, S (1999). Msgstr "Snížení požadavku na prostor stromů přípon". Softwarová praxe a zkušenosti. 29 (13): 1149–1171. doi:10.1002 / (SICI) 1097-024X (199911) 29:13 <1149 :: AID-SPE274> 3.0.CO; 2-O. hdl:10338.dmlcz / 135448.CS1 maint: ref = harv (odkaz)
• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). Vylepšené pole přípon a jeho aplikace pro analýzu genomu. Algoritmy v bioinformatice. Přednášky z informatiky. 2452. str. 449. doi:10.1007/3-540-45784-4_35. ISBN  978-3-540-44211-0.CS1 maint: ref = harv (odkaz)
• Puglisi, Simon J .; Smyth, W. F .; Turpin, Andrew H. (2007). "Taxonomie konstrukčních algoritmů příponových polí". ACM Computing Surveys. 39 (2): 4. doi:10.1145/1242471.1242472. S2CID  2653529.CS1 maint: ref = harv (odkaz)
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Konstrukce lineárního pole přípony téměř čistým indukovaným tříděním. Konference o kompresi dat 2009. str. 193. doi:10.1109 / DCC.2009.42. ISBN  978-0-7695-3592-0.CS1 maint: ref = harv (odkaz)
• Fischer, Johannes (2011). Indukce LCP-pole. Algoritmy a datové struktury. Přednášky z informatiky. 6844. str. 374. arXiv:1101.3448. doi:10.1007/978-3-642-22300-6_32. ISBN  978-3-642-22299-3.CS1 maint: ref = harv (odkaz)
• Salson, M .; Lecroq, T .; Léonard, M .; Mouchard, L. (2010). "Pole dynamické rozšířené přípony". Journal of Discrete Algorithms. 8 (2): 241. doi:10.1016 / j.jda.2009.02.007.CS1 maint: ref = harv (odkaz)
• Burkhardt, Stefan; Kärkkäinen, Juha (2003). Rychlá a lehká konstrukce pole přípony a kontrola. Kombinatorické porovnávání vzorů. Přednášky z informatiky. 2676. str. 55. doi:10.1007/3-540-44888-8_5. ISBN  978-3-540-40311-1.CS1 maint: ref = harv (odkaz)
• Karp, Richard M .; Miller, Raymond E .; Rosenberg, Arnold L. (1972). Rychlá identifikace opakovaných vzorů v řetězcích, stromech a polích. Sborník ze čtvrtého ročníku sympozia ACM o teorii práce s počítači - STOC '72. str. 125. doi:10.1145/800152.804905.CS1 maint: ref = harv (odkaz)
• Farach, M. (1997). Optimální konstrukce stromu přípon s velkými abecedami. Sborník 38. výroční sympozium o základech informatiky. str. 137. doi:10.1109 / SFCS.1997.646102. ISBN  0-8186-8197-7.CS1 maint: ref = harv (odkaz)
• Kärkkäinen, Juha; Sanders, Peter (2003). Jednoduchá konstrukce pole lineárních pracovních přípon. Automaty, jazyky a programování. Přednášky z informatiky. 2719. str. 943. doi:10.1007/3-540-45061-0_73. ISBN  978-3-540-40493-4.CS1 maint: ref = harv (odkaz)
• Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). „Lepší konstrukce pole přípony externí paměti“. Journal of Experimental Algorithmics. 12: 1–24. doi:10.1145/1227161.1402296. S2CID  12296500.CS1 maint: ref = harv (odkaz)
• Kulla, Fabian; Sanders, Peter (2007). "Škálovatelná konstrukce pole paralelních přípon". Parallel Computing. 33 (9): 605. doi:10.1016 / j.parco.2007.06.004.CS1 maint: ref = harv (odkaz)

externí odkazy

• Příponové pole v Javě
• Přídavný třídicí modul pro BWT v C kódu
• Implementace pole přípon v Ruby
• Knihovna a nástroje s příponou pole
• Projekt obsahující různé implementace Suffix Array c / c ++ s jednotným rozhraním
• Rychlá, lehká a robustní knihovna C API pro konstrukci pole přípon
• Implementace Suffix Array v Pythonu
• Lineární časová přípona Implementace pole v jazyce C pomocí stromu přípon