Hash Tree , dekompriemieren, nur wie ?!
-
Hi Liebe Comm. !
Ich habe da ein Leider etwas größeres Problem
Ich muss eine Datei welche mit einem Hash Tree komprimiert wurde dekompriemieren.
Den Code habe ich angegeben, und den kompletten Hash tree ebenfallsIch möchte euch hier einfach mal aufzeigen was ich bis jetzt alles habe
Hash Table:
: 000 A: 0011 B: 111011 C: 01111 D: 10000 E: 110 F: 011100 G: 011101 H: 01010 I: 0100 J: 111111010 K: 1111111 L: 01011 M: 11110 N: 0110 O: 1011 P: 111000 Q: 111111011 R: 1010 S: 1001 T: 0010 U: 10001 V: 111001 W: 111110 X: 111111001 Y: 111010 Z: 111111000
Daraufhin hab ich erstmal einen "Möglichkeitsbaum" erstellt
zu sehen hier
http://img370.imageshack.us/img370/5237/dsc06231hy1.th.jpgSo und nun hab ich folgende files aus dennen ich irgendwie eine Rekursive Funktion rausbasteln muss
Branch - Zweig meine Möglichkeitenbaumes
#include "branch.h" branch::branch(tree_item* ll,tree_item* rr) : tree_item() { l=ll; r=rr; } branch::~branch() { } /*! \fn branch::left() */ tree_item* branch::left() { return l; } /*! \fn branch::right() */ tree_item* branch::right() { return r; } /*! \fn branch::value() */ int branch::value() { /// @brief calls the value functions of its successors ///and summarizes them to the return value return((l->value()) + (r->value())); }
Branch.h
class branch : public tree_item { public: branch(tree_item* ll,tree_item* rr); ~branch(); tree_item* left(); tree_item* right(); int value(); protected: tree_item* l; tree_item* r; };
Dann hab ich noch ein leave was sozusagen den buchstaben darstellen soll
#include "leave.h" leave::leave( int bst, int anz) : tree_item() { ch=bst; v=anz; } leave::~leave() {} /*! \fn leave::value() */ int leave::value() { return v; } /*! \fn leave::left() */ tree_item* leave::left() { /// @brief no successor return 0; } /*! \fn leave::right() */ tree_item* leave::right() { /// @brief no successor return 0; } /*! \fn leave::char_numbr() */ int leave::char_numbr() { return ch; }
das .h file ->
class leave : public tree_item { public: leave(int bst, int anz); ~leave(); int value(); tree_item* left(); tree_item* right(); int char_numbr(); protected: int v; int ch; };
und nun gibt es noch einen hash_tree.cpp
#include<string.h> #include "hash_tree.h" /*! \brief builds huffman tree from array h - 27 elements */ hash_tree::hash_tree(int h[]) { /// cleaning the queue for(int i=0;i<27;++i) items[i]=0; semaphor=0; /// building the queue for(int i=0;i<27;++i) insert(i,h[i]); } hash_tree::~hash_tree() {} /*! \fn hash_tree::insert(int ch,int val) \brief inserts a new leave into the queue */ void hash_tree::insert(int ch,int val) { /*!produces new leave*/ leave * p_l=new leave(ch,val); ///inserts into queue insert( p_l ); } /*! \fn hash_tree::insert(tree_item *) */ void hash_tree::insert(tree_item * t) { /*!searches correct position*/ int i=0; while(items[i] && t->value()<=items[i]->value()&& i<26) i++; /*!reserves place*/ for(int j=26;j>i;j--) items[j]=items[j-1]; /*!inserts new element*/ items[i]=t; /*!corrects amount of items*/ if(semaphor<27)semaphor++; } /*! \fn hash_tree::huff() builds the tree */ void hash_tree::huff() { while(semaphor>1) { /// removes the highest two elements (the two smallest amounts) tree_item* hp1= remove(semaphor-1); tree_item* hp2= remove(semaphor-1); /// builds new branch lower left - higher right tree_item* hp3 = new branch(hp1,hp2); ///inserts into queue insert(hp3); } } /*! \fn hash_tree::remove(int nr) removes one element from the queue and returns its adress element will not be deleted */ tree_item * hash_tree::remove(int nr) { if(nr<27 && semaphor) { /// takes tree item from queue to pointer tree_item * h_p=items[nr]; ///packs queue for (int i=nr;i<semaphor-1;i++) items[i]=items[i+1]; items[semaphor-1]=0; semaphor--; return h_p; } else return 0; } /*! \fn hash_tree::get_hashtable(char[][26]) fills a record of char strings with 0/1s read from the huffman tree */ void hash_tree::get_hashtable(char cde[][26]) { char code[26]=""; trajekt(code,0,items[0]); for( int ch_n=0;ch_n<27;ch_n++) strcpy(cde[ch_n],hash_table[ch_n]); } /*! \fn hash_tree::trajekt(char c[],int lvl) */ void hash_tree::trajekt(char c[],int lvl,tree_item * br) { if(br->left()) { c[lvl]='1'; trajekt(c,lvl+1,br->left()); } if(br->right()) { c[lvl]='0'; trajekt(c,lvl+1,br->right()); } if(!br->left()&&!br->right()) { c[lvl]=0; leave* l_p=(leave*)(br); strcpy(hash_table[l_p->char_numbr()],c); hash_table[l_p->char_numbr()][lvl]=0; } }
mit .h file
class hash_tree{ public: hash_tree(int h[]); ~hash_tree(); void insert(int ch,int val); void insert(tree_item *); void huff(); tree_item * remove(int nr); void get_hashtable(char[][26]); void trajekt(char c[],int lvl, tree_item* br); protected: tree_item* items[27]; int semaphor; char hash_table[27][26]; };
und schließlich noch das tree_item
class hash_tree{ public: hash_tree(int h[]); ~hash_tree(); void insert(int ch,int val); void insert(tree_item *); void huff(); tree_item * remove(int nr); void get_hashtable(char[][26]); void trajekt(char c[],int lvl, tree_item* br); protected: tree_item* items[27]; int semaphor; char hash_table[27][26]; };
Tja das wärs so weit bin ich leider finde ich nirgendst wo im Internet ein Tutorial das mir aufzeigt wie ich nun aus den mir gegebenen Dateien ein Rekursives Programm schreibe welches mir das ganze file wieder dekomprimiert.
Aber vlt wisst ihr wo ich eines finde? oder könnt mir bei meinem rekursiven PGM helfenWas ich weiß ist das ich für jeden Buchstaben sozusagen einen ablauf brauchen z.B. fgetch()=0 -> leave left wenn 3x leave left war -> Leerzeichen
oder so ähnlich leider mach ich das zum ersten malDie zweite möglichkeit wäre das ganze mit hunderten ifs zu dekomprimieren aber das ist nicht das was ich mir unter einer elegante lösung vorstelle
mfg
-
Warum erfindest Du das Rad neu und nimmst nicht einen der vielen verfügbaren Kompressionsformate? Huffman? Du könntest dort auch studieren wie es dort implementiert ist.
Wenn Du Deine bitstruktur auspacken willst kannst Du Dich doch die HashTable als Baum darstellen und Dich an den Knoten entlang hangeln bis Du auf ein Blatt stößt.
-
genau dieses am baum entlanghangeln dabei scheiterts
ich muss ja dann immer wieder zum ursprung zurueck springen und dabei hengts bei mir ein bisschen noch ich komm einfahc gerade nicht drauf wie ich das machen soll
-
Dieser Thread wurde von Moderator/in GPC aus dem Forum Andere GUIs - Qt, GTK+, wxWidgets in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
rekursionen sind nicht nötig, da du ja nur entlang des pfades im baume gehen musst. du hast drei werte pro knoten im baum:
struct node { node* children[2]; char character;
character ist für alle jene nodes 0, die keinen gültigen buchstaben enthalten (ich gehe davon aus, dass 0 kein gültiges zeichen seines eingabealphabeths zur komprimierung ist.).
du nimmst nun das erste bit deiner komprimierten eingabe und verwendest es als index in das array children der wurzel. damit kommst du zu einer zweiten node. du prüfst, ob character 0 ist. ist es 0, so musst du ein weiteres bit deines datenstroms nehmen, um wieder per children-array auf die nächste node kommen. sollte dann irgendwann eine node kommen, deren character nicht 0 ist, hast du einen buchstaben gefunden und schreibst diesen in deine ausgabe. mit dem nächsten bit des komprimierten datenstroms beginnst du wieder bei der wurzel.wenn z.b. deine komprimierung mit einem komprimierten E beginnt, bekommst du node = wurzel->children[1] =>
node = node->children[1] =>
node = node->children[0].
die letzte zuweisung weist "node" eine node zu, deren character != 0 nämlich E ist. damit beendest du die innere schleife, die den baum durchwandert und fährst mit der äußeren fort, die solange läuft, wie bits in der komprimierten eingabe sind.
-
oder als Kompositum implementieren
GetElement() {
wenn ich Blattknoten bin => übergebe mein Zeichen
ansonsten
-erhöhe Bitstrukur-iterator
-wenn der auf eine 0 zeigt rufe GetElement() des linken Kinderknotens auf
-ansonsten rufe GetElement() des rechten Kinderknotens auf