Premium
Decoding prefix codes
Author(s) -
Liddell Mike,
Moffat Alistair
Publication year - 2006
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.741
Subject(s) - huffman coding , decoding methods , computer science , prefix code , redundancy (engineering) , canonical huffman code , prefix , algorithm , list decoding , coding (social sciences) , arithmetic , data compression , theoretical computer science , concatenated error correction code , block code , mathematics , code rate , statistics , systematic code , operating system , linguistics , philosophy
Minimum‐redundancy prefix codes have been a mainstay of research and commercial compression systems since their discovery by David Huffman more than 50 years ago. In this experimental evaluation we compare techniques for decoding minimum‐redundancy codes, and quantify the relative benefits of recently developed restricted codes that are designed to accelerate the decoding process. We find that table‐based decoding techniques offer fast operation, provided that the size of the table is kept relatively small, and that approximate coding techniques can offer higher decoding rates than Huffman codes with varying degrees of loss of compression effectiveness. Copyright © 2006 John Wiley & Sons, Ltd.