Trang chủ » Giải thuật nén Huffman (Phần 1)
Thuật toán

Giải thuật nén Huffman (Phần 1)

cplusplus

Xin chào mọi người!

Lâu lắm rồi mình mới có thể động vào blog (xin lỗi mọi người thật nhiều 🙁 ), 1 phần vì mình có bài tập, 1 phần khác vì mình đang có 1 project riêng cho bản thân (sắp tiết lộ 😀 ), nên thời gian này mình ít lên blog được. Mong các bạn thông cảm (nhắm mắt) bỏ qua cho :D.

Với mỗi máy tính thông dụng thì tất nhiên ai cũng có 1 phần mềm là “WinRAR”. Vậy đã bao giờ các bạn tự hỏi rằng nó nén dữ liệu bằng cách nào mà thông minh quá, chỉ vài thao tác là nén dc cả trăm MB? Sau đây mình xin liệt kê 1 thuật toán cũng rất hay, đó là nén Huffman.

Ở bài viết này mình xin sử dụng nén Huffman tĩnh, phần sau mình sẽ nói về nén Huffman động 😀

1. Khái niệm

Nén Huffman tĩnh là 1 dạng nén không mất dữ liệu (lossless data). Nó dựa trên bảng tần suất các kí tự xuất hiện để xây dựng mã nhị phân cho các kí tự đó sao cho số bit là nhỏ nhất.

Giải thuật được đề xuất bởi David A. Huffman, và công bố vào năm 1952.

David A. Huffman
David A. Huffman

Để mã hoá các kí tự đó, ta thay các kí tự bằng mã nhị phân chẳng hạn như bộ mã ASCII mã hoá được 256 kí tự (ví dụ như kí tự ‘A‘ là 1000001, trong khi ‘a‘ lại là 1100001). Với cách mã hoá này, ta phải dùng 8 bit để biểu diễn 1 ký tự, rất là tiêu tốn bộ nhớ. Ngoài ra, khi mã hoá dữ liệu có thể không cần dùng hết 256 kí tự, và trong chuỗi có thể có những kí tự xuất hiện rất nhiều lần, có những kí tự thì lại xuất hiện 1 2 lần,…

Cùng nhau phân tích thử chuỗi trên nhé!
Cùng nhau phân tích thử chuỗi trên nhé!

Ở chuỗi trên, ta phân tích ra như sau: s(8), e(7), space(5), h(4), l(4), a(2), b(1), y(1), o(1), r(1), dot(1).

Ta nhận ra rằng, kí tự ‘s‘ xuất hiện tận 8 lần, nhưng kí tự ‘r‘ chỉ xuất hiện đúng 1 lần. Nếu ta dùng 8 bit cố định để biểu diễn thì rất … mệt :v. Vì vậy nên ta có thể biểu diễn bằng số bit “linh động” hơn, kí tự nào xuất hiện nhiều thì dùng bit ít, và ngược lại.

Tuy nhiên 1 vấn đề phát sinh là, nếu ta mã hoá với số bit linh động trên thì làm thế nào ta có thể phân biệt được dãy bit nào biểu diễn cho kí tự nào? Ta có thể dùng dấu phẩy để ngăn cách giữa các bit, hoặc sử dụng kí hiệu nào đó. Nhưng nếu vậy thì dấu phẩy sẽ chiếm 1 vùng bộ nhớ đáng kể trong dãy. Vì vậy nên ta có khái niềm về mã tiền tố.

2. Mã tiền tố (prefix-free binary code)

Mã tiền tố là bộ mã của 1 tập hợp các kí hiệu sao cho mỗi kí hiệu không là tiền tố (phần đầu) của các kí hiệu khác trong tập hợp. Ta có thể hiểu mã hoá với độ dài không đổi cũng là mã tiền tố.

Ví dụ: Giả sử ta mã hoá từ “ARRAY

Ta nhận thấy trong dãy có các kí tự ‘A‘, ‘R‘, ‘Y

  • Nếu mã hoá bằng dãy bit có độ dài cố định, ta phải dùng ít nhất 2 bit cho 1 ký tự (‘A‘ => 00, ‘R‘ => 01, ‘Y‘ => 11). Khi đó dãy bit sẽ là 0001010010. Để giải mã, ta chỉ cần đọc 2 bit một và đối chiếu với bảng mã.
  • Nếu mã hoá ‘A‘ => 0, ‘R‘ => 01, ‘Y‘ => 11 thì bộ mã này không là mã tiền tố (vì ‘R‘ => 01 có thể hiểu là kí tự ‘A‘ kèm theo bit 1). Để mã hoá, ta cần phải đặt các dấu phẩy vào giữa (0, 01, 01, 0, 11).
  • Nếu mã hoá ‘A‘ => 0, ‘R‘ => 10, ‘Y‘ => 11 thì bộ mã này là mã tiền tố. Lúc đó dãy bit sẽ là 01010011.

Ta biểu diễn mã tiền tố bằng cây nhị phân như sau:

Biểu diễn bằng cây nhị phân.
Biểu diễn bằng cây nhị phân.

Với mỗi kí tự, ta có thể biểu diễn bằng dãy bit như sau: khi đi từ gốc (root) tới lá (leaf) chứa kí tự đó, nếu đi qua cạnh trái thì ta thêm số 0 vào dãy bit, nếu đi qua cạnh phải thì thêm số 1 vào. Ở cây nhị phân trên, ‘A‘ => 0, ‘R‘ => 10, ‘Y‘ => 11.

Ta có thể thấy, với cách biểu diễn thông thường, ta mất khoảng 40 bits (5 bytes) để biểu diễn chuỗi “ARRAY“. Tuy nhiên với mã độ dài cố định (0001010010), ta mất khoảng 10 bits, tiết kiệm được 75%. Với mã tiền tố (01010011), ta mất khoảng 8 bits, tiết kiệm được lên tới 80%.

3. Giải thuật Huffman tĩnh

Giả sử ta có dãy như sau: s = “AAAAAABCCCCCCDDEEEEE

Tần suất: A(6), B(1), C(6), D(2), E(5). Biểu diễn thông thường: sizeof(s) = (6 + 1 + 6 + 2 + 5)*8 = 160 bits. Tuy nhiên, nếu ta áp dụng mã tiền tố ở trên, ta sẽ thu được: ‘A‘ => 00, ‘C‘ => 01, ‘E‘ => 10, ‘B‘ => 110, ‘D‘ => 111. Vì vậy lúc này: sizeof(s’) = 6 * 2 + 1 * 3 + 6 * 2 + 2 * 3 + 5 * 2 = 43 bits.

Ta có thuật toán như sau:

[B1] Duyệt tập tin => Lập bảng thống kê tần số xuất hiện của các kí tự.

[B2] Xây dựng cây Huffman dựa vào bảng tần số đã lập ở trên.

[B3] Phát sinh bảng mã bit cho từng kí tự tương ứng.

[B4] Duyệt tập tin lần 2 => Thay thế các kí tự trong tập tin bằng mã bit tương ứng.

[B5] Lưu lại cây Huffman để giải nén.

Cây Huffman cho trường hợp trên.
Cây Huffman cho trường hợp trên.

Thuật toán để tạo cây Huffman:

[B1] Sắp xếp bảng tần số các ký tự.

[B2] Chọn 2 phần tử đầu để tạo node x, y có trọng số là tần số. Tạo node z là cha của node x, y có trọng số bằng tổng trọng số của 2 node con.

[B3] Loại bỏ 2 node x, y ra khỏi bảng, sau đó thêm node z vào sao cho bảng tần số vẫn tăng/giảm dần.

[B4] Lặp lại B1-3 sao cho chỉ còn 1 phần tử trong bảng.

Ta cần xây dựng 2 struct:

struct Node
{
	char c;
	int freq;
	Node* left;
	Node* right;
	Node()
	{
		c = '\0';
		freq = -1;
		left = NULL;
		right = NULL;
	}
};

// Struct này có công dụng lưu trữ bit đã mã hoá theo mã tiền tố
struct Bit
{
	char c;
	string bit;
};

Xây dựng class để nén:

class HuffmanCompression
{
private:
	string data; // Lưu trữ chuỗi đọc vào từ file
	Node* root;
	vector<Bit> bit; // Lưu trữ mã bit tương ứng với ký tự ta xét
	string bitTree; // Cây Huffman được mã hoá để lưu vào file
	void convertTree();
	void visit(Node* curr, string bit);
	void generateTree(Node* curr);
public:
	HuffmanCompression() { bitTree = ""; }
	HuffmanCompression(string filePath);
	void compression(string outputPath);
};

Tiếp theo ta cần lập bảng tần số để phát sinh cây Huffman:

void HuffmanCompression::convertTree()
{
	vector<Node*> tree;
	// Lập bảng tần số
	// Duyệt hết chuỗi để kiểm tra
	for (int i = 0; i < data.length(); i++)
	{
		bool existed = false;
		// Duyệt trong bảng, nếu ký tự ta xét đã có trong bảng thì ++freq
		for (int j = 0; j < tree.size(); j++) 
                {
			if (tree[j]->c == data[i])
			{
				tree[j]->freq++;
				existed = true;
				break;
			}
		}
		// Ngược lại thì thêm ký tự đó vào bảng
		if (!existed)
		{
			Node* node = new Node();
			node->c = data[i];
			node->freq = 1;
			tree.push_back(node);
		}
	}

	// Tiếp theo là sắp xếp lại bảng tần số
	for (int i = 0; i < tree.size() - 1; i++)
	{
		for (int j = i + 1; j < tree.size(); j++)
                {
                        if (tree[i]->freq > tree[j]->freq)
			{
				Node* temp = tree[i];
				tree[i] = tree[j];
				tree[j] = temp;
			}
		}
	}
	
	while (true)
	{
		// Tạo node z có con là 2 phần tử đầu trong bảng tần số
		Node* tmp = new Node();
		tmp->left = tree[0];
		tmp->right = tree[1];
		tmp->freq = tmp->left->freq + tmp->right->freq;

		// Xoá 2 phần tử đầu trong bảng tần số
		tree.erase(tree.begin(), tree.begin() + 2);
		tree.resize(tree.size() + 1);

		// Nếu chỉ còn đúng 1 phần tử
		if (tree.size() == 1)
		{
			tree[0] = tmp;
			break;
		}
		else
		{
			// Chèn vị trí node z vào bảng tần số sao cho phù hợp
			// Ở đây mình sắp xếp giảm dần
			for (int j = 0; j < tree.size() - 1; j++)
                        {
                                bool isMax = true;
                                if (tree[j]->freq > tmp->freq)
				{
					for (int k = tree.size() - 1; k > j; k--)
					{
						tree[k] = tree[k - 1];
					}
					tree[j] = tmp;
					isMax = false;
					break;
				}
				if (isMax) tree[tree.size() - 1] = tmp;
			}
		}
	}

	// Cuối cùng ta thu được cây Huffman là phần tử duy nhất còn lại trong bảng tần số
	root = tree[0];
}

Ngoài ra, ta còn phải mã hoá cây Huffman thành dãy bit để lưu vào file.

  • Nếu node là lá: Xuất ra bit ‘1’ và 8 bit ký tự trong lá đó.
  • Nếu node không là lá: Xuất ra bit ‘0’. Sau đó gọi đệ quy đến 2 node con bên trong.

Với trường hợp chuỗi “AAAAAABCCCCCCDDEEEEE“, ta xây dựng cây Huffman thì chuỗi bit của cây sẽ là: 0001B1D1E01A1C (0001010000101010001001010001010101000001101000011).

void HuffmanCompression::generateTree(Node* curr)
{
	if (curr != NULL)
	{
		// Nếu node là lá
		if (curr->left == NULL && curr->right == NULL)
		{
			bitTree += '1';
			bitset<8> bitSq(curr->c);
			bitTree += bitSq.to_string();
		}
		// Ngược lại
		else
		{
			bitTree += '0';
			generateTree(curr->left);
			generateTree(curr->right);
		}
	}
}

Từ cây Huffman đã tạo, ta phát sinh bảng mã bit cho các kí tự:

void HuffmanCompression::visit(Node* curr, string bit)
{
	if (curr != NULL)
	{
		if (curr->left == NULL || curr->right == NULL)
		{
			Bit cBit;
			cBit.c = curr->c;
			cBit.bit = bit;
			this->bit.push_back(cBit);
		}
		else
		{
			visit(curr->left, bit + "0");
			visit(curr->right, bit + "1");
		}
	}
}

Cuối cùng, ta có 1 method compression(string outputPath) để ghi kết quả ra file:

// Hàm dùng để chuyển chuỗi 8 bit thành ký tự tương ứng
char convertBitToChar(string input)
{
	char c = 0;
	for (int i = 0; i < input.length(); i++)
	{
		c = (c << 1) | (input[i] - 48);
	}
	return c;
}

// Hàm dùng để chuyển chuỗi bit sang chuỗi ký tự tương ứng
std::string convertBitStringToCharString(string input)
{
	string result = "";
	while (input.length() > 0)
	{
		string temp;
		if (input.length() > 8)
		{
			temp = input.substr(input.length() - 8, 8);
			input = input.erase(input.length() - 8, 8);
		}
		else
		{
			temp = input;
			if (temp.length() > 8) temp = "0" + temp;
			input = "";
		}
		result = convertBitToChar(temp) + result;
	}
	return result;
}

void HuffmanCompression::compression(string outputPath)
{
	this->convertTree();
	this->visit(root, "");
	this->generateTree(root);

	// Thay thế các kí tự trong chuỗi data thành mã bit tương ứng trong bảng tần số
	string bitSq = "";
	for (int i = 0; i < data.length(); i++)
	{
		for (int j = 0; j < bit.size(); j++)
		{
			if (data[i] == bit[j].c)
			{
				bitSq += bit[j].bit;
				break;
			}
		}
	}

	// Mã hoá bit cây Huffman và bit data thành ký tự để lưu vào file
	string main = convertBitStringToCharString(bitTree + bitSq);
	int realBit = 0, sizeBit = (bitTree + bitSq).length();

	// Do độ dài bit của bitTree và bitSq không là bội của 8
	// Ta cần xác định có bao nhiêu bit '0' được thêm vào chuỗi bit bitTree và bitSq
	while (realBit < sizeBit) realBit += 8;
	char addBit = realBit - sizeBit; 
	// Ta cần phải xác định số lượng ký tự có trong chuỗi 
	char bitNum = this->bit.size();

	ofstream fo(outputPath);
	fo << (char)bitNum << (char)addBit << main;
	fo.close();
}

4. Giải nén

Giải thuật để dịch ngược chuỗi bit dựa vào cây Huffman:

Đi từ gốc cây Huffman, đọc từng bit từ tập tin đã nén:

  • Nếu là bit 0: ta rẽ sang nhánh trái
  • Nếu là bit 1: ta rẽ sang nhánh phải
  • Nếu đến node lá: xuất ra kí tự tại node lá này.

Lặp cho đến khi nào hết dãy bit của tập tin trên.

Ví dụ: Chuỗi bit đã mã hoá: 0000000000001100101010101011111111010101010

huffman-tree-example
Cây Huffman cho ví dụ trên.

Ta cần xây dựng class để giải nén:

class HuffmanExtraction
{
private:
	string bitTree;
	string data;
	Node* root;
	void generateTree(Node* curr);
	char visit(Node* curr);
public:
	HuffmanExtraction() { root = new Node(); }
	HuffmanExtraction(string filePath);
	void extraction(string outputPath);
};

Để đọc 1 file đã mã hoá:

// Constructor của class trên
HuffmanExtraction::HuffmanExtraction(string filePath)
{
	root = new Node();
	string bitSequence = "";
	ifstream fi(filePath, ios::binary);
	char c;
	// Ta không thể đọc 1 lần toàn bộ kí tự trong file
	// Vì có thể đâu đó trong file có chứa kí tự '\0'
	// Nếu ta cố tình đọc thì chuỗi bitSequence sẽ không thể lưu hết được
	// Vì vậy ta cần phải đọc từng ký tự trong file
	while (fi >> noskipws >> c)
	{
		bitset<8> bit(c);
		bitSequence += bit.to_string();
	}
	
	// Lấy ra số ký tự có trong chuỗi mã hoá
	char numChar = convertBitToChar(bitSequence.substr(0, 8));
	bitSequence.erase(0, 8);

	// Lấy ra số bit '0' được thêm vào như phía trên mình đề cập
	char addBit = convertBitToChar(bitSequence.substr(0, 8));
	bitSequence.erase(0, 8);

	// Bỏ đi các bit '0' thừa
	bitSequence.erase(0, addBit);

	// Số bit cần lấy tuân theo công thức dưới đây
	int sizeBit = 10 * numChar - 1;
	bitTree = bitSequence.substr(0, sizeBit);
	bitSequence.erase(0, sizeBit);
	data = bitSequence;
	fi.close();
}

Kế tiếp, ta cần phải tái xây dựng lại cây Huffman dựa trên chuỗi bitTree đã có:

  • Nếu là bit ‘0’, ta xây dựng 2 node con left và right, và gọi đệ quy đến node con đó.
  • Nếu là bit ‘1’, ta đọc 8 bit tiếp theo và lưu vào node lá.
void HuffmanExtraction::generateTree(Node* curr)
{
	while (bitTree.length() > 0)
	{
		// Nếu là node lá
		if (curr->left != NULL && curr->right != NULL) return;

		Node* node = new Node();
		if (bitTree[0] == '0')
		{
			bitTree.erase(0, 1);
			// Ta cần phải xác định xem mình nên gọi đệ quy đến node trái hay phải
			if (curr->left == NULL)
			{
				curr->left = node;
				generateTree(curr->left);
			}
			else
			{
				curr->right = node;
				generateTree(curr->right);
			}
		}
		
		// Nếu gặp bit '1', ta get 8 bit kế tiếp
		else
		{
			string temp = bitTree.substr(1, 8);
			bitTree.erase(0, 9);
			
			// Hàm char convertBitToChar(string temp) dùng để xuất ra ký tự tương ứng với chuỗi bit
			node->c = convertBitToChar(temp);
			if (curr->left == NULL) curr->left = node;
			else curr->right = node;
		}
	}
}

Kế tiếp, ta duyệt chuỗi data dựa vào cây Huffman theo giải thuật mình đã viết ở trên

char HuffmanExtraction::visit(Node* curr)
{
	if (curr->left == NULL && curr->right == NULL)
	{
		return curr->c;
	}
	if (data[0] == '0')
	{
		data.erase(0, 1);
		visit(curr->left);
	}
	else
	{
		data.erase(0, 1);
		visit(curr->right);
	}
}

Cuối cùng là ghi ra file

void HuffmanExtraction::extraction(string outputPath)
{
	this->generateTree(root);
	root = root->left;
	string result = "";
	while (data.length() > 0) result += this->visit(root);
	ofstream fo(outputPath);
	fo << result;
	fo.close();
}

Vậy là ta đã xây dựng thành công giải thuật nén Huffman tĩnh. Tuy nhiên ta nhận ra giải thuật này có 1 khuyết điểm là phải duyệt 2 lần file cần nén, như vậy sẽ tốn chi phí nhiều hơn. Ngoài ra ta còn phải lưu trữ cây Huffman trong dữ liệu nén, như vậy sẽ tăng kích thước file nén. Ở phần tiếp theo, mình sẽ hướng dẫn về nén Huffman động (Adaptive Huffman Compression), sẽ khắc phục được những nhược điểm trên.

Trên đây là bài viết về nén Huffman tĩnh, cảm ơn các bạn đã chú ý theo dõi! Hẹn gặp lại ở những phần tiếp theo!

About the author

Võ Hoài Sơn

Tính tình bất định
Chọc vào là bịnh
Rất yêu lập trình
Luôn code hết mình
Mình hiện đang là sinh viên của trường ĐH Khoa học tự nhiên TPHCM. Bản thân rất thích code, kiêm luôn cả mần thơ nên thường hơi hâm hâm dở dở. Ngoài ra chém gió, chém chuối, chém trái cây các kiểu cũng là sở trường của mình. Rất mong được làm quen với các bạn :D

Add Comment