Giải thuật Huffman + Chương trình Test


Giải thuật Huffman được sử dụng trong việc nén các dữ liệu dạng ký tự bằng việc sử dụng ít bit nhất có thể. Ví dụ như chúng ta có chuỗi “ABC” cần phải mã hóa. Nếu sử dụng mã ASCII với 8 bit cho mỗi ký tự thì với chuỗi “ABC” trên, chúng ta phải sử dụng là: 8 x 3 = 24 bit. Tuy nhiên, nếu sử dụng giải thuật Huffman để nén chuỗi trên thì chúng ta chỉ cần sử dụng: 5 bit. Trong đó, mỗi ký tự sẽ được lưu theo các bit như sau (Không phải là duy nhất, có thể có các cách đánh mã khác cho các ký tự này):

A: 11
B: 10
C: 0

Để biết chi tiết về giải thuật Huffman cũng như cách cài đặt tổng quát thì mọi người có thể xem tại http://vi.wikipedia.org/wiki/M%C3%A3_Huffman. Phần này chúng ta sẽ chỉ tìm cách cài đặt giải thuật Huffman cụ thể bằng ngôn ngữ C#.

Các lớp được sử dụng trong phần này bao gồm:

1. Lớp FreqTable: Đây là lớp được sử dụng để lưu trữ thông tin về tỉ lệ xuất hiện của các ký tự trong chuỗi. Lớp này có constructor nhận một chuỗi để nén và sử dụng một HashTable để lưu dữ liệu

2. Lớp HuffmanTree: Lớp này được dùng để lưu trữ câu Huffman, khai báo của lớp này như sau:

class HuffmanTree : IComparable
{
    public string c;
    public int frequency;
    public HuffmanTree left=null, right=null;
    
    #region IComparable Members

    public int CompareTo(object obj)
    {
        return frequency.CompareTo(((HuffmanTree)(obj)).frequency);
    }

    #endregion
}

– c là biến dùng để lưu trữ ký tự (nếu là nút lá) và để lưu chuỗi kết hợp của hai nút con (nếu là nút trung gian)

– frequency: lưu trữ tỉ lệ xuất hiện của c (nếu là nút là) hoặc lưu tổng số lần xuất hiện của hai nút con (nếu là nút trung gian)

– left, right: hai biến kiểu HuffmanTree được sử dụng để có thể lưu hai nút con, nếu là lá thì left và right sẽ bằng null

– Ngoài ra, lớp này còn thực thi interface IComparable để có thể thực hiện được phép so sánh hai nút (sử dụng khi chúng ta sắp xếp các nút từ nhỏ đến lớn). Việc so sánh này thật ra chính là việc so sánh tỉ lệ xuất hiện của hai nút này.

3. Lớp HuffmanCoding: Lớp này sẽ chứa các lớp kia và cài đặt các phương thức chính như: Encode, Decode. Trong lớp này, chúng ta có sử dụng một List<HuffmanTree> để làm một hàng đợi ưu tiên các nút kiểu HuffmanTree (sau khi thêm một nút vào list này thì chúng ta gọi ngay phương thức Sort để sắp xếp)

Các bước thực hiện trong phương thức Encode(string input) như sau

  • Xây dựng bảng thống kê tỉ lệ xuất hiện của các ký tự trong chuỗi input
  • Duyệt qua danh sách các ký tự có trong chuỗi và thực hiện việc tạo một đối tượng HuffmanTree mới với giá trị c là ký tự đang xét. Sau đó thêm đối tượng này vào hàng đợi ưu tiên
  • Sắp xếp hàng đợi theo thứ tự xuất hiện từ nhỏ đến lớn
  • Trong khi có hơn 1 nút còn nằm trong hàng đợi thì thực hiện các việc sau:

    – Ghép hai phần tử đầu tiên trong hàng đợi thành một phần tử mới

– Bỏ hai phần tử đầu tiên trong hàng đợi ra khỏi hàng đợi và thêm phần tử mới tạo vào hàng đợi

– Sắp xếp lại hàng đợi

  • Cuối cùng, sau khi đã xây dựng xong cây Huffman thì chúng ta sẽ thực hiện duyệt qua mỗi ký tự trong chuỗi input. Với mỗi ký tự đó thì sinh ra mã (codeword) tương ứng bằng cách duyệt cây Huffman từ gốc. Cách duyệt cho ký tự c như sau:

    – khởi tạo chuỗi s là rỗng, gán nút bắt đầu tìm là nút gốc

 

– Kiểm tra nếu thấy nút trái có chứa c thì gán nút tiếp theo là nút trái, đồng thời s = s + “0”. Nếu nút phải chứa c thì gán nút tiếp theo là nút phải, đồng thời s = s + “1”

– Nếu như nút đang xét có left, right bằng null thì đó là nút lá, dừng duyệt và trả về chuỗi s (chính là codeword của c)

Để thực hiện việc decode theo cây Huffman đã xây dựng thì chúng ta thực hiện theo các bước sau (Luôn bắt đầu từ nút gốc):

    • Đọc một ký tự, nếu ký tự này bằng 0 thì đi qua nhánh trái, nếu ký tự này bằng 1 thì đi qua nhánh phải.
    • Nếu nút đang xét là nút lá thì lấy giá trị c của nút đó, gán nút bắt đầu là gốc và quay trở lại bước đầu tiên
    • Nếu nút đang xét không phải nút lá thì quay lại giống như bước đầu (nếu 0, đi qua trái, nếu 1, đi qua phải….)

Chương trình Demo giải thuật Huffman (sử dụng .NET 3.0, C#): https://drive.google.com/open?id=0B5iZPOjOn1osLTdrNjc3NllXbDQ&authuser=0

Update: Mình đã update lại link vì thấy nhiều bạn request file này (do link cũ die)

Tác giả: xuanchien

Tran Xuan Chien. Japan Advanced Institute of Science and Technology - Japan. Senior Developer - NUS Technology.

20 thoughts on “Giải thuật Huffman + Chương trình Test”

  1. Có thể giúp bọn mình thêm một cái nữa được không. Cũng là mã hóa thôi. Mình cần demo thuật mã hóa Shannon và Fano ấy. Đầu vào là dãy các ký tự có xác suất, có tổng bằng 1, đầu ra là từ mã của mỗi ký tự, nhị phân nhé. Sắp xếp trên listview giống như Huffman vậy đó.
    Phần Shannon mình làm ok rồi, chỉ còn phần Fano là đang bó tay!
    Cảm ơn rất nhiều! (khỏi nói chắc bạn biết tôi là ai mà)

  2. a ơi, a còn Code demo này không, link die rồi không tải về được. giờ e đang làm về cái này, nếu còn a gửi qua mail giúp e với, hay cho e cái link mới để tải cũng được, tks a nha..!

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s