3. Hash Tree , dekompriemieren, nur wie ?!

Hash Tree , dekompriemieren, nur wie ?!

  • K

    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 ebenfalls

    Ich 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.jpg

    So 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 helfen

    Was 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 mal 😕

    Die 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 😉

    0
  • W

    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.

    0
  • K

    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

    0
  • C

    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.

    0
  • ?

    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.

    0
  • W

    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

    0
Anmelden zum Antworten