Buzz
Một học sinh muốn vượt qua bài kiểm tra cuối kỳ của mình đã dẫn đến một 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.Với hơn 9 tỷ gigabyte thông tin di chuyển trên internet mỗi ngày, nghiên cứu phải không ngừng tìm cách nén dữ liệu thành gói nhỏ hơn. Nhiều kỹ thuật tập trung vào phương pháp gây tổn thất, làm mất thông tin từ quá trình truyền tải. Google và Netflix đã áp dụng các chiến lược này để giảm kích thước dữ liệu.
Hiện nay, có ít nghiên cứu tập trung vào các phương pháp không gây mất dữ liệu (lossless), trong đó dữ liệu được nén mà không làm mất thông tin. Các phương pháp này đã được chứng minh là hiệu quả từ hình ảnh PNG đến phần mềm PKZip, tất cả nhờ sự tinh thần kiên định của một sinh viên mới tốt nghiệp, người chỉ muốn vượt qua kỳ thi cuối kỳ khó khăn.Thách thức của Fano
Bảy mươi năm trước, giáo sư Robert Fano từ Học viện Công nghệ Massachusetts (MIT) đã đặt ra lựa chọn cho sinh viên lớp lý thuyết thông tin của mình: Làm bài kiểm tra cuối kỳ theo cách 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ể đã thông báo với sinh viên rằng ông là tác giả của thuật toán hiện tại, hoặc ông đã tìm kiếm cải tiến trong nhiều năm và cũng có thể ông đã không nói gì cả. Điều chúng ta biết là Fano đã đưa ra thách thức này cho sinh viên của mình.
Robert Fano và đồng nghiệp đang tận hưởng thời gian cùng nhau.Nhóm đã thực sự tạo ra điều kỳ diệu.Sự sáng tạo của họ không ngừng phát triển.
Mã Morse quốc tế, một phát minh tuyệt vời trong lịch sử.Dù đã tiến bộ, mã Morse vẫn còn nhược điểm.Xoá bỏ sự trùng lặp, một bước tiến quan trọng.
Fano đã tìm ra cách giải quyết vấn đề này một cách thông minh.Việc xây dựng cây nhị phân giúp Fano dễ dàng xác định các đoạn mã.
Cấu trúc cây giúp tránh được sự trùng lặp không mong muốn.Tần suất đóng vai trò quan trọng trong mã hóa thông điệp.
Fano sử dụng phép tính gần đúng để phân chia các chữ cái dựa trên tần suất.
Cây mã của Fano thể hiện rõ sự cân bằng giữa các ký tự.Nén nhỏ hơn bằng cách khám phá từ dưới lên
Huffman đã đảo ngược quy trình, xây dựng cây từ dưới lên.
Huffman, hình như từ 1978 đến 1999. Ảnh: MAA.Một ví dụ mà phương pháp của Fano gặp khó khăn.
Cách tiếp cận không tối ưu của Fano dẫn đến đoạn mã dài 27 bit.
Huffman cập nhật biểu đồ tần suất và chọn lựa chọn ít phổ biến nhất.
Biểu đồ tần suất được cập nhật: O vẫn có trọng số 4, RM và HL giờ có trọng số 2, và S và C đứng riêng lẻ.
Cuối cùng, “schoolroom” trở thành 11101111110000110110000101 (26 bit), giảm một bit so với phương pháp của Fano.
Một bit có thể không nhiều, nhưng trong lượng dữ liệu lớn, sự tiết kiệm nhỏ này có thể lớn lao.Phương pháp của Huffman đã trở nên phổ biến đến mức, ngày nay, hầu hết các chiến lược nén không mất dữ liệu đều sử dụng cách hiểu của Huffman.Điều đó thật tuyệt vời cho một dự án bắt đầu từ mong muốn vượt qua kỳ thi cuối kỳ của một sinh viên mới tốt nghiệp.Theo Quanta Magazine.
