کد هافمن و ایجاد جدول کدینگ

[saeedizade]

سلام
من توی هافمن درخت رو تشکیل دادم
(یعنی از فایل خوندم و با الگوریتمش اون درختو تشکیل دادم)
توی قسمتی که باید به هر کاراکتر کد صفر و یک اختصاص بدیم الگوریتمی به نظرم نمباد
یعنب کاملا درک کردم الگوریتم هافمنو ولی قسمت کد دادن به هر کاراکتر رو چیزی به ذهنم نمیرسه
کسی (ترجیها یه صورت کد) تابعی می تونه بونیسه که درخت رو حرکت کنه و به هر کاراکتر کد بده؟




#include <iostream>
#include <string>
#include <fstream>
#include <cstring>
using namespace std;
fstream infile;
struct node{
int frequency;
char character;
int codehuffman;
node *Llink,*Rlink;
node()
{
frequency=0;codehuffman=0;character=0;Llink=0;Rlin k=0;
}
}nodearray[256];

void frequency (char ch)
{
int a=ch;
nodearray[a].frequency++;
}
void lvr(struct node* head)
{
if (head == NULL)
return;

lvr(head->Llink);

cout<<head->frequency<<" ";

lvr(head->Rlink);

}
void vlr(struct node* head)
{
if (head == NULL)
return;
cout<< head->frequency<<" ";
vlr(head->Llink);
vlr(head->Rlink);
}

int main()
{
infile.open("data.txt");
string line;
while(getline(infile,line))
{
int sizeline;
sizeline=line.length();
char* newdata=new char[sizeline];
strcpy(newdata,line.c_str());
for(int num=0;num<sizeline;num++)
frequency(newdata[num]);
}

for(int i=0;i<256;i++)//set char
nodearray[i].character=i;

int barg=0;
for(int i=0;i<256;i++)//number of barg
if(nodearray[i].frequency>0)
barg++;

node *newnodearr=new node[barg];

int barg2=0;
for(int i=0;i<256;i++)
if(nodearray[i].frequency>0){
newnodearr[barg2]=nodearray[i];
barg2++;
}

for(int i=0;i<barg2-1;i++)
{
for(int j=0;j<barg2-1;j++)
{
if(newnodearr[j].frequency < newnodearr[j+1].frequency)
{
node a=newnodearr[j];
newnodearr[j]=newnodearr[j+1];
newnodearr[j+1]=a;

}
}
}
for(int i=0;i<barg2;i++)
cout<<"char : "<<newnodearr[i].character<<" fre : "<<newnodearr[i].frequency<<endl ;


while(1)//build tree
{
node newnode;
newnode.frequency=newnodearr[barg2-1].frequency+newnodearr[barg2-2].frequency;

newnode.Llink=&newnodearr[barg2-1];
newnode.Rlink=&newnodearr[barg2-2];
node* newnodearr2=new node[barg2];
for(int i=0;i<barg2-1;i++)
newnodearr2[i]=newnodearr[i];

newnodearr2[barg2-2]=newnode;

newnodearr =new node[barg2];
for(int i=0;i<barg2-1;i++)
newnodearr[i]=newnodearr2[i];


barg2-=1;
for(int i=0;i<barg2-1;i++)
for(int j=0;j<barg2-1;j++)
if(newnodearr[j].frequency < newnodearr[j+1].frequency)
{
node a=newnodearr[j];
newnodearr[j]=newnodearr[j+1];
newnodearr[j+1]=a;
}


if(barg2==1)
break;
}


cout<<endl;

cout<<"lvr : "<<endl;
lvr(newnodearr);cout<<endl;cout<<"vlr : "<<endl;
vlr(newnodearr);

cin.get();

return 0;
}

[aqm176]

سلام.

من کدشو نوشتم یادم نیست چکارش کردم و الا بهتون میدادم.

ببینید اگر شما بخواید یک رشته رو کد کنید، باید اولا ترتیب قرار گیری رو داشته باشید، و لذا یه شرط رو رعایت کنید که ترکیب هر دوتا بشه بکیه بعدی.

شاید بهتون کمک کرده باشم، چون خودش یه فرمول داره منم یادم رفته.

روزتون خوش

[saeedizade]

سلام.

من کدشو نوشتم یادم نیست چکارش کردم و الا بهتون میدادم.

ببینید اگر شما بخواید یک رشته رو کد کنید، باید اولا ترتیب قرار گیری رو داشته باشید، و لذا یه شرط رو رعایت کنید که ترکیب هر دوتا بشه بکیه بعدی.

شاید بهتون کمک کرده باشم، چون خودش یه فرمول داره منم یادم رفته.

روزتون خوش


بله درسته این شرط رعایت شده
کسی ایده برای کد دادن به هر یرگ داره؟
struct node{
int frequency;
char character;
int codehuffman;

node *Llink,*Rlink;
node()
{
frequency=0;codehuffman=0;character=0;Llink=0;Rlin k=0;
}
}nodearray[256];


ایده خاصی به ذهنم نمیرسه تا codehuffman رو بدمش

[aqm176]

سلام.

تو الگوریتم فاهمن بر اساس تعداد تکرارشون کد گذاری کن.
مثالی رو گذاشتم در تصویر زیر:
138482

[saeedizade]

شما سوال منو متوجه نمیشی لزومی نداره جواب بدی😊

[aqm176]

سلام مجدد.
میتونستید بجای بیان حرفی که بی آلایش است، کمی دقت کنید.

کتاب ساختمان داده قلزم هست در پی سی دانلود.
دانلود کنید و قشنگ مفهموشو درک کنید، تا به حرف من هم پی ببرید
روز خوش

[rahnema1]

سلام
این کدها را به صورت رشته نشون میده نحوه استفاده هم در تابع main مشخص شده

struct node
{
int value;
node* left;
node* right;
string code;
};

void coding(node* tree, int index = 0)
{
static char buffer[256];
if(tree->left != NULL)
{
buffer[index] = '0';
coding(tree->left, index + 1);
buffer[index] = '1';
coding(tree->right, index + 1);
}
else
{
buffer[index] = '\0';
tree->code = string(buffer);
}
}

int main()
{
node* tree;
//...
//...
coding(tree);
}

[saeedizade]

سلام
این کدها را به صورت رشته نشون میده نحوه استفاده هم در تابع main مشخص شده

struct node
{
int value;
node* left;
node* right;
string code;
};

void coding(node* tree, int index = 0)
{
static char buffer[256];
if(tree->left != NULL)
{
buffer[index] = '0';
coding(tree->left, index + 1);
buffer[index] = '1';
coding(tree->right, index + 1);
}
else
{
buffer[index] = '\0';
tree->code = string(buffer);
}
}

int main()
{
node* tree;
//...
//...
coding(tree);
}


متاسفانه جواب نگرفتم
ادرس root درخت رو میدم ولی کار نمیکنه

[saeedizade]

درواقع یک تابع میخام head درختو بهش بدم حرکت کنه و کل درختو بهش کد نسبت بده:خجالت:

[aqm176]

سلام.
یه مورد دیگه هم که در این الگوریتم هستش اینه که، این الگوریتم بدین صورت کد داده میشه که: NLR ینی اول ریشه و بعد فرزند چپ و فرزند راست به صورت 0 و 1 کد گذاری میشه.
بعد عبارت رو که بصورت postfix بخونید، میشه اون جمله ای که کد کردید.

[saeedizade]

سلام.
یه مورد دیگه هم که در این الگوریتم هستش اینه که، این الگوریتم بدین صورت کد داده میشه که: NLR ینی اول ریشه و بعد فرزند چپ و فرزند راست به صورت 0 و 1 کد گذاری میشه.
بعد عبارت رو که بصورت postfix بخونید، میشه اون جمله ای که کد کردید.
سلام
بله دقیقا
ما باید به چب حرکت کردیم مقدار صفر را داخل پشته بریزیم و راست یک منتها من توی پیاده سازیش به شکل کد خیلی مشکل دارم

[aqm176]

سلام مجدد.

توی کدتون که نگاه کردن، دیدم که لفت و رایت رو دارید که توش ادرس ریخته میشه.

فقط یه حلقه میخواید که بگید تا موقعی که لفت و رایت خالی باشه یا نال باشه برو پایین.
بعد از اونجا شروع کن بزن 1 و برگرد بالا دستت بزن 0 بالادستت اگه چپ داشت بره چپ فیلد کدشو بکنه 0.
حالا کدشو گیر بیارم بهتون میدم.
خیلی راحت تر از این حرفاس.

روزتون خوش

[IamOverlord]

سلام دوست عزیز!
شاید راهی که پیشنهاد می دم زیاد مناسب نباشه..
ولی راهی که به ذهنم رسید این بود که:

آدرس ریشه رو بذاریم تو پشته،
رشته ی کد را با مقداری تهی ایجاد کنیم.. و این حلقه را اجرا کنیم:
--- اگر می شد
--- --- به سمت چپ برویم و 0 را به انتهای کد اضافه کنیم..
--- وگرنه
--- --- به گره رسیدیم و کد گره ی فعلی را ذخیر می کنیم برای آن..
--- --- این حلقه ی فرعی را اجرا می کنیم
--- --- --- یک گره به عقب بر می گردیم (با pop کردن پشته..)
--- --- --- اگر پشته خالی شد از این حلقه ی فرعی خارج می شویم..
--- --- --- یک رقم از انتهای کد حذف می کنیم
--- --- --- اگر فرزند راست گره ی فعلی همان گره ی قبلی ای باشد که از پشته خارج کردیم این حلقه را ادامه می دهیم
--- --- اگر پشته خالی بود از حلقه ی اصلی خارج می شویم وگرنه
--- --- یک گره به سمت راست حرکت می کنیم..
--- --- به کد 1 را اضافه می کنیم..
--- حلقه ی اصلی را ادامه می دهیم..

شاید روی کاغذ این مراحل را برای خودتون تجسم کنید راحت تر متوجه بشید چی کار می کنه دقیقا..
این هم قطعه کد از این الگوریتم به زبان ++C:

stack<node*> path; path.push(nodes[0]);


string code = "";
while(true) {
if(path.top()->pLeft != NULL) {
path.push(path.top()->pLeft);
code += '0';
} else {
codes[(int)(unsigned char)(path.top()->symbol)] = code;
node* pLastNode;
do {
pLastNode = path.top();
path.pop();
if(path.empty())
break;
code.pop_back();
} while (path.top()->pRight == pLastNode);
if(path.empty())
break;
path.push(path.top()->pRight);
code += '1';
}
}

شاید نوشتن یک تابع بازگشتی کار را راحت تر هم بکند..

[saeedizade]

سلام خودم تابعی نوشتم که ادرس ریشه رو میگیره و به تمام برگ ها کد هافمنو نسبت میده


void lvr(struct node* head)
{
static char stk[100] ;
static int a = 0;
if (head == NULL)
{
a--;
stk[a] = 0;
return;
}
stk[a] = '0'; a++;
lvr(head->Llink);
head->codehuffman = stk;
cout << head->codehuffman << " " ;
stk[a] = '1';
a++;
lvr(head->Rlink);
a--;
}

[saeedizade]

حالا کد کامل
باید یک فایل با نام data.txt رو بزارید کنارش تا فشرده منه اگه چند بار میخواهید تست کنید فایل های ایجاد شده رو پاک کنید(مثل فایل comperss و.. که میسازد و متعلق به فایل قبلی است




#include <iostream>

#include <string>

#include <fstream>


using namespace std;

class node{

public:

char character;

string codehuffman;

int freq;

node * Llink;

node * Rlink;


//string position;

node()
{

Llink = NULL;

Rlink = NULL;

int freq = 0;

character = 0;

codehuffman = "";

// position = "";
}

};

struct node2{
char a;
string code;
};

node nodearray[256]; //array to save feature of character : freq , ...

void setfreq(char a) //set number of frequency of character
{

int i = a;

nodearray[i].freq++;

}


void vlr(struct node* head)
{
if (head == NULL)
return;
cout << head->codehuffman << " ";
vlr(head->Llink);
vlr(head->Rlink);
}
void lvr(struct node* head)
{
static char stk[100] ;
static int a = 0;
if (head == NULL)
{
a--;
stk[a] = 0;
return;
}
stk[a] = '0'; a++;
lvr(head->Llink);
head->codehuffman = stk;
cout << head->codehuffman << " " ;
stk[a] = '1';
a++;
lvr(head->Rlink);
a--;
}
void jadval(node * head)
{
static ofstream outfile("table.txt");

if (head == NULL)
return;

jadval(head->Llink);
if (head&&head->character)
outfile << head->character<<" " <<head->codehuffman<<endl;

jadval(head->Rlink);
}
void finalwrite(char arr[8],ofstream * outfile)
{
int a=0;
if (arr[0] == '1')
a += 128;
if (arr[1] == '1')
a += 64;
if (arr[2] == '1')
a += 32;
if (arr[3] == '1')
a += 16;
if (arr[4] == '1')
a += 8;
if (arr[5] == '1')
a += 4;
if (arr[6] == '1')
a += 2;
if (arr[7] == '1')
a += 1;
char b= a ;
cout << a<<" ";
*outfile << b;

}

int main()
{
int length = 256;

for (int i = 0; i < length; i++)
nodearray[i].character = i;//set index of array to character of class

ifstream infile("data.txt"); // for read from file

if (!infile.is_open()) // if file is not open end program
{

cout << "file is not open";
cin.get();
return 0;
}

//string line;
char e;
while (infile>>e )
{ // read file and set number of frequency of char
setfreq(e);
}


int barg = 0; // number of char that it freq is not 0

for (int i = 0; i<256; i++)//number of barg
if (nodearray[i].freq>0)
barg++;

node *newnodearr = new node[barg]; // array of node that freq is not 0

int barg2 = 0;

for (int i = 0; i<256; i++)
if (nodearray[i].freq>0)
{
newnodearr[barg2] = nodearray[i];
barg2++;
}//built that array

int num = barg2;
for (int i = 0; i<barg2 - 1; i++)
{
for (int j = 0; j<barg2 - 1; j++)
{
if (newnodearr[j].freq < newnodearr[j + 1].freq) //sort that array big to small
{
node a = newnodearr[j];
newnodearr[j] = newnodearr[j + 1];
newnodearr[j + 1] = a;

}
}
}

for (int i = 0; i<barg2; i++)
cout << "char : " << newnodearr[i].character << " fre : " << newnodearr[i].freq << endl;
while (1) //building huffman tree
{
node newnode;

newnode.freq = newnodearr[barg2 - 1].freq + newnodearr[barg2 - 2].freq; //give to smaller char

newnode.Llink = &newnodearr[barg2 - 1]; //ser left
newnode.Rlink = &newnodearr[barg2 - 2]; //set right
node* newnodearr2 = new node[barg2];
for (int i = 0; i<barg2 - 1; i++)
newnodearr2[i] = newnodearr[i];

newnodearr2[barg2 - 2] = newnode; // new code take place of two old node

newnodearr = new node[barg2]; // updating array
for (int i = 0; i<barg2 - 1; i++)
newnodearr[i] = newnodearr2[i];


barg2 -= 1;
for (int i = 0; i<barg2 - 1; i++)
for (int j = 0; j<barg2 - 1; j++)
if (newnodearr[j].freq < newnodearr[j + 1].freq) // sort new array
{
node a = newnodearr[j];
newnodearr[j] = newnodearr[j + 1];
newnodearr[j + 1] = a;
}


if (barg2 == 1) // end if stay 1 node
break;
}//newnodearr root

lvr(newnodearr);
cout << endl;
vlr(newnodearr);
jadval(newnodearr);
ifstream infile1("table.txt");
node2 arraynode[265];
string line3;

while (getline(infile1, line3)){
char* newdata2 = new char[line3.size()];

strcpy(newdata2, line3.c_str()); //copy line in a char array
int t = newdata2[0];
arraynode[t].a = newdata2[0];
string k;
for (int num = 4; num < line3.size(); num++)
{

arraynode[t].code += newdata2[num];
}
}








ofstream comfile("compress.txt");
ifstream infile2("data.txt");



char w;
cout << endl;

while (infile2 >> w)
{
int u = w;
//cout << arraynode[u].a << ":";
//cout << arraynode[u].code << ":";
comfile << arraynode[u].code;
}//build frist compress file
infile2.close();
comfile.close();
ifstream infile3("data.txt");
int frist = infile3.tellg();
infile3.seekg(0,ios::end);
int end = infile3.tellg();
int sizefile= end - frist;
ofstream compfile("finalcompress.txt",ios::app);
infile2.open("compress.txt");
for (int r = 0; r < sizefile / 8; r++)
{
char buffer[8];
for (int h = 0; h < 8; h++)
{
infile2 >> buffer[h];
}
finalwrite(buffer,& compfile);
}
cout << endl << "compress ended";
cin.get();
return 0;
}