Huffman-Dateiformat

[LX]

Hallo, Struppi!

Ich habe es eben selbst noch mal korrigiert (siehe unten). er gibt jetzt den Tree für "test" als Hash aus:

{"t":"0","s":"10","e":"11"};

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={},
        Branch={},
        repsort=[],
        c1, c2, l, mix, 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
    console.log(Tree);
};
huffman_enc('test');

Da ich jetzt erst mal auf gzip verzichte, werde ich ein Format wählen, welches zuerst die Länge des Baums (in Byte), dann den Baum, dann die Anzahl der Padding-Bits am Ende und dann die Daten (mit 0er-Bits als Padding) enthält. So ist es am einfachsten und vermutlich auch noch einigermaßen performant.

Gruß, LX