In this paper, we propose a greedy technique for adaptive Fano coding, which is suitable for a wide range of applications, specially those in which memory constraints are tight. Our scheme has great potential in maximizing the output entropy, and thus has also indirect cryptographic implications. This paper includes the encoding and decoding algorithms, and the partitioning procedures suitable for the binary and r-ary schemes. It also includes a rigorous analysis of the properties of the algorithm. Empirical results demonstrate that our adaptive Fano scheme compresses marginally less than the adaptive Huffman scheme. In terms of speed, the former is faster in the compression phase and slower in the decompression phase. We also present the extension of the binary adaptive Fano coding method to multi-symbol code alphabets. We introduce the corresponding partitioning procedure, which deals with consecutive partitionings that satisfy the principles of Fano coding. To find the optimal partitioning, we propose a brute force algorithm that searches the entire space of all possible partitionings in O(m/sup r-1/) time. As opposed to this, we propose a greedy linear-time algorithm that finds a sub-optimal but accurate consecutive partitioning.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Greedy adaptive Fano coding


    Contributors:
    Rueda, L.G. (author) / Oommen, B.J. (author)


    Publication date :

    2002-01-01


    Size :

    815211 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    10.0407 Greedy Adaptive Fano Coding

    Institute of Electrical and Electronics Engineers | British Library Conference Proceedings | 2002



    Explorer gets greedy

    Online Contents | 2005



    Routenoptimierung mit Greedy-Algorithmen

    Hillert, Freimut | SLUB | 1992