Name
Title | ||
|---|---|---|
Asymptotics of greedy algorithms for variable-to-fixed length coding of Markov sources |
Abstract | ||
|---|---|---|
In this paper, alphabet extension for Markov sources is studied such that each extension tree is grown by splitting the node with the maximum value for a weight as a generalization of the leaf probability in Tunstall's (1967) algorithm. We show that the optimal asymptotic rate of convergence of the per-symbol code length to the entropy does not depend on an a priori selected proportional allocation of the sizes of the extension trees at the states. We show this without imposing restrictive conditions on the weight by which the trees are extended. Further, we prove the asymptotic optimality of an algorithm that allocates an increasing total number of leaves among the states. Finally, we give exact formulas for all the relevant quantities of the trees grown |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1109/TIT.2002.1013141 | Information Theory, IEEE Transactions |
Keywords | Field | DocType |
Markov processes,algorithm theory,convergence of numerical methods,data communication,optimisation,probability,trees (mathematics),variable length codes,Markov sources,Tunstall's algorithm,asymptotic optimality,data compression,entropy,extension tree,fixed-length codeword,greedy algorithms,leaf probability,optimal asymptotic convergence rate,per-symbol code length,text compression algorithm,variable-to-fixed length coding | Discrete mathematics,Combinatorics,Markov process,Markov chain,A priori and a posteriori,Greedy algorithm,Coding (social sciences),Rate of convergence,Asymptotic analysis,Mathematics,Alphabet | Journal |
Volume | Issue | ISSN |
48 | 7 | 0018-9448 |
Citations | PageRank | References |
9 | 0.65 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| I. Tabus | 1 | 87 | 10.32 |
| Jorma Rissanen | 2 | 1665 | 798.14 |