Wyszukiwarka
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 111 razy
Publikacje, które mogą cię zainteresować
On extremal sizes of locally k-tree graphs
- M. Borowiecki,
- P. Borowiecki,
- E. Sidorowicz
- + 1 autorów