Average Size of a Suffix Tree for Markov Sources - Publikacja - MOST Wiedzy

Wyszukiwarka

Average Size of a Suffix Tree for Markov Sources

Abstrakt

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

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Aktywność konferencyjna
Typ:
publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
Tytuł wydania:
27th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA'16 strony 1 - 13
Język:
angielski
Rok wydania:
2016
Opis bibliograficzny:
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
Weryfikacja:
Politechnika Gdańska

wyświetlono 20 razy

Publikacje, które mogą cię zainteresować

Meta Tagi