Sufixový strom

Technology
12 hours ago
8
4
2
Avatar
Author
Albert Flores

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

[url=https://people.ksp.sk/~kuko/gnarley-trees/SuffixTree.html]Vizualizace suffixového stromu[/url]

Kategorie:Stromy (datové struktury)

5 min read
Share this post:
Like it 8

Leave a Comment

Please, enter your name.
Please, provide a valid email address.
Please, enter your comment.
Enjoy this post? Join Cesko.wiki
Don’t forget to share it
Top