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 nichtzuerst 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.