Huffman-Dateiformat

[LX]

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

[Blubb]

Hallo,

Leider habe ich bisher keine einfach verständlichen Informationen darüber gefunden, auf welche Weise die Daten gespeichert werden - gibt es einen Header?

Der Huffman-Algorithmus heißt Algorithmus, weil es ein Verfahren beschreibt - nicht die konkrete Implementation oder Umsetzung.

Wie werden Baum und komprimierten Daten getrennt? Wird das Ende über eine absolute/relative Längenangabe oder ein Endzeichen markiert?

Das darfst du selbst bestimmen und keiner wird böse sein. Als "best practise" würde ich dir ASN.1 empfehlen.

Grüße

[LX]

Wie werden Baum und komprimierten Daten getrennt? Wird das Ende über eine absolute/relative Längenangabe oder ein Endzeichen markiert?
Das darfst du selbst bestimmen und keiner wird böse sein. Als "best practise" würde ich dir ASN.1 empfehlen.

Danke für die Empfehlung. Hast Du vielleicht auch eine Ahnung, wie es in deflate/gzip/zlib gehandhabt wird?

Gruß, LX

[Blubb]

Hallo,

Danke für die Empfehlung. Hast Du vielleicht auch eine Ahnung, wie es in deflate/gzip/zlib gehandhabt wird?

nein, hatte ich bis eben nicht. Aber nachdem ich mir den Sourcecode angesehen habe weiß ich es ;-) (Tipp: unzip.c)

Sourcecode von GZIP

Grüße

[Struppi]

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

Anscheinend haben das schon andere probiert: http://rumkin.com/tools/compression/compress_huff.php

und zip gibt's auch http://de.w3support.net/index.php?db=so&id=294297

oder hier

Struppi.

[LX]

Hi, Struppi!

Einen LZW(de)compressor habe ich bereits geschrieben, allerdings habe ich es mir nicht so unnötig schwer dabei gemacht.

Huffman/LZ77 ist dabei aber schon eine etwas andere Herausforderung.

Gruß, LX

[Struppi]

Einen LZW(de)compressor habe ich bereits geschrieben, allerdings habe ich es mir nicht so unnötig schwer dabei gemacht.

Ich hatte mir das nicht im Detail angeschaut. Aber bei deinem Code fehlt auch noch was, er bricht bei mir mit einer Fehlermeldung ab.

Fehler: Branch is not defined
Quelldatei: http://localhost/javascript/tmp.html
Zeile: 47

Aber auf den ersten Blick, sieht die Lösung in dem Stackoverflow thread auch nicht umständlicher aus als dein Ansatz.

Huffman/LZ77 ist dabei aber schon eine etwas andere Herausforderung.

http://blog.java2script.org/2006/09/03/lz77-javascript-compressor-reloaded/

Struppi.

[LX]

Hi!

Ich hatte mir das nicht im Detail angeschaut. Aber bei deinem Code fehlt auch noch was, er bricht bei mir mit einer Fehlermeldung ab.

Fehler: Branch is not defined
Quelldatei: http://localhost/javascript/tmp.html
Zeile: 47

Das war ein Tippfehler; ich hatte kürzere Namen verlängert, damit sie aufschlussreicher werden, leider hatte ich oben "Branches" und unten "Branch" geschrieben; wenn Du diese Inkohärenz korrigierst, sollte der Code funktionieren.

Gruß, LX

[Struppi]

Ich hatte mir das nicht im Detail angeschaut. Aber bei deinem Code fehlt auch noch was, er bricht bei mir mit einer Fehlermeldung ab.

Fehler: Branch is not defined
Quelldatei: http://localhost/javascript/tmp.html
Zeile: 47

Das war ein Tippfehler; ich hatte kürzere Namen verlängert, damit sie aufschlussreicher werden, leider hatte ich oben "Branches" und unten "Branch" geschrieben; wenn Du diese Inkohärenz korrigierst, sollte der Code funktionieren.

Dann kommt:
Fehler: mix is not defined
Quelldatei: http://localhost/javascript/tmp.html
Zeile: 47

Wenn ich aus dem m ein mix mache kommt:
Fehler: Dict is undefined
Quelldatei: http://localhost/javascript/tmp.html
Zeile: 39

Struppi.

[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

[Struppi]

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

Bei mir nicht:
Fehler: Dict is undefined
Quelldatei: http://localhost/javascript/tmp.html
Zeile: 41

Das ist bei mir Zeile 41

if (!Dict[c]) {

Struppi.

[Struppi]

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

Bei mir nicht:

Weil ich statt 'test' 'aaaa' probiert habe, dann kommt die von mir genannte Fehlermeldung. Deine Funktion braucht anscheinend mindestens zwei unterschiedliche Buchstaben.

Struppi.

[LX]

Stimmt. Ich habe aber bereits festgestellt, dass die Bäume nicht so ausbalanciert werden, dass eine Kompression stattfinden kann. Nachdem ich dieses Problem dadurch behoben habe, dass ich dem Bewertungshash die zusätzlichen Zusammenstellungen wieder eingefügt und das Array jedes Mal neu sortiert habe, habe ich nun das Problem, dass viele der Bitersetzungen mit 0 anfangen - was jedoch zu Problemen bei der Speicherung der Bäume führt; 0 sollte für das häufigste Zeichen reserviert sein und alle anderen mit 1 anfangen. Dieses Problem werde ich jetzt beheben, indem ich das am meisten auftauchende Zeichen als erstes auf das 0-byte codiere und dann erst alle anderen Zeichen. Ich halte Euch auf dem Laufenden. Das ganze könnte möglicherweise für den nächsten js1k-Wettbewerb interessant werden - oder für die effiziente Speicherung größerer Datenmengen in localStorage.

Gruß, LX

[LX]

Hallo!

Ich habe den Codec jetzt unter http://tinyjs.sf.net/tiny-huffman-de.html ins Netz gestellt. Er ist im ungepackten Source relativ gut kommentiert, so dass er hoffentlich verständlich ist.

Gruß, LX