Huffman, Kompression



  • Hi,

    ich beschäftige mich momentan mit der Huffman Kompression und das Prinzip dahinter ist mir grundsätzlich klar. Ich habe also einen Eingabetext, zähle die Häufigkeit der enthaltenen Zeichen und erstelle daraus einen Baum. Anschließend nutze ich diesen Baum um den entsprechenden Code zu generieren, der aus 0 und 1 besteht.

    Gut... Aber wenn ich einen solchen Code habe, dann ist dieser doch vieeeel länger als der Ursprungstext. Was mache ich also mit diesem Code? 😕



  • asdasdasd schrieb:

    Gut... Aber wenn ich einen solchen Code habe, dann ist dieser doch vieeeel länger als der Ursprungstext.

    Wie kommst du darauf? Ein Zeichen besteht aus 8 Bits, in der Huffman-Codierung dann aus variabel vielen, aber durchschnittlich (normalerweise) weniger als 8 Bits.



  • Ich habe die 0 und 1 nicht als Binärfolge wahrgenommen und es stattdessen als String verstanden.

    Nun habe ich jedoch ein neues Problem. Beispielsweise habe ich folgenden Code, den ich bereits in Byte-Blöcke aufgeteilt habe

    0001001   1. Byte
    1101100   2. Byte
    1000110   3. Byte
    1111010   4. Byte
    1000101   5. Byte
    111       6. Byte
    

    Beim 6. "Byte" habe ich ein Problem. Wie soll ich diese Folge speichern? Ich komme ja nicht auf 8 Bit. Ich kann es zwar mit Nullen auffüllen, aber beim Auslesen ergibt sich hieraus zwangsläufig ein Problem... Schließlich stellen auch die Nullen etwas dar. Ich kann sie also weder nach belieben hinzufügen, noch nach belieben streichen...

    Wie mache ich es richtig?



  • asdasdasd schrieb:

    Ich habe die 0 und 1 nicht als Binärfolge wahrgenommen und es stattdessen als String verstanden.

    Nun habe ich jedoch ein neues Problem. Beispielsweise habe ich folgenden Code, den ich bereits in Byte-Blöcke aufgeteilt habe

    0001001   1. Byte
    1101100   2. Byte
    1000110   3. Byte
    1111010   4. Byte
    1000101   5. Byte
    111       6. Byte
    

    Beim 6. "Byte" habe ich ein Problem. Wie soll ich diese Folge speichern? Ich komme ja nicht auf 8 Bit. Ich kann es zwar mit Nullen auffüllen, aber beim Auslesen ergibt sich hieraus zwangsläufig ein Problem... Schließlich stellen auch die Nullen etwas dar. Ich kann sie also weder nach belieben hinzufügen, noch nach belieben streichen...

    Wie mache ich es richtig?

    Oh, hab mich verzählt. Aber das Problem bleibt bestehen:

    00010011
    10110010
    00110111
    10101000
    101111[b]??[/b]
    


  • asdasdasd schrieb:

    Schließlich stellen auch die Nullen etwas dar.

    Dann bau Deinen Baum halt so, dass die Nullen eben nichts darstellen (=ein zusätzliches Zeichen, dass 0x vorkommt)



  • asdasdasd schrieb:

    asdasdasd schrieb:

    Ich habe die 0 und 1 nicht als Binärfolge wahrgenommen und es stattdessen als String verstanden.

    Nun habe ich jedoch ein neues Problem. Beispielsweise habe ich folgenden Code, den ich bereits in Byte-Blöcke aufgeteilt habe

    0001001   1. Byte
    1101100   2. Byte
    1000110   3. Byte
    1111010   4. Byte
    1000101   5. Byte
    111       6. Byte
    

    Beim 6. "Byte" habe ich ein Problem. Wie soll ich diese Folge speichern? Ich komme ja nicht auf 8 Bit. Ich kann es zwar mit Nullen auffüllen, aber beim Auslesen ergibt sich hieraus zwangsläufig ein Problem... Schließlich stellen auch die Nullen etwas dar. Ich kann sie also weder nach belieben hinzufügen, noch nach belieben streichen...

    Wie mache ich es richtig?

    Oh, hab mich verzählt. Aber das Problem bleibt bestehen:

    00010011
    10110010
    00110111
    10101000
    101111[b]??[/b]
    

    Das ist kein problem. Du schreibst halt nur 6 Bits anstatt ein volles Byte. Das ist doch der Witz an der Sache.



  • Hi,

    man speichert zusätzlich zum Bit-Datenstrom auch die Anzahl der unkomprimierten Bytes und hört beim dekomprimieren einfach auf wenn man diese Anzahl erreicht hat. Auffüllen kannst Du mit was immer Du willst, es wird beim dekomprimieren ja ignoriert.

    Speicherst Du eine kompakte Variante des Baums mit ab, um die Original-Daten korrekt dekomprimieren zu können, oder rekonstruierst Du das live, während des dekomprimierens, aus den bereits dekomprimierten Daten?

    Grüße
    Erik



  • Zum Zeitpunkt meines Posts, hatte ich das nur gedanklich durchgespielt, aber nicht programmiert.

    Mein aktueller Versuch, der sehr bescheiden ist, schaut so aus:

    #include <iostream>
    #include <string>
    #include <list>
    
    typedef std::list<class HuffmanNode *> HuffmanNodes;
    
    class HuffmanNode
    {
    	private:
    		bool myIsLeaf;
    		char myChar;
    		int myValue;
    
    		HuffmanNode *myLeft;
    		HuffmanNode *myRight;
    
    	public:
    		HuffmanNode(bool leaf, char ch, int value, HuffmanNode *left = NULL, HuffmanNode *right = NULL) 
    			: myIsLeaf(leaf), myChar(ch), myValue(value), myLeft(left), myRight(right)
    		{
    		}
    
    		~HuffmanNode()
    		{
    			if (myLeft) delete myLeft;
    			if (myRight) delete myRight;
    		}
    
    		void setValue(int val)
    		{
    			myValue = val;
    		}
    
    		void setLeft(HuffmanNode *left)
    		{
    			myLeft = left;
    		}
    
    		void setRight(HuffmanNode *right)
    		{
    			myRight = right;
    		}
    
    		bool isLeaf()
    		{
    			return myIsLeaf;
    		}
    
    		char getChar()
    		{
    			return myChar;
    		}
    
    		int getValue()
    		{
    			return myValue;
    		}
    
    		HuffmanNode *getLeft()
    		{
    			return myLeft;
    		}
    
    		HuffmanNode *getRight()
    		{
    			return myRight;
    		}
    };
    
    class Huffman
    {
    	private:
    		HuffmanNodes myNodes;
    		std::string myInput;
    		std::string myCodeBuf;
    		std::string myValueBuf;
    
    		HuffmanNode *myRoot;
    
    	public:
    		void encode(const std::string& str)
    		{
    			myInput = str;
    
    			for (unsigned int i = 0; i < str.length(); ++i)
    			{
    				bool found = false;
    
    				for (HuffmanNodes::iterator it = myNodes.begin(); it != myNodes.end(); ++it)
    				{
    					if ((*it)->getChar() == str[i])
    					{
    						(*it)->setValue((*it)->getValue() + 1);
    						found = true;
    						break;
    					}
    				}
    
    				if (!found)
    				{
    					myNodes.push_back(new HuffmanNode(true, str[i], 1));
    				}
    			}
    
    			HuffmanNode *newNode = NULL;
    
    			while (myNodes.size() > 1)
    			{
    				newNode = new HuffmanNode(false, 0, 0);
    
    				HuffmanNodes::iterator left = findLowestNode();
    				newNode->setLeft(*left);
    				myNodes.erase(left);
    
    				HuffmanNodes::iterator right = findLowestNode();
    				newNode->setRight(*right);
    
    				newNode->setValue(newNode->getLeft()->getValue() + newNode->getRight()->getValue());
    
    				*right = newNode;
    			}
    
    			myRoot = newNode;
    
    			std::string complete;
    
    			for (unsigned int i = 0; i < str.length(); ++i)
    			{
    				getCode(newNode, str[i], "");
    				complete += myCodeBuf;
    			}
    
    			myCodeBuf = complete;
    
    			decode(myRoot, 0);
    
    			std::cout << myCodeBuf << std::endl;
    			std::cout << myValueBuf << std::endl;
    
    			delete newNode;
    		}
    
    		void decode(HuffmanNode *start, unsigned int pos)
    		{
    			if (pos > myCodeBuf.length())
    			{
    				return;
    			}
    
    			if (start->isLeaf())
    			{
    				myValueBuf += start->getChar();
    
    				start = myRoot;
    			}
    
    			if (myCodeBuf[pos] == '0')
    			{
    				if (start->getLeft())
    				{
    					decode(start->getLeft(), pos + 1);
    				}
    			}
    			else
    			{
    				if (start->getRight())
    				{
    					decode(start->getRight(), pos + 1);
    				}
    			}
    		}
    
    		HuffmanNodes::iterator findLowestNode()
    		{
    			int min = -1;
    
    			HuffmanNodes::iterator pos = myNodes.end();
    
    			for (HuffmanNodes::iterator it = myNodes.begin(); it != myNodes.end(); ++it)
    			{
    				if ((*it)->getValue() < min || min == -1)
    				{
    					pos = it;
    					min = (*it)->getValue();
    				}
    			}
    
    			return pos;
    		}
    
    		void getCode(HuffmanNode *start, char c, std::string code)
    		{
    			if (start->isLeaf())
    			{
    				if (start->getChar() == c)
    				{
    					myCodeBuf = code;
    					return;
    				}
    			}
    			else
    			{
    				getCode(start->getLeft(), c, code + "0");
    				getCode(start->getRight(), c, code + "1");
    			}
    		}
    };
    
    int main()
    {
    	Huffman huff;
    
    	huff.encode("Sollte dieser Text erscheinen, dann war der Test erfolgreich :-)");
    }
    

    Aber er scheint zumindest korrekt zu funktionieren. Ich müsste das ganze jetzt vom String weg auf Bits anwenden, aber da fehlt mir die Grundlage über Bitmanipulationen. 😞



  • ohne deinen Code angeschaut zu haben: du kannst ja einfach im letzten Schritt von Strings auf Bits konvertieren. Und die Bit-Grundlagen musst halt einfach lernen. Dazu ist eine Huffman-Implementierung sogar ideal -- genau damit hab ich ernsthaft Bitoperationen in C++ erlernt 🙂



  • Wenn's hilft:

    void TBitStream::writeBits(unsigned long val,unsigned long digits)
    {
      flushRBuf();
      if (digits<32)val&=(1<<digits)-1;
      if (digits>24)
      {
        writeBits(val&16777215,24);
        writeBits(val>>24,digits-24);
      }
      else
      {
        binaryLength+=digits;
        binData|=val<<(binaryLength-digits);
        handleData();
      }
    }
    
    void TBitStream::handleData()
    {
      while (binaryLength>=8)
      {
        writeBuffer[writeBufferPos++]=binData&255;
        if (writeBufferPos>=writeBufferSize)flushWBuf();
        binData>>=8;
        binaryLength-=8;
      }
    }
    

    Geht evtl. auch ohne die Sonderbehandlung für >24 Bits.
    Habe den Code vor gut zehn Jahren geschrieben, wahrscheinlich habe ich mir was dabei gedacht (oder auch nicht).
    Aber so funktioniert es auf jeden Fall, die Bitoperationen kannst du übernehmen. Das ganze mal selbst auf Papier durchzuspielen hilft beim Verständnis.
    Edit: Sonderbehandlung kannst du nur weglassen, wenn du für binData einen 64-bit-Typ verwendest.



  • Danke, ich hab noch etwas gelesen und speicher das ganze nun so nach und nach in einem std::string

    char temp = 0;
    			int counter = 8;
    			for (unsigned int i = 0; i < myCodeBuf.length(); ++i)
    			{
    				if (counter <= 0)
    				{
    					counter = 7;
    					myRealBuf += temp; // myRealBuf = das finale Ergebnis
    					temp = 0;
    				}
    				else
    				{
    					counter--;
    				}
    
    				if (myCodeBuf[i] == '1') 
    temp |= (1 << counter);
    			}
    

    Auslesen kann ich das dann wieder so:

    for (unsigned int i = 0; i < myRealBuf.length(); ++i)
    			{
    				for (int j = 7; j >= 0; --j)
    				{
    					char c = myRealBuf[i];
    					if ((c & (1 << j)) != 0)
    					{
    						std::cout << "1";
    					}
    					else
    					{
    						std::cout << "0";
    					}
    				}
    			}
    

    Ich hoffe, diese Vorgehensweise ist so in Ordnung. Zumindest scheint es zu funktionieren 🙂

    Allerdings werde ich wohl tatsächlich zur Dekomprimierung neben der Häufigkeitstabelle auch die Anzahl der Bits speichern müssen, damit ich später weiß, wo der Code wirklich zu ende ist.

    Danke für die ganze Hilfe 👍



  • Ich konnte inzwischen fast alles lösen 🙂 Das einzige Problem, dass ich noch habe, ist die Speicherung der Häufigkeitstabelle.

    Ich hatte erst die Idee, sie nach diesem Format einfach an den Anfang der Datei zu schreiben:

    a 10\n
    b 2\n
    f 3\n
    t 54\n
    \n
    <Komprimierte Daten>
    

    Allerdings frage ich mich, ob das auf diesen Weg sinnvoll ist?


Anmelden zum Antworten