Après avoir construit mon arbre de Huffman poids de la racine est 700k quand je l'ai lu 5megs de données

Question

// Huffman Tree.cpp

#include "stdafx.h"
#include <iostream>
#include <string>//Necessary to do any string comparisons
#include <fstream>
#include <iomanip>
#include <cstdlib>//for exit() function

using namespace std;

class BinaryTree{

private:
    struct treenode{
        char data;
        int weight;     
        treenode *LChild;
        treenode *RChild;
    };
    treenode * root;
    int freq[256];
    treenode* leaves[256];
    string path[256];
    string longestpath;
    void BuildHuffmanStrings(treenode *p, string path);

public:
    void InitializeFromFile(string FileName);
    void EncodeFile(string InFile, string OutFile);
    void DecodeFile(string InFile, string OutFile);


BinaryTree()
{
    for(int i=0;i<256;i++){
        freq[i]=0;
        leaves[i] = new treenode;
    }
    root=NULL;
}
};//Class end

    /*Takes supplied filename and builds Huffman tree, table of encoding strings, etc.
    Should print number of bytes read.*/
void BinaryTree::InitializeFromFile(string Filename){
    int CHAR_RANGE = 256;
    ifstream inFile;
    inFile.open(Filename.c_str(), fstream::binary);
    if(inFile.fail()){
        cout<<"Error in opening file "<<Filename;
        return;
    }
    char c;
    inFile.get(c);
    int bytesread = 0;
    while(!inFile.eof()){
        bytesread++;
        freq[(int)c] ++;
        inFile.get(c);
    }
    for(int i=0;i<CHAR_RANGE;i++){//makes a leafnode for each char
        leaves[i]->weight=freq[i];
        leaves[i]->data=(char)i;
    }
    int wheremin1, wheremin2, min1, min2;
    /*Builds the Huffman Tree by finding the first two minimum values and makes a parent
    node linking to both*/
    for(int k=0;k<256;k++){
        wheremin1=0; wheremin2=0;
        min1 = INT_MAX; min2 = INT_MAX;
        //Finding the smallest values to make the branches/tree
        for(int i=0;i<CHAR_RANGE;i++){
            if(leaves[i] && freq[i]<min1){
                min1=leaves[i]->weight; wheremin1=i;
            }
        }for(int i=0;i<CHAR_RANGE;i++){
            if(leaves[i] && freq[i]<min2 && i!=wheremin1){
                min2=leaves[i]->weight; wheremin2=i;
            }
        }
        if(leaves[wheremin1] && leaves[wheremin2]){
            treenode* p= new treenode;
            p->LChild=leaves[wheremin1]; p->RChild=leaves[wheremin2];//Setting p to point at the two min nodes
            p->weight=min1 + min2;
            leaves[wheremin2]=NULL;
            leaves[wheremin1]=p;
            root=p;
        }
    }//end for(build tree)
    cout<<" Bytes read: "<<bytesread;
    cout<<" Weight of the root: "<<root->weight;
}

/*Takes supplied file names and encodes the InFile, placing the result in OutFile. Also
checks to make sure InitializeFromFile ran properly. Prints in/out byte counts. Also 
computes the size of the encoded file as a % of the original.*/
void BinaryTree::EncodeFile(string InFile, string OutFile){

}

/*Takes supplied file names and decodes the InFile, placing the result in OutFile. Also
checks to make sure InitializeFromFile ran properly. Prints in/out byte counts.*/
void BinaryTree::DecodeFile(string InFile, string OutFile){

}

int main(array<System::String ^> ^args){
    BinaryTree BT;
    BT.InitializeFromFile(filename);
    return 0;
}

Alors mon bytesRead var = octets autour 5mil, mais le poids de ma racine est = à 0 à la fin de tout ce code.

Si vous ne pouvez pas le comprendre (je vais dépenser au moins une heure à la recherche du bug avant le coucher) pourriez-vous me donner quelques conseils pour améliorer l'efficacité?

Edit: Le problème a été if(freq[i]<min1). D'abord, il devrait être feuilles [i] -> comparaison de poids à min1 parce que c'est le tableau que je suis en fait manipuler pour créer l'arbre (fréq [] a juste poids, pas de pointeurs TreeNode). Donc, pour le fixer, je fis cette ligne et l'instruction if après: if(leaves[i] && leaves[i]->weight<=min1) et if(leaves[i] && (leaves[i]->weight)<=min2 && i!=wheremin1)

Si vous avez d'autres suggestions pour le nettoyage de mon code (. D'autres commentaires dans certains endroits, différentes façons de comparer, etc.), s'il vous plaît suggérer. Je ne suis pas un grand codeur, mais je voudrais être et je suis en train de travailler à avoir un bon code.

Edit2: Je posté le nouveau / code fixe. Le poids de ma racine est maintenant égale à bytesRead. Je suis toujours ouvert aux suggestions pour nettoyer ce code.

Answer 1

Peu chose que je pouvais trouver:

if(freq[i]<min1){

doit être

if(freq[i]<=min1){

comme vous ne pouvez pas dire à coup sûr vous toutes les fréquences seront moins INT_MAX. De même:

if(freq[i]<min2 && i!=wheremin1){

devrait être:

if(freq[i]<=min2 && i!=wheremin1){

min1 et min2 peuvent être égaux aussi.

Une fois que vous commencez à combiner les nœuds, vous prenez soin de supprimer les combinant nœuds et insérer le nouveau nœud combiné en changeant la matrice de leaves. Mais vous ne changez pas le tableau de freq, qui a besoin de changer les puits afin que les fréquences des noeuds supprimés ne participent pas à nouveau.

Answer 2

Quelques conseils:

1) une fonction "DumpState ()" qui produit la sortie (à Cout) à la recherche à peu près comme ceci:

 ============START==================
 freq[0] = <some number>
 freq[1] = <some number>
 ...
 freq[255] = <some number>
 leaves[0] = null
 leaves[1] = { data = 'B', weight = 3 }
 ...
 leaves[255] = null
 ============= END ================

Mettre cette fonction avant votre boucle principale, après une itération, après deux itérations, etc.

2) Créez un fichier d'entrée qui est vraiment, vraiment simple. Quelque chose comme:

aabc

Exécuter votre programme, et enregistrez le fichier journal (créé avec 1 ci-dessus). Travail à travers ce que devrait se passe avant la première boucle, dans la première boucle, etc. Comparez cela avec votre fichier journal, de ce que est en fait qui se passe. Vous pouvez imprimer quelques autres variables aussi (min1, min2, wheremin1, wheremin2).

Answer 3

Je n'ai pas encore la solution, mais ont peu de commentaires. Ceci est tout à fait un long morceau de code. Et pour être honnête peu maladroite. Je suggère de remanier votre code dans les méthodes appropriées. (Plusieurs fois, les problèmes sont résolus simplement en refactorisation!)

Par exemple, les lignes suivantes dans BinaryTree :: InitializeFromFile ()

for(int i=0;i<256;i++){
    freq[i]=0;
    leaves[i] = new treenode;
}

peut être plus approprié dans le constructeur BinaryTree. En outre, il y a deux éléments suivants dans BinaryTree

treenode * root;
treenode * leaves[256]

Pouvez-vous commenter ce qui est pour quoi? Le chiffre magique est de 256 est présent dans plusieurs endroits. Pouvez-vous avoir une variable convenablement nommée pour cela?