Thế này nhé các bạn! Mỗi ngày có hơn 9 tỷ gigabyte (tương đương 9 ngàn petabyte) thông tin lướt qua lướt lại trên Internet đó Con số khủng phết đúng không? Và câu chuyện về cách nén dữ liệu bắt đầu từ một sinh viên chỉ muốn... pass môn thôi, mà lại tạo ra thuật toán đỉnh giúp thu nhỏ dữ liệu mà không làm mất thông tin luôn!
Giờ các nhà nghiên cứu cứ phải đau đầu tìm cách nén data thành những gói nhỏ hơn. Nhiều kỹ thuật xịn xò hiện giờ tập trung vào phương pháp lossy (tức là nén mà để mất thông tin đi một chút). Ví dụ như Google có chiến lược là máy gửi bỏ bớt chi tiết ảnh, rồi máy nhận dùng AI đoán lại phần thiếu Còn Netflix thì hạ chất lượng video xuống nếu phát hiện bạn xem trên màn hình độ phân giải thấp.
Ngược lại, ít người nghiên cứu về chiến lược lossless (không mất dữ liệu) lắm, vì sao ư? Vì nó đã quá hiệu quả rồi! Từ chuẩn ảnh PNG đến PKZip ai cũng xài. Và tất cả nhờ vào một sinh viên muốn vượt qua kỳ thi khó nhằn thôi
Đề bài của thầy Fano
Chuyện là 70 năm trước, giáo sư Robert Fano (1917-2016) của MIT cho sinh viên hai lựa chọn: Làm bài thi cuối kỳ truyền thống HOẶC cải tiến thuật toán nén dữ liệu hàng đầu lúc đó. Plot twist là chính thầy Fano là người tạo ra thuật toán ban đầu đó, nhưng không rõ thầy có nói với học sinh hay không nữa
Thầy Fano đặt bài toán thế này: Thường thì mỗi ký tự được gán một số nhị phân (chỉ có 0 và 1), ví dụ chữ A là 01000001, dấu chấm than là 00100001. Cứ 8 bit = 1 ký tự, dễ hiểu nhưng cực kỳ lãng phí vì chữ phổ biến hay hiếm đều dùng chung số bit
Tiếp cận tốt hơn là giống mã Morse - chữ E thường gặp chỉ cần một dấu chấm, còn chữ Q hiếm hơn thì phải dùng mã dài hơn.
Nhưng mã Morse cũng không hiệu quả lắm vì phải có khoảng dừng giữa các ký tự, nếu không sẽ không biết phân biệt được đâu là đâu!
Phá bỏ sự trùng lặp
Thầy Fano giải quyết vấn đề này bằng cách dùng mã có độ dài khác nhau MÀ KHÔNG cần khoảng trống, với điều kiện không dùng cùng pattern cho cả mã hoàn chỉnh và phần đầu của mã khác. Ví dụ chữ S được gán 01, thì không chữ nào khác có mã bắt đầu bằng 01 nữa - các mã 010, 011, 0101 đều bị cấm luôn!
Kết quả là tin nhắn có thể đọc từ trái sang phải mà không bị nhầm lẫn. Ví dụ: S=01, A=000, M=001, L=1, thì 0100100011 dịch ngay thành "small" (01+001+000+1+1) dù L chỉ 1 số, S là 2 số, còn lại là 3 số mỗi chữ
Để xác định mã, thầy Fano xây dựng cây nhị phân, đặt mỗi chữ cái ở cuối nhánh. Mã được xác định theo đường đi từ trên xuống: rẽ trái thêm 0, rẽ phải thêm 1. Cấu trúc cây giúp tránh trùng lặp dễ dàng - một khi đặt chữ cái rồi thì nhánh đó kết thúc luôn!
Vai trò quan trọng của tần suất
Thầy Fano sắp xếp các chữ cái theo tần suất xuất hiện, rồi gán vào các nhánh sao cho chữ bên trái và bên phải trong mỗi cặp nhánh có tổng tần suất tương đương nhau. Theo cách này, ký tự dùng nhiều sẽ nằm trên nhánh ngắn hơn, ít dày đặc hơn. Chữ cái xuất hiện nhiều có mã ngắn, chữ hiếm có mã dài để cân bằng
Kết quả là nén dữ liệu hiệu quả rõ rệt! Nhưng đây chỉ là phương pháp gần đúng thôi. Vậy nên thầy Fano thách thức các sinh viên tìm ra cách tốt hơn nữa!
Nén nhỏ hơn nữa bằng cách đi từ dưới lên
Và đây là lúc David Huffman (1925-99) - học sinh của thầy Fano - vào cuộc! Thầy Fano xây cây từ trên xuống, còn Huffman lật ngược quy trình - xây từ dưới lên
Ý tưởng sâu sắc của Huffman là: dù sao thì hai ký tự ít phổ biến nhất sẽ có hai mã dài nhất. Vì vậy, Huffman tìm hai ký tự hiếm nhất, nhóm chúng thành cặp, rồi lặp lại với các ký tự còn lại và cặp vừa tạo.
Xét ví dụ từ "schoolroom" mà cách của thầy Fano hơi vấp: O xuất hiện 4 lần, S/C/H/L/R/M mỗi chữ 1 lần. Cách của thầy Fano cho ra 27 bit.
Còn Huffman bắt đầu với hai chữ hiếm nhất - ví dụ R và M - nhóm chúng lại, coi như một chữ duy nhất.
Sau đó cập nhật biểu đồ tần số: O xuất hiện 4 lần, RM được dùng 2 lần (về mặt chức năng), và S, C, H, L. Huffman lại chọn hai tùy chọn ít phổ biến nhất, ví dụ ghép H với L.
Cập nhật tiếp: O vẫn là 4, RM và HL mỗi cái là 2, S và C đứng riêng. Huffman cứ tiếp tục như vậy - mỗi bước nhóm hai tùy chọn ít xảy ra nhất rồi cập nhật cả cây lẫn tần suất.
Cuối cùng, "schoolroom" thành 11101111110000110110000101 (26 bit) - ít hơn cách của thầy Fano 1 bit! Nghe có vẻ ít nhưng nhân lên hàng tỷ gigabyte thì khủng lắm nha
Cách tiếp cận của Huffman mạnh đến mức giờ hầu như mọi chiến lược nén lossless đều dùng toàn bộ hoặc một phần cách hiểu của Huffman. Dùng PKZip để nén tài liệu Word? Bước đầu xác định sự lặp lại, bước hai chạy qua quy trình Huffman luôn!
Quả thật không tệ cho một dự án xuất phát từ việc một sinh viên muốn pass môn nhỉ?
Nguồn: tinhte.vn