Uncommon Suffix Tries
Affiliation auteurs | Affiliation ok |
Titre | Uncommon Suffix Tries |
Type de publication | Journal Article |
Year of Publication | 2015 |
Auteurs | Cenac P, Chauvin B, Paccaut F, Pouyanne N |
Journal | RANDOM STRUCTURES & ALGORITHMS |
Volume | 46 |
Pagination | 117-141 |
Date Published | JAN |
Type of Article | Article |
ISSN | 1042-9832 |
Mots-clés | mixing properties, prefix tree, probabilistic source, suffix tree, suffix trie, variable length Markov chain |
Résumé | 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. (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 117-141, 2015 |
DOI | 10.1002/rsa.20500 |