LX: Huffman-Dateiformat

Beitrag lesen

Hallo! Ich schreibe gerade als Fingerübung einen einfachen Huffman-(De)kompressor in Javascript. Die Bäume zu bauen, war eine relativ einfache Übung; auch die Übersetzung in die Bitfolgen ist einfach genug - aber genug der langen Worte, ich zeige Euch einfach mal den bisherigen Code:

huffman_enc=function(data){  
    // Dict=Frequency dictionary, Tree=tree, Branches=Branches, repsort=for first sort after repetition, c1/c2=Character register, l=length counter, mix=mix register, f=recursive function  
    var Dict={},  
        Tree={},  
        Branches={},  
        repsort=[],  
        c1, c2, l, m, r;  
    // build dictionary (D) and key table for sort order  
    data.replace(/./g, function(c) {  
        if (!Dict[c]) {  
            repsort.push(c);  
            Dict[c]=1;  
        } else {  
            Dict[c]++;  
        }  
    });  
    // sort order table  
    repsort.sort(function(x,y) { return Dict[x]-Dict[y]; });  
        // create Tree, 1st step  
    while ((c1=repsort.shift()) && (c2=repsort.shift())) {  
        Branch[mix=c1+(c2||'')]=[c2.length>1 ? Branch[c2] : c2, c1.length>1 ? Branch[c1] : c1];  
        // trick: put elements back until there is only one of them left  
        repsort.unshift(mix);  
    }  
    // create Tree recursively, 2nd step  
    (r=function(Dict, mix) {  
        l=-1;  
        while (++l < 2) {  
            if (Dict[l]) {  
                if (typeof Dict[l]=='string') {  
                    Tree[Dict[l]]=mix+l;  
                } else {  
                    r(Dict[l],mix+l);  
                }  
            };  
        }  
    })(Branch[mix], '');  
    // now Tree contains each character and its binary representation as string.  
    // TODO: convert data, put stuff together  
};

Leider habe ich bisher keine einfach verständlichen Informationen darüber gefunden, auf welche Weise die Daten gespeichert werden - gibt es einen Header? Wie werden Baum und komprimierten Daten getrennt? Wird das Ende über eine absolute/relative Längenangabe oder ein Endzeichen markiert?

Das Ziel ist im Endeffekt ein komplettes deflate (gzip) in JavaScript. Sobald ich den Hoffman-Codec habe, nehme ich mir LZ77 vor.

Gruß, LX

--
RFC 2324, Satz 7 (Sicherheit): Jeder, der zwischen meinem Kaffee und mir steht, gilt als unsicher.