Sufixový strom

Sufixový strom je speciální druh trie, která uchovává všechny sufixy (podřetězce od nějakého znaku až do konce) nějakého řetězce. Každý vnitřní vrchol odpovídá prefixu nějakého sufixu, tedy nějakému podslovu.

Je-li tato trie komprimovaná (cesty ve stromu jsou nahrazeny hranou), dá se reprezentovat v prostoru lineárním k délce řetězce. Existují algoritmy pro postavení sufixového stromu v lineárním čase.

Sufixový strom umožňuje rychle řešit řadu řetězcových úloh, například inverzní vyhledávání, hledání nejdelšího opakujícího se podslova nebo Burrowsovu-Wheelerovu transformaci.

Externí odkazy

Pahýl
Pahýl
 Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.
Stromové datové struktury
Vyhledávací stromy
(dynamické množiny/ asociativní pole)

2–3 • 2–3–4 • AA • (a,b) • AVL • B • B+ • B* • Bx • (Optimální) Binární vyhledávací • Dancing • HTree • Intervalový • Stromy s pořadím (Order statistic) • (Doleva převážený) Červeno-černý • Scapegoat • Splay • T • Treap • UB • Váhově vyvážený (tj. BB[α])

Haldy

Binární • Binomiální • Brodal • Fibonacciho • Leftist • Pairing • Skew • Van Emde Boasův strom • Slabá

Trie

Ctrie • C-trie • Hašovací • Komprimovaná trie (tj. Patricia) • Sufixový (tj. PAT) • Ternální hledání • X-fast • Y-fast

Prostorové indexační stromy

Ball • BK • BSP • Kartézský • Hilbertův R • k-d (implicitní k-d) • M • Metrický • MVP • Oktálový (Octree) • PH • Prioritní R • Čtyřstrom (Quadtree) • R • R+ • R* • Segmentový • VP (vantage-point) • X

Jiné stromy

Strom pokrytí • Obousměrně provázaný (Doubly chained tree) • Exponenciální • Fenwickův • (Binární) Strom s prstem • Fraktálový indexový • Fúzní (Fusion tree) • Hašovací kalendář • iDistance • K-ární • Knuthův transformovaný (Left-child right-sibling binary tree) • Link/cut • Log-strukturovaný spojovací • Hašový Merkleův (TTH) • PQ • Rozsahový (Range) • SPQR • Top (Horní strom)

Kategorie:Stromy (dat. strukt.)