On the Memory Efficiency and Search time for Huffman Coding Scheme

摘要

Hashemian has proposed a technique to improve the memory efficiency and the symbol search time of the Huffman compression coding scheme. This is achieved by uniform partitioning and clustering of the single-side growing Huffman tree (SGH-tree). In the example given by Hashemian for a 32-symbol source with 13-level SGH-tree, the memory requirement is 126 words and the memory efficiency is only 50%, compared to 2 and 0.39%, respectively, for unstructured memory environment La this paper, the memory efficiency and the search time are further improved by extending the set of decoded symbols; the new added symbols are groups of consecutive single symbols with certain criterion. The extended set of decoded symbols keeps the same structure of the SGH-tree; thus, there is no increase in the memory requirement It is required to modify the decoding procedure, resulting in a change of the contents of the look up tables (LUTs) of the clusters, the super table (ST) of the SGH-tree, and the memory (RAM) table. With this technique, the memory requirement is 120 words and the memory efficiency is 82%. Since the new added symbols are groups of consecutive single symbols, the search time for some symbols is reduced, leading to an improvement in the search time for modified technique.