2
// 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;
}
따라서이 코드의 끝 부분에서 내 bytesread var = 약 5mil 바이트이지만 루트의 가중치는 0입니다. .내가 허프만 트리를 만든 후에 5 메가의 데이터를 읽을 때 루트의 가중치가 700k입니다.
당신이 알아낼 수 없다면 (나는 침대에서 벌레를 찾고있는 적어도 다른 시간을 보내고있을 것입니다.) 효율성을 향상시키기위한 조언을 줄 수 있습니까?
편집 : 문제는 if(freq[i]<min1)입니다. 먼저 잎이 [i] -> min1에 대한 가중치 비교가되어야합니다. 왜냐하면 그 배열이 실제로 나무를 만들기 위해 조작하고 있기 때문입니다 (freq []는 treenode 포인터가 아닌 가중치를가집니다). 문제를 해결하기 위해 그 라인과 if 구문을 다음과 같이 작성했습니다. if(leaves[i] && leaves[i]->weight<=min1) 및 if(leaves[i] && (leaves[i]->weight)<=min2 && i!=wheremin1)
내 코드를 정리할 제안이 더 많으면 (예 : 특정 위치에 주석 추가, 다른 방법 비교 등) 제발 제안 해주세요. 나는 훌륭한 코더가 아니지만 나는되고 싶고 좋은 코드를 가지고 일하려고 노력하고있다.
편집 2 : 새/고정 코드를 게시했습니다. 루트의 가중치가 이제 bytesread와 같습니다. 나는 아직도이 코드를 정리할 제안을하고있다. 내가 찾을 수
저는 학교에서 똑같은 일을하고 있습니다. 무게가 0 인 경우 어떻게 처리합니까? 트리를 만들 때 0 값을 무시할 수 있어야합니다. – Maynza
나는 나무에 던지기 만하고있다. 지금도 효율성에 대해 걱정하지 않아도됩니다. – Azreal