Analysis of the average depth in a suffix tree under a Markov modelReport as inadecuate

Analysis of the average depth in a suffix tree under a Markov model - Download this document for free, or read online. Document in PDF available to download.

1 ALGORITHMS - Algorithms Inria Paris-Rocquencourt 2 Department of mathematics Purdue University

Abstract : In this report, we prove that under a Markovian model of order one, the average depth of suffix trees of index n is asymptotically similar to the average depth of tries a.k.a. digital trees built on n independent strings. This leads to an asymptotic behavior of $\log{n}-h + C$ for the average of the depth of the suffix tree, where $h$ is the entropy of the Markov model and $C$ is constant. Our proof compares the generating functions for the average depth in tries and in suffix trees; the difference between these generating functions is shown to be asymptotically small. We conclude by using the asymptotic behavior of the average depth in a trie under the Markov model found by Jacquet and Szpankowski JaSz91.

Keywords : asymptotics analytic methods Suffix trees depth average analysis

Author: Julien Fayolle - Mark Daniel Ward -



Related documents