Compression

Post date: Nov 27, 2013 3:28:30 AM

سلام

چند روز قبل برای یه دوست، برنامه «فشرده سازی با استفاده از کد هافمن» را نوشتم. یک متن داریم که از کاراکترهای مشخصی استفاده می‌کند. مثلا این متن را در نظر بگیرید:

"aabaaxyxbaxaa"

می‌خواهیم این متن را به روش هافمن فشرده کنیم. اول باید کد صفر و یکی هر کاراکتر رو پیدا کنیم و بعد به جای هر کاراکتر کد مربوط به آن را بگذاریم. اول یک جدول از کاراکترها و تعداد تکرارشان درست می‌کنیم:

حالا برای به دست آوردن کد مربوط به هر کاراکتر، باید درخت دو دویی‌ای به دست بیاوریم که کدها را مشخص می‌کند. برای به دست آوردن این درخت از درخت‌های تک نقطه‌ای شروع می‌کنیم و به درخت‌های بزرگ تر می‌رسیم:

از بین این‌ها، دو تا را که کم ترین مقدار را دارند انتخاب می‌کنیم و از آن‌ها یک درخت دو دویی می‌سازیم:

مقدار سرشاخه اضافه شده برابر با مجموع مقدار ریشه‌هایش است. یعنی 3 = 2 + 1. همیشه ریشه سمت چپ کم تر (یا مساوی با) ریشه سمت راست است.

بعد دقیقا همین کار و سرشاخه‌های باقی مانده تکرار می‌کنیم. یعنی دو تا با کمترین مقدار را انتخاب می‌کنیم و از آن‌ها یک درخت بزرگ تر می‌سازیم:

و دوباره این کار را می‌کنیم تا فقط یک درخت باقی بماند:

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

با این درخت کد مربوط به هر کاراکتر مشخص می‌شود:

حالا متن "aabaaxyxbaxaa" به این صورت فشرده می‌شود: 1101111000100001110011 که در سه بایت جا می‌گیرد. یعنی 13 کاراکتر در 3 کاراکتر فشرده می‌شود.

البته فشرده سازی برای متن‌های طولانی معنی پیدا می‌کند. چون علاوه بر بیت‌هایی که به دست آمد جدول بالا هم باید ذخیره بشود که آن هم خودش جا می‌خواهد.

حالا قرار است برنامه‌ای بنویسیم که یک متن رو به روشی که گفتم فشرده کند.

من برای نوشتن این برنامه اول تصمیم گرفتم درخت‌های دو دویی رو شبیه سازی کنم. کار اصلی یک برنامه نویس شبیه سازی است. این کار رو به وسیله یک کلاس انجام دادم که خواص بازگشتی دارد. بعد، کلاسی برای فشرده سازی نوشتم:

#include <conio.h>

#include <string>

#include <vector>

#include <map>

#include <iostream>

using namespace std;

class BinTree // این کلاس درخت دو دویی را شبیه سازی میکند

{

public:

BinTree* left; // یال سمت چپ

BinTree* right; // یال سمت راست

int node;

char reserved_char; // برای ضبط کاراکتر وقتی درخت فقط یک نقطه است یعنی پایین ترین قسمت است

vector<bool> reserved_bins; // کدی صفر و یکی مربوط به کاراکتر بالا

//-----------------------

private:

void SetNode(int _node) // مقدار یک گره یعنی نقطه

{

node = _node;

}

void SetLeft(BinTree* _left) // تعیین یال چپ

{

left = _left;

}

void SetRight(BinTree* _right) // تعیین یال راست

{

right = _right;

}

//-----------------------

bool isSimple() // آیا درخت فقط یک نقطه است؟

{

return (left == 0);

}

int GetLeftNode() // مقدار عددی نقطۀ طرف چپ

{

return left -> node;

}

int GetRightNode() // مقدار عددی نقطۀ طرف راست

{

return right -> node;

}

//-----------------------

bool ContainTree(BinTree* subtree) // آیا این پارامتر بخشی از درخت اصلی است؟

{

if(subtree == this)

return true;

if(isSimple())

return false;

if(left -> ContainTree(subtree))

return true;

if(right -> ContainTree(subtree))

return true;

return false;

}

public:

vector<bool> GetBin(BinTree* subtree) // گرفتن کد صفر و یک هر نقطۀ تحتانی از درخت با استفاده از درخت

{

vector<bool> ret;

if(subtree == this)

return ret;

if(isSimple())

{

cout<< "Error in GetBin\n";

return ret;

}

if(left -> ContainTree(subtree))

{

ret.push_back(false);

vector<bool> v = left -> GetBin(subtree);

unsigned len = v.size();

for(unsigned i = 0; i < len; i++)

ret.push_back(v[i]);

}

if(right -> ContainTree(subtree))

{

ret.push_back(true);

vector<bool> v = right -> GetBin(subtree);

unsigned len = v.size();

for(unsigned i = 0; i < len; i++)

ret.push_back(v[i]);

}

return ret;

}

//-----------------------

void Print() // چاپ درخت . از این تابع استفاده نمی شود

{

cout<< node;

if(!isSimple())

{

cout<< "[";

left -> Print();

cout<< " : ";

right -> Print();

cout<< "]";

}

}

//-----------------------

BinTree(int _node)

{

SetNode(_node);

SetLeft(0);

SetRight(0);

}

BinTree(int _node, BinTree* _0, BinTree* _1)

{

SetNode(_node);

SetLeft(_0);

SetRight(_1);

}

};

class Compress // کلاسی که یک رشته می گیرید و به روش هافمن فشرده می کند

{

public:

string text;

vector<bool> bins;// برداری که متن بعد از تبدیل شدن به صفر و یک درش قرار میگیره. تا صفر و یک ها رو داشته باشیم.

private:

BinTree* tree; // the bintree made

typedef map<char,unsigned> MAP; //MAP تعریف

typedef MAP::iterator IT; //IT تعریف

typedef pair<char,unsigned> PAIR;

MAP char_count; // کاراکترها و تعداد آنها

vector<BinTree*> bintrees;

vector<BinTree*> simples;

vector<BinTree*> created_bintrees;// reserved for freeing memory

bool Repetitive(char ch) // مشخص کنندۀ تعداد تکرار کاراکتر

{

for (IT it = char_count.begin(); it != char_count.end(); it++)

{

if(it -> first == ch)

return true;

}

return false;

}

void FillMap()//char_count کامل کنندۀ

{

char_count.empty(); // protecting code

unsigned len = text.length();

for(unsigned i = 0; i < len; i++)

{

char ch = text[i];

if(Repetitive(ch))

char_count[ch]++;

else

char_count.insert(PAIR(ch,1));

}

}

//------------------------------------------------------------------

int Node(unsigned i)

{

return bintrees[i] -> node;

}

unsigned TreesNumber() // تعداد درختهایی که قرار است به هم متصل شوند

{

return bintrees.size();

}

void CombineTrees() // متصل کردن دو در خت مناسب از درخت های باقی مانده

{

unsigned n = TreesNumber();

if(n <= 1) // protecting abnormal use

return;

unsigned i_min1 = 0;

unsigned i_min2 = 0;

for(unsigned i = 0; i < n; i++) // minimum offset

{

if(Node(i) < Node(i_min1))

i_min1 = i;

}

for(unsigned i = 0; i < n; i++) // second minimum offset

if(i != i_min1)

{

if(Node(i) < Node(i_min2))

i_min2 = i;

}

if(i_min1 == i_min2)

i_min2++;

int node = Node(i_min1) + Node(i_min2); // new node for new_tree

BinTree* left = bintrees[i_min1]; // left for new_tree

BinTree* right = bintrees[i_min2]; // right for new_tree

BinTree* new_tree = new BinTree(node,left,right); // new bintree

bintrees[i_min1] = new_tree; // replace offset i_min1

bintrees.erase(bintrees.begin() + i_min2); // delete offset i_min2

created_bintrees.push_back(new_tree); // reserved for freeing memory

}

void CreateBinTree() // ایجاد درخت اصلی بزرگ با استفاده از کاراکترها و تعداد آنها

{

FillMap();

for (IT it = char_count.begin(); it != char_count.end(); it++)

{

bintrees.empty(); // protecting code

BinTree* simple = new BinTree(it -> second);

simple -> reserved_char = it -> first;

bintrees.push_back(simple);

simples.push_back(simple);

created_bintrees.push_back(simple); // reserved for freeing memory

}

while(TreesNumber() > 1) // combine bintrees to get one

CombineTrees();

}

void GetTree() // تولید و انتساب درخت اصلی

{

CreateBinTree();

tree = bintrees[0];

}

void FindBinCodes() // قرار دادن کد مربوط به هر کاراکتر به درخت تک نقطۀ مربوط به آن

{

unsigned simlen = simples.size();

for(unsigned i = 0; i < simlen; i++)

simples[i] -> reserved_bins = tree -> GetBin(simples[i]);

}

vector<bool> GetCode(char ch) // به دست آوردن کد هر کاراکتر به صورت آرایه

{

unsigned simlen = simples.size();

for(unsigned i = 0; i < simlen; i++)

{

if(simples[i] -> reserved_char == ch)

return simples[i] -> reserved_bins;

}

cout<< "Error in GetCode()" "\n"; // protecting code

vector<bool> ret;

return ret;

}

void ConvertText() // تبدیل رشته با کد هافمن

{

unsigned size = text.size();

for(unsigned i = 0; i < size; i++)

{

vector<bool> v = GetCode(text[i]);

unsigned v_len = v.size();

for(unsigned j = 0; j < v_len; j++)

bins.push_back(v[j]);

}

}

//------------------------------------------------------------------

public:

void Print() // چاپ اطلاعات

{

cout<< "original text:\n \"" << text << "\"" "\n";

cout<< "\n" "Code Table:" "\n\n";

unsigned simlen = simples.size();

for(unsigned i = 0; i < simlen; i++)

{

char ch = simples[i] -> reserved_char;

vector<bool> v = simples[i] -> reserved_bins;

cout<< ch << " : ";

unsigned v_len = v.size();

for(unsigned j = 0; j < v_len; j++)

cout<< v[j];

cout<< "\n";

}

cout<< "\n\n" "zipped text bits: " "\n\n";

unsigned len = bins.size();

for(unsigned i = 0; i < len; i++)

cout<< bins[i];

}

Compress(string text): text(text) // سازنده

{

GetTree();

FindBinCodes();

ConvertText();

}

~Compress() // نابود کنندۀ درخت های ایجاد شده

{

unsigned len = created_bintrees.size();

for(unsigned i = 0; i < len; i++)

delete created_bintrees[i];

}

};

int main()

{

string text = "aabaaxyxbaxaa"; // رشته ای که قرار است فشرده شود

Compress com(text);

com.Print();

_getch();

}

Output:

original text:

"aabaaxyxbaxaa"

Code Table:

a : 1

b : 011

x : 00

y : 010

zipped text bits:

1101111000100001110011