huffman codierung -> wirres zeug bei einigen daten



  • Hallo

    ich möchte den huffman codierer nachbauen. für kleine texte funktiniert das
    prima. für größere, insbesondere binärdateien klappt das aber nichtmehr, und
    warum das nicht klappt versteh ich nicht 😃

    zuerst hab ich mir eine kleine bitstream klasse geschrieben, damit das
    bitgeschiebe sicherer wird.

    class bitstream
    {
    public:
    	bitstream() : frac(0)
    	{
    	}
    	void pushbit(unsigned char bit)
    	{
    		bit &= 1;
    
    		if (!frac)
    			vec.push_back(bit);
    		else
    			vec.back() |= bit << frac;
    
    		++frac;
    		frac %= bitcount;
    	}
    	unsigned char getbit(unsigned pos) const
    	{
    		if (pos >= getsize())
    			return 0;
    
    		return (vec[pos / bitcount] >> (pos % bitcount)) & 1;
    	}
    	unsigned getsize() const
    	{
    		return vec.size() * bitcount + frac - (frac ? bitcount : 0);
    	}
    private:
    	static const unsigned bitcount = 32;
    	std::vector<unsigned> vec;
    	unsigned frac; // rest eines 32-bit wortes
    };
    

    die benötigten struturen und funktionen:

    struct node // ein knoten im graphen
    {
    	bool operator < (const node &other)
    	{
    		return num < other.num;
    	}
    	node *left, *right;
    	unsigned num;
    	unsigned value;
    };
    struct lookup // tabelle, die die umwandlung zeichen -> huffcode erlaubt
    {
    	unsigned data; // die bits
    	unsigned length; // bit-länge
    };
    void build_lookup(lookup *l, node *p, unsigned char data, unsigned length)
    { // baut rekurisv die tabelle auf
    	if (p->left)
    	{
    		build_lookup(l, p->left, data << 1, length + 1);
    		build_lookup(l, p->right, (data << 1) | 1, length + 1);
    	}
    	else
    	{
    		l[p->value].data = data;
    		l[p->value].length = length;
    	}
    }
    

    als erstes zähle ich welches zeichen wie oft vorkommt. im zweiten teil (+256)
    des buffers speichere ich das zeichen selber um den buffer kompakt und ohne
    lücken(wichtig) zu halten:

    const unsigned char *pstr = msg;
    	const unsigned char *endptr = msg + strlen((char*)msg); //f.GetBufferSize();
    	while (pstr != endptr)
    	{
    		bool found = false;
    		for (unsigned i = 0; i < max_pos; ++i)
    		{
    			if (buffer[256 + i] == *pstr)
    			{
    				++buffer[i];
    				found = true;
    				break;
    			}
    		}
    		if (!found)
    		{
    			buffer[max_pos] = 1;
    			buffer[256 + max_pos++] = *pstr;
    		}
    		++pstr;
    	}
    

    jetzt noch die baumstrucktur aufbauen:

    node nodes[512];
    	node *root = 0;
    	for (unsigned i = 0; i < max_pos; ++i)
    	{
    		nodes[i].left = 0;
    		nodes[i].right = 0;
    		nodes[i].num = buffer[i];
    		nodes[i].value = buffer[256 + i];
    	}
    	unsigned index = 512; // position vor der neue elemente eingefügt werden
    	while (max_pos > 1)
    	{
    		node *min_node;
    
    		min_node = std::min_element(nodes, nodes + max_pos);
    		std::swap(*min_node, nodes[max_pos - 1]); // kleinstes element an das ende kopieren
    		min_node = std::min_element(nodes, nodes + max_pos - 1);
    		std::swap(*min_node, nodes[max_pos - 2]); // zweitkleinstes element vor das ende kopieren
    
    		// platz freimachen (ans ende des buffers kopieren)
    		nodes[--index] = nodes[max_pos - 1];
    		nodes[--index] = nodes[max_pos - 2];
    
    		node &last = nodes[max_pos - 2]; // freigewordenes element
    
    		last.left = &nodes[index];
    		last.right = &nodes[index + 1];
    		last.num = last.left->num + last.right->num;
    		last.value = 0;
    
    		root = &last;
    
    		--max_pos;
    	}
    

    danach "nurnoch" codieren und decodieren

    lookup table[256];
    build_lookup(table, root, 0, 0);
    
    bitstream bs;
    
    pstr = msg;
    while (pstr != endptr)
    {
    	const lookup &l = table[*pstr++];
    
    	for (unsigned i = 0; i < l.length; ++i)
    		bs.pushbit(l.data >> (l.length - i - 1));
    }
    
    // decode
    std::vector<unsigned char> decoded;
    
    unsigned pos = 0;
    
    while (bs.getsize() > pos)
    {
    	node *pnode = root;
    	while (pnode->left)
    	{
    		pnode = bs.getbit(pos) ? pnode->right : pnode->left;
    		++pos;
    	}
    	decoded.push_back(pnode->value);
    }
    

    bei kleinen daten klappt es wie bereits gesagt. ich weiß echt nich woran
    das liegen kann, das programm läuft auch ohne absturz, warnung etc...



  • Ehrlich gesagt, ist mir das zu viel zum Durchlesen. An deiner Stelle würde ich mir Stift und Zettel schnappen und parallel zum Debugger von Hand mitrechnen. Dann sollte dein Fehler schon auffallen. Mit ein wenig Geschick ist das nicht allzu viel Arbeit.


Log in to reply