• DocumentCode
    2684748
  • Title

    A work-efficient parallel algorithm for constructing Huffman codes

  • Author

    Milidiú, Ruy Luiz ; Laber, Eduardo Sany ; Pessoa, Artur Rives

  • Author_Institution
    Dept. de Inf., PUC-Rio, Rio de Janeiro, Brazil
  • fYear
    1999
  • fDate
    29-31 Mar 1999
  • Firstpage
    277
  • Lastpage
    286
  • Abstract
    Given an alphabet Σ={a1,...,an) and a corresponding list of weights [w1,...,wn], a Huffman code for this alphabet is a prefix code that minimizes the weighted length of a code string, defined to be Σi=1 nwili, where li is the length of the code assigned to ai. We present ES-ParHuff, a work-efficient PRAM CREW algorithm for constructing Huffman codes. An important feature of the algorithm is its simplicity. This algorithm is a direct parallelization of Huffman´s algorithm. ES-ParHuff runs in O(Hloglog(n/H)) time with O(n) work, where H is the length of the longest generated code
  • Keywords
    Huffman codes; computational complexity; minimisation; parallel algorithms; ES-ParHuff; Huffman codes; PRAM CREW algorithm; code string; prefix code; running time; weighted length minimization; work-efficient parallel algorithm; Binary trees; Chromium; Huffman coding; Merging; Parallel algorithms; Phase change random access memory;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Data Compression Conference, 1999. Proceedings. DCC '99
  • Conference_Location
    Snowbird, UT
  • ISSN
    1068-0314
  • Print_ISBN
    0-7695-0096-X
  • Type

    conf

  • DOI
    10.1109/DCC.1999.755677
  • Filename
    755677
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2684748