Uncommon suffix tries

DOI10.1002/RSA.20500zbMATH Open1320.68057arXiv1112.4131OpenAlexW1980038196MaRDI QIDQ5175232FDOQ5175232

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)

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.

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

Recommendations

• Average size of a suffix tree for Markov sources
• scientific article
• 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

zbMATH Keywords

suffix treemixing propertiesprefix treevariable-length Markov chainprobabilistic sourcesuffix trie

Mathematics Subject Classification ID

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

Cites Work

• Mixing: Properties and examples
• Algorithms on Strings, Trees and Sequences
• Title not available (Why is that?)
• Dynamical sources in information theory: A general analysis of trie structures
• 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
• Asymptotical growth of a class of random trees
• Renewal sequences and intermittency
• Asymptotic properties of data compression and suffix trees
• Entropy and prefixes
• Random perturbations of stochastic processes with unbounded variable length memory
• On the height of digital trees and related problems
• Context trees, variable length Markov chains and dynamical sources

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)