Cách nén dữ liệu bằng mã hóa Huffman: 10 bước

Mục lục:

Cách nén dữ liệu bằng mã hóa Huffman: 10 bước
Cách nén dữ liệu bằng mã hóa Huffman: 10 bước

Video: Cách nén dữ liệu bằng mã hóa Huffman: 10 bước

Video: Cách nén dữ liệu bằng mã hóa Huffman: 10 bước
Video: Đi lấy NHÂN MỤN, nam thanh niên tá hoả nặn ra NẮM TÓC bên trong khiến nhân viên KHIẾP SỢ | TB Trends 2024, Tháng Ba
Anonim

Thuật toán của Huffman được sử dụng để nén hoặc mã hóa dữ liệu. Thông thường, mỗi ký tự trong tệp văn bản được lưu trữ dưới dạng tám bit (chữ số, 0 hoặc 1) ánh xạ tới ký tự đó bằng cách sử dụng mã hóa được gọi là ASCII. Tệp được mã hóa Huffman phá vỡ cấu trúc 8 bit cứng nhắc để các ký tự được sử dụng phổ biến nhất được lưu trữ chỉ trong một vài bit ('a' có thể là "10" hoặc "1000" chứ không phải là ASCII, là "01100001"). Do đó, các ký tự ít phổ biến nhất thường sẽ chiếm nhiều hơn 8 bit ('z' có thể là "00100011010"), nhưng vì chúng rất hiếm khi xảy ra, nói chung, mã hóa Huffman tạo ra một tệp nhỏ hơn nhiều so với bản gốc.

Các bước

Phần 1/2: Mã hóa

Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 1
Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 1

Bước 1. Đếm tần số của từng ký tự trong tệp cần mã hóa

Bao gồm một ký tự giả để đánh dấu phần cuối của tệp - điều này sẽ quan trọng sau này. Hiện tại, hãy gọi nó là EOF (cuối tệp) và đánh dấu nó có tần suất là 1.

Ví dụ: nếu bạn muốn mã hóa tệp văn bản là "ab ab cab", bạn sẽ có 'a' với tần số 3, 'b' với tần số 3, '' (dấu cách) với tần số 2, 'c' với tần số 1 và EOF với tần số 1

Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 2
Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 2

Bước 2. Lưu trữ các ký tự dưới dạng các nút cây và đưa chúng vào một hàng đợi ưu tiên

Bạn sẽ xây dựng một cây nhị phân lớn với mỗi ký tự là một chiếc lá, vì vậy bạn nên lưu trữ các ký tự ở định dạng sao cho chúng có thể trở thành các nút của cây. Đặt các nút này vào một hàng đợi ưu tiên với tần suất của mỗi ký tự là mức độ ưu tiên của nút đó.

  • Cây nhị phân là một định dạng dữ liệu trong đó mỗi phần dữ liệu là một nút có thể có tối đa một cha và hai con. Nó thường được vẽ như một cây phân nhánh, do đó có tên.
  • Hàng đợi là một tập hợp dữ liệu được đặt tên phù hợp, trong đó thứ đầu tiên đi vào hàng đợi cũng là thứ đầu tiên xuất hiện (như xếp hàng đợi). Trong hàng đợi ưu tiên, dữ liệu được lưu trữ theo thứ tự ưu tiên của chúng, vì vậy điều đầu tiên xuất hiện là điều cấp thiết nhất, điều có mức độ ưu tiên nhỏ nhất, thay vì điều đầu tiên được xếp vào hàng.
  • Trong ví dụ "ab ab cab", hàng đợi ưu tiên của bạn sẽ giống như sau: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 3
Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 3

Bước 3. Bắt đầu xây dựng cây của bạn

Loại bỏ (hoặc xếp hàng) hai thứ cấp thiết nhất khỏi hàng đợi ưu tiên. Tạo một nút cây mới làm nút cha của hai nút này, lưu trữ nút đầu tiên làm nút con bên trái và nút thứ hai làm nút con bên phải của nó. Mức độ ưu tiên của nút mới phải là tổng các mức độ ưu tiên của nút con của nó. Sau đó xếp nút mới này vào hàng đợi ưu tiên.

Hàng đợi ưu tiên bây giờ trông giống như sau: {'': 2, nút mới: 2, 'a': 3, 'b': 3}

Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 4
Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 4

Bước 4. Hoàn thành việc xây dựng cây của bạn:

lặp lại bước trên cho đến khi chỉ có một nút trong hàng đợi. Lưu ý rằng ngoài các nút bạn đã tạo cho các ký tự và tần số của chúng, bạn cũng sẽ định vị lại, chuyển thành cây và xếp hàng lại các nút cha, các nút đã là cây của chính nó.

  • Khi bạn hoàn thành, nút cuối cùng trong hàng đợi sẽ là gốc của cây mã hóa, với tất cả các nút khác sẽ phân nhánh từ nó.
  • Các ký tự được sử dụng thường xuyên nhất sẽ là các lá gần ngọn cây nhất, trong khi các ký tự ít được sử dụng sẽ được đặt ở dưới cùng của cây, xa gốc hơn.
Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 5
Nén dữ liệu bằng cách sử dụng mã hóa Huffman Bước 5

Bước 5. Tạo một bản đồ mã hóa. Đi bộ qua cây để tiếp cận từng nhân vật. Mỗi khi bạn truy cập nút con bên trái của nút, đó là '0'. Mỗi khi bạn truy cập nút con bên phải, đó là '1'. Khi bạn đến một ký tự, hãy lưu ký tự đó với dãy số 0 và 1 mà nó đã mất để đến đó. Trình tự này là những gì ký tự sẽ được mã hóa như trong tệp nén. Lưu trữ các ký tự và trình tự của chúng trong một bản đồ.

  • Ví dụ, bắt đầu từ gốc. Truy cập nút con bên trái của gốc, sau đó truy cập nút con bên trái của nút đó. Vì nút bạn đang ở hiện tại không có bất kỳ nút con nào, bạn đã đạt đến một ký tự. Đây là ' '. Vì bạn đã đi bộ sang trái hai lần để đến đây nên mã hóa cho '' là "00".
  • Đối với cây này, bản đồ sẽ giống như sau: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Nén dữ liệu bằng mã hóa Huffman Bước 6
Nén dữ liệu bằng mã hóa Huffman Bước 6

Bước 6. Trong tệp đầu ra, bao gồm bản đồ mã hóa làm tiêu đề

Điều này sẽ cho phép tệp được giải mã.

Nén dữ liệu bằng mã hóa Huffman Bước 7
Nén dữ liệu bằng mã hóa Huffman Bước 7

Bước 7. Mã hóa tệp

Đối với mỗi ký tự trong tệp được mã hóa, hãy viết chuỗi nhị phân mà bạn đã lưu trữ trong bản đồ. Khi bạn đã mã hóa xong tệp, hãy đảm bảo thêm EOF vào cuối.

  • Đối với tệp "ab ab cab", tệp được mã hóa sẽ có dạng như sau: "1011001011000101011011".
  • Các tệp được lưu trữ dưới dạng byte (8 bit hoặc 8 chữ số nhị phân). Bởi vì thuật toán Mã hóa Huffman không sử dụng định dạng 8-bit, các tệp được mã hóa thường sẽ không có độ dài là bội số của 8. Các chữ số còn lại sẽ được điền bằng 0. Trong trường hợp này, hai số 0 sẽ được thêm vào cuối tệp, trông giống như một khoảng trắng khác. Đây có thể là một vấn đề: làm thế nào bộ giải mã biết khi nào dừng đọc? Tuy nhiên, vì chúng tôi đã bao gồm một ký tự cuối tệp, bộ giải mã sẽ đến điều này và sau đó dừng lại, bỏ qua bất kỳ thứ gì khác được thêm vào sau đó.

Phần 2 của 2: Giải mã

Nén dữ liệu bằng mã hóa Huffman Bước 8
Nén dữ liệu bằng mã hóa Huffman Bước 8

Bước 1. Đọc trong tệp được mã hóa Huffman

Đầu tiên, hãy đọc tiêu đề, đây phải là bản đồ mã hóa. Sử dụng điều này để xây dựng cây giải mã giống như cách bạn đã tạo cây mà bạn đã sử dụng để mã hóa tệp. Hai cây phải giống hệt nhau.

Nén dữ liệu bằng mã hóa Huffman Bước 9
Nén dữ liệu bằng mã hóa Huffman Bước 9

Bước 2. Đọc từng chữ số trong hệ nhị phân

Di chuyển cây khi bạn đọc: nếu bạn đọc bằng '0', hãy chuyển đến nút con bên trái của nút bạn đang ở và nếu bạn đọc bằng '1', hãy chuyển đến nút con bên phải. Khi bạn đến một lá (một nút không có bất kỳ nút nào con), bạn đã đến một ký tự. Ghi ký tự vào tệp đã giải mã.

Do cách các ký tự được lưu trữ trong cây, các mã cho mỗi ký tự có thuộc tính tiền tố, do đó không có mã hóa nhị phân của ký tự nào có thể xảy ra khi bắt đầu mã hóa của ký tự khác. Mã hóa cho mỗi ký tự là hoàn toàn duy nhất. Điều này làm cho việc giải mã dễ dàng hơn nhiều

Nén dữ liệu bằng mã hóa Huffman Bước 10
Nén dữ liệu bằng mã hóa Huffman Bước 10

Bước 3. Lặp lại cho đến khi bạn đạt EOF

Xin chúc mừng! Bạn đã giải mã tệp.

Đề xuất: