A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors

DOI10.1137/0222070zbMath0799.68050OpenAlexW2088116326MaRDI QIDQ4277536

Wojciech Szpankowski

Publication date: 7 February 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/3f51667b3ec8263d2af414abe72dfb8e54b89128

zbMATH Keywords

heightshortest pathdata compressionmixing conditionprobabilistic modelsRényi entropyalgorithms on wordsgeneralized suffix treestypical depth insertion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Discrete mathematics in relation to computer science (68R99)

Related Items (15)

Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach ⋮ On the construction of classes of suffix trees for square matrices: Algorithms and applications ⋮ Context Trees, Variable Length Markov Chains and Dynamical Sources ⋮ Return-time -spectrum for equilibrium states with potentials of summable variation ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ The longest common substring problem ⋮ On the entropy of a hidden Markov process ⋮ Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees ⋮ Probabilistic modeling of data structures on words. A reply to Professor Andersson's letter ⋮ Spaces, Trees, and Colors ⋮ On average sequence complexity ⋮ Optimal data compression algorithm ⋮ Universal Data Compression Algorithm Based on Approximate String Matching ⋮ Faster entropy-bounded compressed suffix trees ⋮ Practical Compact Indexes for Top-kDocument Retrieval

This page was built for publication: A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors