A fast algorithm for constructing nearly optimal prefix codes | Zendy

Osorio Roberto R. | Zendy; González Patricia | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

A fast algorithm for constructing nearly optimal prefix codes

Author(s) -

Osorio Roberto R.,

González Patricia

Publication year - 2016

Publication title -

software: practice and experience

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.437

H-Index - 70

eISSN - 1097-024X

pISSN - 0038-0644

DOI - 10.1002/spe.2375

Subject(s) - huffman coding , prefix code , computer science , algorithm , prefix , sorting , coding (social sciences) , code (set theory) , fountain code , data compression , focus (optics) , time complexity , theoretical computer science , block code , linear code , mathematics , decoding methods , programming language , linguistics , philosophy , statistics , physics , set (abstract data type) , optics

Summary Huffman algorithm allows for constructing optimal prefix‐codes with O ( n · l o g n ) complexity. As the number of symbols n grows, so does the complexity of building the code‐words. In this paper, a new algorithm and implementation are proposed that achieve nearly optimal coding without sorting the probabilities or building a tree of codes. The complexity is proportional to the maximum code length, making the algorithm especially attractive for large alphabets. The focus is put on achieving almost optimal coding with a fast implementation, suitable for real‐time compression of large volumes of data. A practical case example about checkpoint files compression is presented, providing encouraging results. Copyright © 2015 John Wiley & Sons, Ltd.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research