Phát triển tiện ích nén dữ liệu dựa trên mã Huffman bằng Haskell

Triển khai chương trình nén dữ liệu sử dụng mã hóa Huffman

• Mã Huffman là gì?
  • Thực hiện nén dữ liệu bằng cách ánh xạ mỗi ký tự thành một chuỗi bit duy nhất
  • Các ký tự xuất hiện thường xuyên được ánh xạ thành chuỗi bit ngắn, còn các ký tự xuất hiện hiếm hơn được ánh xạ thành chuỗi bit dài
  • Ví dụ: với chuỗi aaab, a được ánh xạ thành 1, b được ánh xạ thành 0, nên được nén thành 1110

Mã không tiền tố

• Mã không tiền tố là gì?
  • Đảm bảo không có từ mã nào là tiền tố của một từ mã khác
  • Ví dụ: với aaabc, a được ánh xạ thành 1, b thành 00, c thành 01, nên được nén thành 1110001

Tạo mã không tiền tố

• Cách tạo mã không tiền tố
  • Đặt tất cả ký tự vào các lá của một cây nhị phân đầy đủ
  • Gán nhãn nhánh trái là 1, nhánh phải là 0
  • Đường đi từ gốc đến lá mô tả từ mã của từng ký tự

Viết bộ mã hóa

• Định nghĩa kiểu

  • Định nghĩa các kiểu Bit, Code, FreqMap, CodeMap, Weight, HTree
  • HTree gồm Leaf và Fork

• Hàm mã hóa

  • Hàm chuyển chuỗi thành bit
  • Sử dụng FreqMap để tính tần suất của từng ký tự, rồi tạo cây Huffman dựa trên đó
  • Tạo từ mã cho từng ký tự từ cây Huffman

• Hàm giải mã

  • Hàm chuyển bit về chuỗi gốc
  • Sử dụng cây Huffman để giải mã tuần tự các bit

Tích hợp với tệp nhị phân

• Mã hóa dữ liệu nhị phân
  • Dùng mô-đun Data.ByteString.Char8 để đọc byte dưới dạng ký tự
  • Sử dụng bộ mã hóa văn bản để mã hóa dữ liệu nhị phân

Tuần tự hóa

• Hàm tuần tự hóa
  • Chuyển FreqMap và các bit thành byte thực tế rồi lưu vào tệp
  • Dùng monad Put để tạo ByteString hiệu quả

Giải tuần tự hóa

• Hàm giải tuần tự hóa
  • Chuyển dữ liệu đọc từ tệp thành FreqMap và các bit
  • Dùng monad Get để giải tuần tự hóa FreqMap

Tích hợp toàn bộ mã

• Hàm nén và giải nén tệp
  • Hàm compress: đọc tệp, tạo bản đồ tần suất, mã hóa dữ liệu rồi lưu thành tệp nén
  • Hàm decompress: đọc tệp nén, giải mã dữ liệu rồi lưu lại thành tệp gốc

Các điểm cải tiến

• Đa luồng

  • Giải mã song song các phần của tệp
  • Thêm một bảng chỉ định ranh giới từng phần và kích thước giải mã dự kiến để cho phép xử lý song song

• Mã hóa một lần duy nhất

  • Vừa tạo bản đồ tần suất theo thời gian thực vừa mã hóa
  • Không cần đưa bản đồ tần suất vào phần đầu tệp

• Mã Huffman chuẩn tắc

  • Giải mã với độ phức tạp thời gian O(1) bằng cách lập chỉ mục vector thay vì duyệt cây

• Tạo mã nhanh hơn

  • Nếu thử mã hóa một lần duy nhất, cần tăng tốc độ tạo code map

Ý kiến của GN⁺

• Ưu điểm của mã hóa Huffman

  • Cho phép nén dữ liệu hiệu quả bằng cách ánh xạ các ký tự xuất hiện thường xuyên thành chuỗi bit ngắn
  • Có thể xử lý dữ liệu lớn trong khi vẫn giảm thiểu mức sử dụng bộ nhớ

• Ưu điểm của Haskell

  • Có thể viết mã theo hướng mô-đun bằng cách tận dụng ưu điểm của lập trình hàm
  • Có thể tối ưu hóa việc sử dụng bộ nhớ thông qua đánh giá lười

• Các dự án có chức năng tương tự

  • Có nhiều công cụ nén dữ liệu như gzip, bzip2
  • Điều quan trọng là so sánh ưu và nhược điểm của từng công cụ để chọn công cụ phù hợp

• Những điều cần cân nhắc khi áp dụng công nghệ mới

  • Cần chọn thuật toán phù hợp dựa trên hiệu năng và mức sử dụng bộ nhớ
  • Có thể nâng cao hiệu quả bằng cách áp dụng các kỹ thuật tối ưu như mã hóa một lần duy nhất

[GN⁺]

Ý kiến Hacker News

• Có tồn tại thuật toán in-place dựa trên mảng, giúp giảm nhu cầu cấp phát cây và lần theo con trỏ

  • Khi học cách tiếp cận dựa trên cây ở đại học, tôi đã không biết còn có phương pháp khác
  • Cách tiếp cận bằng cây trực quan và hữu ích, nhưng khi cần xử lý nhiều dữ liệu thật nhanh thì dùng mảng in-place hợp lý hơn
  • Tài liệu tham khảo: "In-Place Calculation of Minimum-Redundancy Codes" (Moffat, Katajainen, 1995)

• Việc nói rằng mã từ không được trở thành tiền tố của mã từ khác là không hoàn toàn chính xác về mặt kỹ thuật

  • Lớp mã có thể giải mã duy nhất là một siêu tập của mã tiền tố
  • Ví dụ, đảo ngược mã tiền tố vẫn có thể được giải mã một cách rõ ràng
  • Mã ví dụ:

    a 1
    b 00
    c 10
    

  • Mã của 'a' là tiền tố của mã của 'c', nhưng nếu xử lý theo chiều ngược lại thì vẫn có thể giải mã rõ ràng

• Tôi thắc mắc liệu có tutorial tương tự nào nói về các tính năng nâng cao hơn khi viết chương trình Haskell hay không, như monad transformer, lens, v.v.

• Khóa học lập trình hàm của Coursera (Scala) có bài tập về mã hóa Huffman tương tự

  • Liên kết: Coursera Scala Functional Programming

• Tôi đã dùng mã Huffman để chạy chương trình macro của bộ xử lý MICMAC với số vi chu kỳ và vi lệnh tối thiểu

  • Tôi đã lập histogram cho các lệnh macro và dựa trên đó viết chương trình microcode giải mã tiến dần
  • Trên thực tế, có lẽ nó sẽ chậm và bất tiện
  • Điểm mạnh của mã Huffman là có thể điều chỉnh độ sâu tiền tố theo phân bố của các giá trị
  • Tôi đã phải xử lý dự đoán nhánh trong mô hình bộ xử lý không vượt quá pipeline

• Thông tin thêm về mã hóa Huffman: Rosetta Code Huffman Coding

• Câu hỏi dành cho các lập trình viên Haskell: hiệu năng của Haskell ra sao đối với những người muốn viết mã đã được tối ưu?

  • Tôi đặc biệt quan tâm đến hiệu năng tính toán số dùng phép toán ma trận và tận dụng SIMD

• Ý kiến cảm ơn vì đã chia sẻ

• Có lỗi đánh máy trong bảng ở phần "Creating prefix-free codes"

  • D phải là '0010' (hiện đang bị ghi nhầm thành '0110')
  • Ngoài ra thì đây là một bài đọc rất hay

• Arithmetic coding tốt hơn ở gần như mọi khía cạnh

  • Có thể triển khai với ít RAM và ít mã hơn
  • Cho tỷ lệ nén và giải nén tốt hơn
  • Dễ cập nhật động xác suất xuất hiện của các ký hiệu khác nhau trong luồng hơn
  • Mã Huffman được dùng vì nó được phát minh trước còn arithmetic coding thì từng bị ràng buộc bởi bằng sáng chế
  • Hiện các bằng sáng chế đã hết hạn, nên nên dùng thiết kế tốt hơn