Efficient Implementation of the Generalized Tunstall Code Generation Algorithm
| dc.creator | Baer, Michael B. | |
| dc.date | 2008-09-05 | |
| dc.date | 2009-05-08 | |
| dc.date.accessioned | 2026-07-07T13:12:26Z | |
| dc.date.available | 2026-07-07T13:12:26Z | |
| dc.description | A method is presented for constructing a Tunstall code that is linear time in the number of output items. This is an improvement on the state of the art for non-Bernoulli sources, including Markov sources, which require a (suboptimal) generalization of Tunstall's algorithm proposed by Savari and analytically examined by Tabus and Rissanen. In general, if n is the total number of output leaves across all Tunstall trees, s is the number of trees (states), and D is the number of leaves of each internal node, then this method takes O((1+(log s)/D) n) time and O(n) space. | |
| dc.description | 5 pages, 5 figures, accepted to ISIT 2009 | |
| dc.identifier | https://arxiv.org/abs/0809.0949 | |
| dc.identifier | http://arxiv.org/abs/0809.0949 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/229579 | |
| dc.subject | Information Theory | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | E.4; H.1.1 | |
| dc.title | Efficient Implementation of the Generalized Tunstall Code Generation Algorithm | |
| dc.type | text |