Correspondences between variable length parsing and coding problems
In variable-length-to-black binary source coding, a parse tree is used to associate a string of binary source symbols with each of a set of \(K\) code symbols. A parse tree is a complete binary tree with \(K\) leaf nodes and \(K-1\) internal nodes. A path through the parse tree from the root to a leaf describes the string of source symbols associated with the code symbol at the leaf. Previous work considered the parsing problem in which the tree is to be constructed to minimize the discrimination function \(\min_P D_t (P \parallel Q) = -\sum p_i \log_t (p_i /q_i)\) where \(P\) and \(Q\) are two probability distributions of \(K\) symbols, and where \(t\in (0,1)\) is the base of the logarithm. It is shown that the algorithm used in that work corresponds to a previous algorithm of Karp for variable length coding with unequal costs for arbitrary source distributions. The interpretation of various other source coding algorithms (including Tunstall, dyadic, Lempel, Even and Cohen, Huffman and Varn) as minimization algorithms for various functionals is discussed. For the entire collection see [Zbl 0909.00053].
- Code and parse trees for lossless source encoding
- Variable-to-fixed length codes and the conservation of entropy
- A Note on Approximation of Uniform Distributions From Variable-to-Fixed Length Codes
- Variable-length unequal cost parsing and coding for shaping
- scientific article; zbMATH DE number 3557667
- Code and parse trees for lossless source encoding
- A Note on Approximation of Uniform Distributions From Variable-to-Fixed Length Codes
- Optimal Parsing Trees for Run-Length Coding of Biased Data
- On the AEP of word-valued sources
- Variable-length unequal cost parsing and coding for shaping
- Multidimensional Incremental Parsing for Universal Source Coding
- Bidirectional grammars for machine-code decoding and encoding
This page was built for publication: Correspondences between variable length parsing and coding problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247210)
