Uncommon Suffix Tries

Details Uncommon Suffix Tries Uncommon Suffix Tries

2011-12-18

arxiv.org/abs/1112.4131v2

Mathematics

Probability

Scientific paper

Common assumptions on the source producing the words inserted in a suffix trie with $n$ leaves lead to a $\log n$ 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 $\log n$. 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.

Affiliated with

Also associated with

No associations

Rating

Uncommon Suffix Tries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Uncommon Suffix Tries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uncommon Suffix Tries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-25799