Wyszukiwarka
Abstrakt
In a recently proposed graphical compression algorithm by Choi and Szpankowski (2012), the following tree arose in the course of the analysis. The root contains n balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability p) or the right subtree (with probability 1p). A new node is created as long as there is at least one ball in that node. Furthermore, a nonnegative integer d is given, and at level d or greater one ball is removed from the leftmost node before the balls move down to the next level. These steps are repeated until all balls are removed (i.e., after n + d steps). Observe that when d = 1 the above tree can be modeled as a trie that stores n independent sequences generated by a binary memoryless source with parameter p. Therefore, we coin the name (n; d)-tries for the tree just described, and to which we often refer simply as d-tries. We study here in detail the path length, and show how much the path length of such a d-trie diers from that of regular tries. We use methods of analytic algorithmics, from Mellin transforms to analytic poissonization.
Autorzy (3)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
ELECTRONIC JOURNAL OF COMBINATORICS
nr 19,
strony 1 - 22,
ISSN: 1077-8926 - Język:
- angielski
- Rok wydania:
- 2012
- Opis bibliograficzny:
- Choi Y., Knessl C., Szpankowski W.: On a Recurrence Arising in Graph Compression// ELECTRONIC JOURNAL OF COMBINATORICS. -Vol. 19, iss. 3 (2012), s.1-22
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 46 razy