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

      0 references
      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
      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

      Identifiers