Uncommon suffix tries

DOI10.1002/RSA.20500MaRDI QIDQ5175232zbMATH OpenOpenAlexFDO

Authors Peggy Cénac, Brigitte Chauvin, Frédéric Paccaut, Nicolas Pouyanne

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

mixing propertiesprefix treeprobabilistic sourcesuffix treesuffix trievariable-length Markov chain

Mathematics Subject Classification ID

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

Abstract: Common assumptions on the source producing the words inserted in a suffix trie with $n$ leaves lead to a $logn$ height and saturation level. We provide an example of a suffix trie whose height increases faster than a power of $n$ and another one whose saturation level is negligible with respect to $logn$. Both are built from VLMC (Variable Length Markov Chain) probabilistic sources; they are easily extended to families of sources having the same properties. The first example corresponds to a "logarithmic infinite comb" and enjoys a non uniform polynomial mixing. The second one corresponds to a "factorial infinite comb" for which mixing is uniform and exponential.

Recommendations

• Average size of a suffix tree for Markov sources
• scientific article; zbMATH DE number 177551
• Towards a complete characterization of tries
• Concentration of Size and Path Length of Tries
• Dynamical sources in information theory: A general analysis of trie structures

Cites work

• A Note on the Height of Suffix Trees
• A universal data compression system
• Algorithms on Strings, Trees and Sequences
• Asymptotic properties of data compression and suffix trees
• Asymptotical growth of a class of random trees
• Context trees, variable length Markov chains and dynamical sources
• Dynamical sources in information theory: A general analysis of trie structures
• Entropy and prefixes
• scientific article; zbMATH DE number 1139639 (Why is no real title available?)
• Mixing: Properties and examples
• On the height of digital trees and related problems
• Random perturbations of stochastic processes with unbounded variable length memory
• Renewal sequences and intermittency
• Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression

Cited in

(1)

• Towards a realistic analysis of the QuickSelect algorithm

This page was built for publication: Uncommon suffix tries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175232)