• DocumentCode
    1356022
  • Title

    A dynamic programming algorithm for constructing optimal “1”-ended binary prefix-free codes

  • Author

    Chan, Sze-Lok ; Golin, Mordecai J.

  • Author_Institution
    Dept. of Comput. Sci., Hong Kong Univ., Hong Kong
  • Volume
    46
  • Issue
    4
  • fYear
    2000
  • fDate
    7/1/2000 12:00:00 AM
  • Firstpage
    1637
  • Lastpage
    1644
  • Abstract
    The generic Huffman-encoding problem of finding a minimum cost prefix free code is almost completely understood. There still exist many variants of this problem which are not as well understood, though. One such variant, requiring that each of the codewords ends with “1”, has previously been introduced in the literature with the best algorithms known for finding such codes running in exponential time. We develop a simple O(n3) time algorithm for solving the problem
  • Keywords
    Huffman codes; binary codes; computational complexity; dynamic programming; trees (mathematics); codewords; dynamic programming algorithm; exponential time algorithms; generic Huffman-encoding problem; minimum cost prefix free code; optimal 1-ended binary prefix-free codes; Automatic testing; Computer science; Cost function; Cryptography; Dynamic programming; Entropy; Heuristic algorithms; Probability distribution;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/18.850708
  • Filename
    850708
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1356022