Việc nén dữ liệu đã thúc đẩy mạng Internet như thế nào?

Từ việc một học sinh mong muốn vượt qua bài kiểm tra cuối kỳ của mình đã dẫn đến thuật toán phổ biến giúp thu nhỏ dữ liệu mà không làm mất mát thông tin trong đó

Với hơn 9 tỷ gigabyte (tương đương 9 ngàn petabyte) thông tin di chuyển trên internet mỗi ngày, các nhà nghiên cứu phải không ngừng tìm kiếm những cách mới để nén dữ liệu thành những gói nhỏ hơn. Nhiều kỹ thuật tiên tiến tập trung vào các phương pháp gây tổn thất (lossy), tức là việc đạ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 tải. Ví dụ, Google gần đây đã tiết lộ một chiến lược gây tổn thất trong đó máy tính bên gửi giảm bớt chi tiết từ một hình ảnh và máy tính bên nhận sử dụng trí tuệ nhân tạo để đoán ra những phần còn thiếu. Ngay cả Netflix cũng sử dụng phương pháp làm giảm chất lượng, họ 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 phim 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 gây mất dữ liệu (lossless), trong đó các lượt truyền tải được làm cho nhỏ hơn, nhưng không có phần dữ liệu nào bị hy sinh. Nguyên nhân là vì các phương pháp không làm mất dữ liệu đã có hiệu quả rõ rệt. Chúng hỗ trợ mọi thứ từ chuẩn hình ảnh PNG đến tiện ích phần mềm phổ biến là PKZip. Và tất cả chỉ là do một sinh viên mới tốt nghiệp, người chỉ đơn giản là tìm cách vượt qua kỳ thi cuối kỳ khó khăn.

Đề bài của Fano

Bảy mươi năm trước, một giáo sư của Học viện Công nghệ Massachusetts (MIT) tên là Robert Fano (1917-2016) đã đưa ra cho các sinh viên trong lớp lý thuyết thông tin của ông 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 khi đó để nén dữ liệu. Fano có thể đã 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 ông đã tìm kiếm một cách cải tiến trong nhiều năm và cũng có thể đã không thông báo gì cả. Ở đây những gì chúng ta biết là Fano đã đưa ra thử thách sau cho các sinh viên của mình.

Chúng ta hãy xem xét một tin nhắn được tạo thành từ các chữ cái, các con 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 (số chỉ gồm hai ký tự, thường là 0 và 1). Chẳng hạn, một máy tính có thể lấy đại diện cho chữ A là 01000001 và một dấu chấm than là 00100001. Điều này dẫn đến các đoạn mã khá dễ phân tích — cứ mỗi tám chữ số (tức 8 bit, bằng 1 byte), tương ứng với một ký tự duy nhất — nhưng lại 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ả chỉ mục phổ biến lẫn không phổ biến. Một cách tiếp cận tốt hơn sẽ là một thứ gì đó giống như mã Morse, trong đó chữ E thường gặp đượ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 đòi hỏi đoạn mã dài hơn và tốn nhiều công sức hơn là gạch ngang-gạch ngang-chấm-gạch ngang (−−∙−).

Tuy nhiên, mã Morse cũng không hiệu quả. Chắc chắn là có 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 tin nhắn trong mã Morse trừ khi chúng bao gồm cả các khoảng lặng ngắn giữa mỗi lần truyền tải 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”).

Phá bỏ sự trùng lặp

Fano đã giải quyết được phần này của vấn đề. Ông nhận ra rằng mình có thể sử dụng các mã có độ dài khác nhau mà không cần những khoảng trống tốn kém, miễn là ông không bao giờ sử dụng cùng một khuôn mẫu số đó cho cả một mã hoàn chỉnh và phần đầu của một 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 gặp phải 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ừ “small” (tức là 01+001+000+1+1) mặc dù L được biểu thị bằng 1 con số, S bằng hai con số và các chữ cái kia bằng ba số mỗi chữ.

Để thực sự xác định các đoạn mã, Fano đã xây dựng những cây nhị phân, đặt mỗi chữ cái cần thiết ở cuối nhánh thị giác (vì nếu đi tiếp sẽ bị lầm lẫn). 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 để số 1, quy tắc này áp dụng cho mọi nhánh. 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 tùy ý vào cây, nhánh đó sẽ kết thúc luôn, nghĩa là không mã nào trong tương lai có thể bắt đầu theo cách tương tự.

Một cây Fano cho tin nhắn là từ ”encoded" (được mã hóa). Chữ D xuất hiện sau một lần rẽ trái rồi mới đến phải (đường màu cam), vì vậy nó được mã hóa là 01, trong khi chữ C là phải-phải-trái (đường màu xanh dương), thành 110. Điều quan trọng là tất cả các nhánh đều kết thúc sau khi đặt một chữ cái. Như ta thấy ở cây này, mọi nhánh của nó đã kết thúc vì đã đặt chữ toàn bộ.

Vai trò quan trọng của tần suất

Để quyết định xem những chữ cái nào sẽ đi đến chỗ nào, Fano có nguy cơ phải kiểm tra kỹ lưỡng mọi khuôn mẫu có thể để đạt hiệu quả tối đa, nhưng điều đó ắt hẳn là không thực tế. Vì vậy, thay vào đó, ông đã phát triển một phép tính gần đúng: Đối với mỗi tin nhắn, ông 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 vào 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ủa các chữ cái có tần suất thấp hơn.

Thông điệp “bookkeeper” (kế toán viên) có ba chữ E, hai chữ K, hai chữ O và một chữ B, một P và một R. Tính đối xứng của Fano thể hiện rõ ràng trên toàn bộ cây. Ví dụ: E và K cùng nhau có tổng tần số là 5, hoàn toàn phù hợp với tần số kết hợp của O, B, P và R. Những chữ xuất hiện nhiều có mã ngắn và chữ xuất hiện ít có mã dài hơn để có sự cân bằng.

Kết quả là việc nén dữ liệu có hiệu quả rõ rệt. Nhưng đó chỉ là một phương thức 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ó.

Nén nhỏ hơn nữa bằng cách đi từ dưới lê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 nhiều nhất có thể giữa các nhánh được ghép nối. Sinh viên của ông, David Huffman (1925-99), đã 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. Góc nhìn sâu của Huffman là, bất kể điều gì khác xảy ra, thì trong một đoạn 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 có phân nhánh, sau đó lặp lại quy trình, lần này là tìm kiếm hai chỉ 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 phải chùn bước. Trong từ “schoolroom,” O xuất hiện bốn lần và S/C/H/L/R/M mỗi chữ 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 điệp kết quả đòi hỏi 27 bit.

Cách làm chưa tối ưu theo kiểu của Fano: đầu tiên chọn ra chữ cái phổ biến nhất (O) và một chữ bất kỳ (S) sao cho tần suất của cặp OS (Freq = 5) bằng với tần suất của các chữ còn lại, tức CHLRM (Freq = 5). Sau đó ở nhánh OS ngay lập tức gán chữ O cho nhánh trái, chữ S cho nhánh phải. Với nhánh CHLRM ta chọn hai nhánh rẽ là CH (Freq = 2) và LRM (Freq = 3), và cứ tiếp tục gán dần xuống như hình. Cuối cùng ta được đoạn mã 27 bit (27 ký tự 0 và 1).

Tần suất của một cặp nhánh bất kỳ không nhất thiết phải bằng nhau, bởi điều này không phải lúc nào cũng làm được, nhưng theo đề xuất của Fano phải cố gắng tìm sao cho càng gần càng tốt để đạt hiệu quả nén dữ liệu, vì các chữ cái được gán sẽ có xu hướng nằm phía trên nhiều hơn và dẫn tới mã ngắn hơn. Cách làm này chỉ là một trong số nhiều cách tiếp cận từ trên xuống, những cách còn lại sẽ cho ra đoạn mã nhiều bit hơn nữa, nghĩa là nó kém hiệu quả hơn.

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 Huffman đưa ra cho ông bốn lựa chọn: chữ O xuất hiện bốn lần, nút kết hợp mới là RM đượ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ần nữa chọn hai tùy chọn ít phổ biến nhất, khớp với nhau, chẳng hạn 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 bằng cách nhóm hai tùy chọn ít xảy ra nhất và sau đó cập nhật cả biểu đồ cây lẫn biểu đồ tần suất.

Cuối cùng, “schoolroom” trở thành 11101111110000110110000101 (26 bit), bớt đi một bit so với 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ả phần tiết kiệm dữ liệu 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 hóa ra đã 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 cách hiểu 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 được kích thước thông điệp, nhưng bước thứ hai là lấy thông điệp đã nén và chạy nó thông qua quy trình Huffman.

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

Theo Quanta Magazine.