Repozytorium publikacji - Politechnika Gdańska

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

Autorzy

• Philippe Jacquet,
• prof. dr inż. Wojciech Szpankowski link otwiera się w nowej karcie