An Average-Case Analysis of Basic Parameters of the Suffix Tree
J Fayolle · Birkhäuser Basel eBooks · 2004
The LZ’77 algorithm offers one of the best available rates for lossless data compression. It is based on the suffix tree structure. Our aim is to obtain the asymptotics of the mean size and external path length of a suffix tree by comparing them to those of a trie or digital tree. The core problem lies within the set on which we build the suffix tree. This set is correlated , so we cannot use the methods that have proved efficient for the trie. The proof relies on combinatorics , generating functions , and complex analysis . These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.