Thuật toán nén dữ liệu

Nén dữ liệu là phương thức đào thải các biết tin dư thừa trong vấn đề màn trình diễn tài liệu. Nó có rất nhiều vận dụng, nhất là trong vấn đề truyền tin vì chưng góp rút gọn gàng lên tiếng gửi đi. Có các thuật tân oán nén tài liệu và Huffman Coding là một trong những đó. Bài viết này đa số bàn về ý tưởng phát minh của thuật toán thù này.

Bạn đang xem: Thuật toán nén dữ liệu

Mục lục 2. Thuật toán thù Huffman Coding 1. Nén dữ liệu

Hãy xem câu “Hello” được màn trình diễn dưới dạng mã ASCII ra sao nhé:


*
Câu "Hello" được trình diễn bên dưới dạng mã ASCII

Mỗi ký kết trường đoản cú sử dụng 8 bit nhằm màn trình diễn nên tổng số đã sử dụng 64 bit.

Bảng mã ASCII mở rộng dùng 8 bit nhằm màn biểu diễn 256 ký trường đoản cú khác nhau. Trong lúc ấy thông điệp của bọn họ chỉ tất cả 5 ký tự khác biệt, những điều đó thực tiễn chỉ cần sử dụng 3 bit là đủ nhằm phân biệt được 5 ký từ bỏ này.

Bây giờ đồng hồ ta vẫn liệt kê 5 ký kết từ bỏ riêng biệt cùng gán đến nó một mã nhị phân 3 bit riêng biệt. Lúc bấy giờ ta vẫn có thể trình diễn toàn diện thông điệp sẽ nén và dùng bảng giải mã này nhằm Phục hồi thông điệp lúc đầu.


*
Thông điệp đã nén bởi 3-bit coding

bởi thế, chỉ việc cần sử dụng $3 imes 8 = 24$ bit nhằm màn biểu diễn thông điệp trên. Mỗi cam kết trường đoản cú phần đông cần sử dụng đúng một vài lượng bit để biểu diễn, bọn họ Điện thoại tư vấn bí quyết này là fixed-length encoding. Bảng các giá trị được mã hóa cũng là prefix code.

Prefix code rất có thể được khái niệm khó khăn phát âm nhỏng sau (theo Wikipedia):

A prefix code is a type of code system distinguished by its possession of the “prefix property”, which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system. It is trivially true for fixed-length code, so only a point of consideration in variable-length code.

Chúng ta gọi dễ dàng như sau: Prefix code là một tập những quý hiếm mã hóa nhưng không tồn tại bộ phận như thế nào được bắt đầu bởi 1 phần tử không giống.

Với fix-length encoding sử dụng cùng một số lượng bit nhằm mã hóa, những quý giá mã hóa hồ hết khác nhau. Do đó, nó là prefix-code. Dù vậy, các quý hiếm mã hóa cùng với số lượng bit không giống nhau (variable-length encoding) cũng chính là prefix code ví như thỏa mãn tính chất bên trên.

Ví dụ: Tập A = 0, 10, 110, 111 là một trong những prefix code do không tồn tại thành phần nào ban đầu bởi bộ phận không giống. Nhưng B = 0, 10, 110, 101 chưa phải prefix code vày có phần tử 101 bắt đầu bằng thành phần 10.

Prefix code hoàn toàn có thể được màn trình diễn thành cây nhị phân mã hóa. Mỗi cam kết tự đề nghị mã hóa đang nằm tại nút ít lá. Giá trị mã hóa của cam kết từ đó diễn tả bằng đường đi từ bỏ nút gốc cho nút lá đựng ký trường đoản cú đó. Nhánh bên trái miêu tả quý giá 0, nhánh bên bắt buộc diễn đạt giá trị 1.

ví dụ như mang lại chữ “Hellooo!” được mã hóa bằng 3-bit encoding:


*
Cây nhị phân mã hóa 3-bit encoding

Ta lại nhận thấy rằng, bao hàm bộ phận xuất hiện thêm rất nhiều lần, nếu đính thêm cho chúng một mã bao gồm độ dài rẻ độc nhất vô nhị, còn những bộ phận xuất ít hơn rất có thể tất cả mã dài ra hơn nữa, thì vẫn rất có thể tiết kiệm ngân sách và chi phí được không dừng lại ở đó.

Giả sử ta lựa chọn 1 prefix code như ví dụ bên dưới:


*
Câu "Hello" được trình diễn dưới dạng mã ASCII

Rõ ràng chỉ cần dùng 18 bit nhằm trình diễn thông điệp trên. Cách gán mã dựa vào gia tốc mở ra cũng đó là ý tưởng phát minh của thuật toán Huffman coding.


Cây nhị phân mã hóa variable-length encoding
2. Thuật toán thù Huffman Coding

Với phát minh bên trên, thuật toán thù Huffman coding gồm 3 bước:

Bước 1: Đếm gia tốc mở ra của các thành phần trong chuỗi nguồn vào.Cách 2: Xây dựng cây Huffman (cây nhị phân mã hóa).

Xem thêm: Những Sao Hàn Có Khuôn Mặt Vuông Mới Đúng Là Đẹp Như Tượng Tạc

Cách 3: Từ cây Huffman, ta đã có được những giá trị mã hóa. Lúc bấy giờ, ta có thể kiến thiết chuỗi mã hóa trường đoản cú những cực hiếm này.

Quá trình thành lập cây Huffman tất cả công việc sau:

2.1. Tạo danh sách chứa những nút lá bao gồm bộ phận nguồn vào và trọng số nút ít là tần suất xuất hiện của nó.2.2. Từ list này, kéo ra 2 phần tử gồm tần suất lộ diện ít nhất. Sau kia gắn thêm 2 nút ít vừa lấy ra vào một nút nơi bắt đầu new cùng với trọng số là tổng của 2 trọng số ở nút ít vừa kéo ra nhằm tạo thành thành một cây.2.3. Đẩy cây bắt đầu vào lại list.2.4. Lặp lại bước 2 cùng 3 cho đến lúc danh sách chỉ từ 1 nút ít gốc duy nhất của cây.2.5. Nút sót lại chính là nút ít cội của cây Huffman.

Để dễ dàng tiếp xúc các bước tiến hành kiến tạo cây Huffman, chúng ta sẽ cần sử dụng lại ví dụ ở phần trước.

Cách 2.1: Sau lúc đếm gia tốc xuất hiện thêm các thành phần nguồn vào. Chúng ta sản xuất list những nút lá với trọng số là tần suất lộ diện. Danh sách sẽ có được 5 bộ phận như bên dưới.


*
Danh sách thuở đầu

Cách 2.2 cùng 2.3: Chọn 2 nút ít có trọng số thấp duy nhất, sinh sản nút ít gốc bắt đầu gồm trọng số bởi tổng 2 trọng số nút nhỏ. Sau đó gắn 2 nút nhỏ vào nút ít gốc cùng đẩy lại vào list. Danh sách rất cần được màn biểu diễn đặc trưng nhằm rất có thể lấy ra các nút trọng số nhỏ tuổi tuyệt nhất một giải pháp buổi tối ưu duy nhất.


*
Lần 1

Bước 2.4: Lặp lại quá trình 2.2 và 2.3.


*
Lần 2

Bước 2.4: Lặp lại quá trình 2.2 với 2.3.


*
Lần 3

Bước 2.5: Chỉ còn lại 1 nút trong list, nút ít này chính là cây Huffman


*
Cây còn lại vào list

Từ cây Huffman, ta hoàn toàn có thể suy ra các cực hiếm mã hóa của từng phần tử bằng phương pháp phê chuẩn cây nhị phân mã hóa.


Cây nhị phân mã hóa

Ở hầu như bài viết tiếp theo sau, bọn họ sẽ cùng bàn về cách hiện nay phát minh này bởi ngôn từ thiết kế Java.