Nén dữ liệu không mất dữ liệu hoạt động như thế nào | Tạp chí lượng tử

Với hơn 9 tỷ gigabyte thông tin di chuyển trên internet mỗi ngày, các nhà nghiên cứu không ngừng tìm kiếm những cách mới để nén dữ liệu thành các gói nhỏ hơn. Các kỹ thuật tiên tiến tập trung vào các phương pháp giảm tổn thất, đạt được khả năng nén bằng cách cố ý “làm mất” thông tin từ quá trình truyền. Ví dụ, Google gần đây đã tiết lộ một chiến lược mất dữ liệu trong đó máy tính gửi bỏ chi tiết từ một hình ảnh và máy tính nhận sử dụng trí tuệ nhân tạo để đoán những phần còn thiếu. Ngay cả Netflix cũng sử dụng phương pháp giảm chất lượng, hạ cấp chất lượng video bất cứ khi nào công ty phát hiện ra rằng người dùng đang xem trên thiết bị có độ phân giải thấp.

Ngược lại, rất ít nghiên cứu hiện đang được theo đuổi về các chiến lược không mất dữ liệu, trong đó các đường truyền được thực hiện nhỏ hơn, nhưng không có chất nào bị hy sinh. Nguyên nhân? Các phương pháp không mất dữ liệu đã có hiệu quả rõ rệt. Chúng cung cấp năng lượng cho mọi thứ, từ tiêu chuẩn hình ảnh JPEG đến tiện ích phần mềm phổ biến PKZip. Và tất cả chỉ vì một sinh viên mới tốt nghiệp, người chỉ đơn giản là tìm cách thoát khỏi kỳ thi cuối kỳ khó khăn.

Bảy mươi năm trước, một giáo sư của Học viện Công nghệ Massachusetts tên là Robert Fano đã đưa ra cho các sinh viên trong lớp lý thuyết thông tin của mình một lựa chọn: Làm bài kiểm tra cuối kỳ truyền thống hoặc cải tiến một thuật toán hàng đầu để nén dữ liệu. Fano có thể hoặc không thông báo cho sinh viên của mình rằng ông là tác giả của thuật toán hiện có đó, hoặc rằng ông đã tìm kiếm một cải tiến trong nhiều năm. Những gì chúng ta biết là Fano đã đưa ra thử thách sau cho các học trò của mình.

Hãy xem xét một tin nhắn được tạo thành từ các chữ cái, số và dấu chấm câu. Một cách đơn giản để mã hóa một tin nhắn như vậy là gán cho mỗi ký tự một số nhị phân duy nhất. Chẳng hạn, một máy tính có thể biểu thị chữ A là 01000001 và một dấu chấm than là 00100001. Điều này dẫn đến các mã dễ phân tích — cứ tám chữ số hoặc bit, tương ứng với một ký tự duy nhất — nhưng cực kỳ kém hiệu quả vì cùng một số của các chữ số nhị phân được sử dụng cho cả mục phổ biến và không phổ biến. Một cách tiếp cận tốt hơn sẽ là một cái gì đó giống như mã Morse, trong đó chữ E thường được biểu thị bằng một dấu chấm duy nhất, trong khi chữ Q ít phổ biến hơn yêu cầu dấu gạch ngang dài hơn và tốn nhiều công sức hơn.

Tuy nhiên, mã Morse cũng không hiệu quả. Chắc chắn, một số mã ngắn và những mã khác dài. Nhưng vì độ dài của mã khác nhau nên không thể hiểu được các thông điệp trong mã Morse trừ khi chúng bao gồm các khoảng thời gian im lặng ngắn giữa mỗi lần truyền ký tự. Thật vậy, nếu không có những khoảng dừng tốn kém đó, người nhận sẽ không có cách nào để phân biệt thông điệp Morse dash dot-dash-dot dot-dot dash dot (“trite”) với dash dot-dash-dot dot-dot-dash dot (“true” ).

Fano đã giải quyết được phần này của vấn đề. Anh ấy nhận ra rằng anh ấy có thể sử dụng các mã có độ dài khác nhau mà không cần khoảng trống tốn kém, miễn là anh ấy không bao giờ sử dụng cùng một kiểu chữ số cho cả mã hoàn chỉnh và phần đầu của mã khác. Ví dụ: nếu chữ S quá phổ biến trong một tin nhắn cụ thể đến mức Fano đã gán cho nó mã cực ngắn 01, thì không có chữ cái nào khác trong tin nhắn đó sẽ được mã hóa bằng bất kỳ thứ gì bắt đầu 01; các mã như 010, 011 hoặc 0101 đều sẽ bị cấm. Kết quả là, tin nhắn được mã hóa có thể được đọc từ trái sang phải mà không có bất kỳ sự mơ hồ nào. Ví dụ chữ S gán 01, chữ A gán 000, chữ M gán 001, chữ L gán 1, đột nhiên tin nhắn 0100100011 có thể dịch ngay thành từ “nhỏ” mặc dù L được biểu thị bằng XNUMX chữ số, S bằng hai chữ số và các chữ cái khác bằng ba chữ số mỗi chữ số.

Để thực sự xác định các mã, Fano đã xây dựng các cây nhị phân, đặt mỗi chữ cái cần thiết ở cuối nhánh thị giác. Mã của mỗi chữ cái sau đó được xác định theo đường dẫn từ trên xuống dưới. Nếu đường dẫn phân nhánh sang trái, Fano đã thêm 0; nhánh bên phải có điểm 1. Cấu trúc cây giúp Fano dễ dàng tránh được những trùng lặp không mong muốn đó: Một khi Fano đặt một chữ cái vào cây, nhánh đó sẽ kết thúc, nghĩa là không mã nào trong tương lai có thể bắt đầu theo cách tương tự.

Để quyết định những chữ cái nào sẽ đi đến đâu, Fano có thể đã kiểm tra kỹ lưỡng mọi mẫu có thể để đạt hiệu quả tối đa, nhưng điều đó sẽ không thực tế. Vì vậy, thay vào đó, anh ấy đã phát triển một phép tính gần đúng: Đối với mỗi tin nhắn, anh ấy sẽ sắp xếp các chữ cái có liên quan theo tần suất và sau đó gán các chữ cái cho các nhánh sao cho các chữ cái ở bên trái trong bất kỳ cặp nhánh cụ thể nào được sử dụng trong tin nhắn với số lần tương đương với chữ bên phải. Theo cách này, các ký tự được sử dụng thường xuyên sẽ kết thúc trên các nhánh ngắn hơn, ít dày đặc hơn. Một số lượng nhỏ các chữ cái có tần suất cao sẽ luôn cân bằng với một số lượng lớn hơn các chữ cái có tần suất thấp hơn.

Kết quả là nén hiệu quả rõ rệt. Nhưng đó chỉ là một con số gần đúng; một chiến lược nén tốt hơn phải tồn tại. Vì vậy, Fano đã thách thức các sinh viên của mình tìm ra nó.

Fano đã xây dựng các cây của mình từ trên xuống, duy trì sự đối xứng giữa các nhánh được ghép nối nhiều nhất có thể. Sinh viên của ông, David Huffman, đã lật ngược quy trình, xây dựng các loại cây tương tự nhưng từ dưới lên. Cái nhìn sâu sắc của Huffman là, bất kể điều gì khác xảy ra, trong một mã hiệu quả, hai ký tự ít phổ biến nhất sẽ có hai mã dài nhất. Vì vậy, Huffman đã xác định hai ký tự ít phổ biến nhất, nhóm chúng lại với nhau thành một cặp phân nhánh, sau đó lặp lại quy trình, lần này tìm kiếm hai mục ít phổ biến nhất trong số các ký tự còn lại và cặp mà ông vừa tạo.

Hãy xem xét một thông điệp mà cách tiếp cận Fano chùn bước. Trong “schoolroom,” O xuất hiện bốn lần và S/C/H/L/R/M mỗi cái xuất hiện một lần. Cách tiếp cận cân bằng của Fano bắt đầu bằng cách gán chữ O và một chữ cái khác cho nhánh bên trái, với tổng số năm cách sử dụng của các chữ cái đó sẽ cân bằng năm lần xuất hiện của các chữ cái còn lại. Thông báo kết quả yêu cầu 27 bit.

Ngược lại, Huffman bắt đầu với hai trong số các chữ cái không phổ biến - chẳng hạn, R và M - và nhóm chúng lại với nhau, coi cặp này giống như một chữ cái duy nhất.

Sau đó, biểu đồ tần số được cập nhật của anh ấy đưa ra cho anh ấy bốn lựa chọn: chữ O xuất hiện bốn lần, nút RM kết hợp mới được sử dụng hai lần về mặt chức năng và các chữ cái đơn lẻ S, C, H và L. Huffman lại chọn hai tùy chọn ít phổ biến nhất, khớp với nhau (nói) H với L.

Biểu đồ cập nhật lại: O vẫn có trọng số là 4, RM và HL hiện mỗi cái có trọng số là 2, và chữ S và C đứng riêng lẻ. Huffman tiếp tục từ đó, trong mỗi bước nhóm hai tùy chọn ít xảy ra nhất và sau đó cập nhật cả biểu đồ cây và biểu đồ tần suất.

Cuối cùng, “phòng học” trở thành 11101111110000110110000101, loại bỏ một chút cách tiếp cận từ trên xuống của Fano.

Một bit nghe có vẻ không nhiều, nhưng ngay cả khoản tiết kiệm nhỏ cũng tăng lên rất nhiều khi được nhân lên hàng tỷ gigabyte.

Thật vậy, cách tiếp cận của Huffman đã trở nên mạnh mẽ đến mức, ngày nay, gần như mọi chiến lược nén không mất dữ liệu đều sử dụng toàn bộ hoặc một phần hiểu biết của Huffman. Cần PKZip để nén tài liệu Word? Bước đầu tiên liên quan đến một chiến lược thông minh khác để xác định sự lặp lại và do đó nén kích thước thông báo, nhưng bước thứ hai là lấy thông báo đã nén và chạy nó thông qua quy trình Huffman. Lưu trữ hình ảnh dưới dạng JPEG? Trước tiên, máy tính của bạn dịch hình ảnh thành biểu diễn dựa trên văn bản và sau đó, sử dụng lại mã hóa Huffman để nén văn bản đó.

Không tồi đối với một dự án ban đầu được thúc đẩy bởi mong muốn bỏ qua kỳ thi cuối kỳ của một sinh viên mới tốt nghiệp.