Uncommon Suffix Tries

作者：Cenac Peggy; Chauvin Brigitte; Paccaut Frederic; Pouyanne Nicolas^*

来源：Random Structures and Algorithms, 2015, 46(1): 117-141.

DOI：10.1002/rsa.20500

• variable length Markov chain
• probabilistic source
• mixing properties
• prefix tree
• suffix tree
• suffix trie

Common assumptions on the source producing the words inserted in a suffix trie with n leaves lead to a lnn 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 lnn. Both are built from VLMC (Variable Length Markov Chain) probabilistic sources and are easily extended to families of tries 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.

• 出版日期2015-1