Correspondences between variable length parsing and coding problems (Q4247210)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1301974
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Correspondences between variable length parsing and coding problems |
scientific article; zbMATH DE number 1301974 |
Statements
10 July 2002
0 references
variable-length-to-block coding
0 references
block-to-variable-length coding
0 references
unequal costs coding
0 references
parse tree
0 references
parsing
0 references
source coding
0 references
0.8294335007667542
0 references
0.7993202209472656
0 references
0.7755080461502075
0 references
0.763936460018158
0 references
Correspondences between variable length parsing and coding problems (English)
0 references
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].
0 references