Giải thích entropy
Năm 1948, một kỹ sư tại Bell Labs là Claude Shannon đặt ra một câu hỏi chưa ai từng phát biểu chính xác: một thông điệp chứa bao nhiêu thông tin? Câu trả lời của ông là một con số, đo bằng bit, không phụ thuộc vào ý nghĩa của thông điệp mà vào mức độ bất ngờ của nó. Con số ấy, entropy, đặt ra giới hạn cho mọi chương trình nén, mọi đường truyền mạng và mọi thiết bị lưu trữ, và giải thích vì sao có những văn bản co lại chỉ còn một phần nhỏ kích thước, trong khi những văn bản khác không thể ép nhỏ chút nào.
Thông tin là sự bất ngờ
Ý tưởng sâu sắc của Shannon là đo thông tin bằng mức độ bất ngờ của một thông điệp chứ không phải bằng ý nghĩa của nó. Nếu bạn đã biết câu trả lời, nghe nó chẳng cho bạn biết gì; nếu nó có thể là một trong cả nghìn điều, nó cho bạn biết rất nhiều. Một thông điệp chọn ra một trong hai khả năng như nhau mang một bit. Một trong bốn cần hai bit, một trong tám cần ba bit, và nói chung một trong N khả năng như nhau cần log₂ N bit. Do đó một ký hiệu xuất hiện với xác suất p mang −log₂ p bit: nó càng hiếm thì càng cho bạn biết nhiều.
Công thức của Shannon
Entropy là lượng thông tin trung bình mỗi ký hiệu: H = −Σ p log₂ p, lấy tổng trên mọi ký hiệu với xác suất p của nó. Với một đồng xu cân đối, H bằng 1 bit. Với một đồng xu ra mặt ngửa 90% số lần, nó chỉ còn 0,47 bit, vì kết quả thường chẳng có gì bất ngờ. Entropy lớn nhất khi mọi ký hiệu có khả năng như nhau, log₂ n bit với n ký hiệu, và bằng không khi một ký hiệu là chắc chắn. Shannon chọn cái tên này theo lời khuyên của John von Neumann, vì cùng công thức ấy xuất hiện trong vật lý, nơi entropy đo mức độ hỗn loạn.
Giới hạn của nén
Định lý mã hóa nguồn của Shannon nói rằng không có mã không mất dữ liệu nào có thể dùng trung bình ít bit mỗi ký hiệu hơn entropy của nguồn, và các mã có thể tiến gần đến giới hạn đó tùy ý. Mã hóa Huffman, do David Huffman phát minh năm 1952 khi còn là sinh viên, gán mã ngắn cho các ký hiệu thường gặp và mã dài cho các ký hiệu hiếm, và chỉ cách entropy chưa đến một bit mỗi ký hiệu; mã hóa số học còn tiến gần hơn nữa. Vì vậy entropy không chỉ là một mô tả mà là một giới hạn cứng: một tệp gồm các byte ngẫu nhiên, với 8 bit entropy mỗi byte, hoàn toàn không thể nén được.
Ngữ cảnh và độ dư thừa
Các chữ cái trong văn bản không độc lập với nhau. Trong tiếng Anh, sau Q là U, sau dấu chấm là chữ hoa, và một từ bắt đầu bằng INFORMA gần như chắc chắn tiếp tục bằng TION. Tính đến các ký hiệu trước đó cho ta entropy có điều kiện, thấp hơn entropy của các ký hiệu khi đếm riêng từng cái. Phần chênh lệch là độ dư thừa: phần của thông điệp lẽ ra có thể đoán trước. Các chương trình nén như ZIP, dùng phương pháp deflate, tìm những chuỗi lặp lại và thay chúng bằng tham chiếu ngắn, còn các bộ nén hiện đại dự đoán từng ký hiệu từ ngữ cảnh của nó.
Tiếng Anh chứa bao nhiêu thông tin?
Nếu đếm từng chữ cái theo tần suất của tiếng Anh, mỗi chữ cái mang khoảng 4,1 bit, so với 4,7 bit của các chữ cái chọn ngẫu nhiên. Năm 1951, Shannon đi xa hơn: ông cho mọi người xem phần đầu của một văn bản và yêu cầu họ đoán chữ cái tiếp theo, đồng thời đếm xem họ cần bao nhiêu lần đoán. Từ câu trả lời của họ, ông ước tính rằng tiếng Anh chỉ mang khoảng 0,6 đến 1,3 bit mỗi chữ cái. Nói cách khác, khoảng ba phần tư tiếng Anh viết là dư thừa, và vì thế một văn bản bị mất bớt chữ cái thường vẫn đọc được.
Tính ngẫu nhiên và mật khẩu
Entropy cũng đo tính khó đoán, điều mà bảo mật dựa vào. Một khóa hay mật khẩu được chọn đồng đều từ N khả năng có log₂ N bit entropy, và kẻ tấn công trung bình phải thử khoảng một nửa số đó. Một mật khẩu ngẫu nhiên 12 chữ cái lấy từ 26 chữ cái thường có khoảng 56 bit; một từ thông dụng có ít hơn nhiều, dù nó dài đến đâu. Các bộ sinh số ngẫu nhiên được kiểm tra bằng cách xác nhận rằng đầu ra của chúng có đủ entropy của một nguồn ngẫu nhiên, và các hệ điều hành thu thập entropy từ nhiễu thời gian để tạo hạt giống cho chúng.
Entropy xuất hiện ở đâu
Entropy quyết định một cuộc gọi điện thoại, một bức ảnh hay một luồng video cần bao nhiêu bit, và một modem hay kết nối Wi-Fi có thể tiến gần đến dung lượng kênh của nó đến mức nào. Các nhà sinh học dùng nó để đo thông tin trong DNA, nơi bốn loại bazơ mỗi loại mang tối đa 2 bit, và đo sự đa dạng của một hệ sinh thái. Trong học máy, cây quyết định chọn câu hỏi làm giảm entropy nhiều nhất, và hàm mất mát entropy chéo được dùng để huấn luyện phần lớn mạng nơ-ron. Các nhà ngôn ngữ học so sánh các ngôn ngữ qua entropy của chúng theo ký tự và theo từ.
Khám phá
Mở máy tính entropy để đo bất kỳ văn bản nào theo ký tự, từ hoặc byte. So sánh một đoạn văn với chữ cái, bit, chữ số và DNA ngẫu nhiên, xem độ bất ngờ của từng ký hiệu, văn bản chứa bao nhiêu thông tin so với kích thước lưu trữ, và số bit mỗi ký hiệu giảm thế nào khi biết thêm ngữ cảnh, bên cạnh kết quả thực tế của ZIP.
Câu hỏi thường gặp
Vì sao entropy được đo bằng bit?
Vì Shannon dùng logarit cơ số 2, để một lựa chọn có-hoặc-không giữa hai phương án như nhau được tính là một đơn vị. Với logarit tự nhiên, đơn vị là nat, khoảng 1,44 bit, và với cơ số 10 là hartley, khoảng 3,32 bit; các nhà vật lý và một số nhà thống kê dùng những đơn vị đó.
Một văn bản có thể có entropy lớn hơn log₂ kích thước bảng chữ cái của nó không?
Không. Với n ký hiệu khác nhau, entropy tối đa là log₂ n bit mỗi ký hiệu, chỉ đạt được khi tất cả phổ biến như nhau. Bất kỳ sự mất cân bằng nào, và bất kỳ khả năng đoán trước nào từ ngữ cảnh, đều làm nó giảm.
Entropy trong lý thuyết thông tin có giống entropy trong vật lý không?
Các công thức giống nhau về hình thức: Boltzmann và Gibbs viết entropy vật lý dưới dạng một tổng trên xác suất của các trạng thái vi mô của một hệ. Ý nghĩa cũng có liên quan, vì cả hai đều đo xem bạn không biết bao nhiêu, và về sau các nhà vật lý đã chứng minh rằng xóa một bit thông tin nhất định phải tỏa ra một lượng nhiệt nhỏ.
Vì sao nén một tệp đã nén chẳng giúp ích gì?
Một bộ nén tốt loại bỏ phần lớn độ dư thừa, nên đầu ra của nó gần như ngẫu nhiên, với gần 8 bit entropy mỗi byte. Không còn gì để loại bỏ, và nén lại lần nữa thường làm tệp lớn hơn một chút vì phần chi phí phụ của chính bộ nén.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Mở máy tính entropy