Uncommon suffix tries

DOI10.1002/rsa.20500zbMath1320.68057arXiv1112.4131OpenAlexW1980038196MaRDI QIDQ5175232

Brigitte Chauvin, Nicolas Pouyanne, Peggy Cénac, Frederic Paccaut

Publication date: 20 February 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.4131

zbMATH Keywords

suffix treemixing propertiesprefix treevariable-length Markov chainprobabilistic sourcesuffix trie

Mathematics Subject Classification ID

Discrete-time Markov processes on general state spaces (60J05) Data structures (68P05)

Related Items

Towards a realistic analysis of the QuickSelect algorithm

Cites Work

• Unnamed Item
• On the height of digital trees and related problems
• Random perturbations of stochastic processes with unbounded variable length memory
• Asymptotical growth of a class of random trees
• Entropy and prefixes
• Mixing: Properties and examples
• Dynamical sources in information theory: A general analysis of trie structures
• Renewal sequences and intermittency
• Context Trees, Variable Length Markov Chains and Dynamical Sources
• Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression
• A universal data compression system
• A Note on the Height of Suffix Trees
• Algorithms on Strings, Trees and Sequences
• Asymptotic properties of data compression and suffix trees