Average Size of a Suffix Tree for Markov Sources

Philippe Jacquet; Wojciech Szpankowski

Average Size of a Suffix Tree for Markov Sources

Abstract

We study a suffix tree built from a sequence generated by a Markovian source. Such sources are more realistic probabilistic models for text generation, data compression, molecular applications, and so forth. We prove that the average size of such a suffix tree is asymptotically equivalent to the average size of a trie built over n independentsequences from the same Markovian source. This equivalenceis only known for memoryless sources. We then derive a formula for the size of a trie under Markovian model to complete the analysis for suffix trees. We accomplish our goal by applying some novel techniques of analytic combinatorics on words also known as analytic pattern matching

Authors (2)

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

SUFFIX TREE, MARKOV SOURCES, DIGITAL TREES

Details

Category:: Conference activity
Type:: publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Title of issue:: 27th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA'16 strony 1 - 13
Language:: English
Publication year:: 2016
Bibliographic description:: Jacquet P., Szpankowski W.: Average Size of a Suffix Tree for Markov Sources// 27th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA'16 / ed. Ralph Neininger, Marek Zaione Kraków: , 2016, s.1-13
Verified by:: Gdańsk University of Technology