Mã Huffman
Mã Huffman được định nghĩa là một loại mã tiền tố tối ưu cụ thể thường được sử dụng để nén dữ liệu không mất dữ liệu.
Quá trình tìm kiếm hoặc thực hiện một đoạn mã như vậy được tiến hành bằng phương pháp mã hóa Huffman, một thuật toán được phát triển bởi David A. Huffman khi ông còn là một Sc.D. sinh viên tại MIT, và xuất bản trong bài báo năm 1952 "Phương pháp xây dựng mã dự phòng tối thiểu".
Đầu ra từ thuật toán của Huffman có thể được hiển thị dưới dạng bảng mã có độ dài thay đổi để mã hóa một ký hiệu nguồn (chẳng hạn như một ký tự trong tệp). Thuật toán tạo bảng này từ xác suất ước tính hoặc tần suất xuất hiện (trọng số) cho mỗi giá trị có thể có của ký hiệu nguồn. Như trong các phương pháp mã hóa entropy khác, các ký hiệu phổ biến hơn thường được biểu diễn bằng cách triển khai ít bit hơn các ký hiệu ít phổ biến hơn. Phương pháp Huffman có thể được triển khai một cách hiệu quả, tìm mã theo thời gian tuyến tính với số lượng trọng số đầu vào nếu các trọng số này được sắp xếp.
Entropy
Trong lý thuyết thông tin, định lý mã hóa nguồn của Shannon (hay định lý mã hóa không ồn ào) có thể thiết lập các giới hạn đối với khả năng nén dữ liệu và ý nghĩa hoạt động của entropy Shannon.
Định lý mã hóa nguồn hiển thị rằng (trong giới hạn, vì độ dài của một luồng dữ liệu biến ngẫu nhiên độc lập và được phân phối giống hệt nhau (i.i.d.) có xu hướng đến vô cùng) nên không thể nén dữ liệu sao cho tốc độ mã (số trung bình của bit trên mỗi ký hiệu) nhỏ hơn entropy Shannon của nguồn, nếu không có nó hầu như chắc chắn rằng thông tin sẽ bị mất. Tuy nhiên, có thể có được tỷ lệ mã gần với entropy Shannon một cách tùy ý, với xác suất mất mát không đáng kể.
Entropy thông tin được định nghĩa là tốc độ trung bình mà thông tin được tạo ra bởi một nguồn dữ liệu ngẫu nhiên.
Tính toán Entropy cho một biến ngẫu nhiên
Chúng tôi cũng có thể tính toán lượng thông tin có trong một biến ngẫu nhiên.
Ví dụ, nếu chúng ta muốn tính toán thông tin cho một biến ngẫu nhiên X với phân phối xác suất p, điều này có thể được viết dưới dạng một hàm H (); ví dụ:H (X)
Trên thực tế, việc tính toán thông tin cho một biến ngẫu nhiên tương tự như tính toán thông tin cho phân phối xác suất của các sự kiện cho biến ngẫu nhiên.
Việc tính toán thông tin cho một biến ngẫu nhiên được ký hiệu là “entropy thông tin”, “entropy Shannon” hoặc đơn giản là “entropy”.
Nó liên quan đến ý tưởng về entropy từ vật lý bằng phép loại suy, ở chỗ cả hai đều liên quan đến sự không chắc chắn của thuật ngữ.
Trực giác cho entropy là nó được định nghĩa là số bit trung bình cần thiết để biểu diễn hoặc truyền một sự kiện rút ra từ phân phối xác suất cho biến ngẫu nhiên.
Entropy Shannon của một phân phối được định nghĩa là lượng thông tin dự kiến trong một sự kiện được rút ra từ phân phối đó.
Nó cung cấp một giới hạn thấp hơn về số lượng bit trung bình cần thiết để mã hóa các ký hiệu được rút ra từ một phân phối P.
Entropy có thể được tính cho một biến ngẫu nhiên X với k ở trạng thái rời rạc K như sau
H(X) = -sum(each k in K p(k) * log(p(k)))
Điều đó có nghĩa là số âm của tổng xác suất của mỗi sự kiện nhân với nhật ký xác suất của mỗi sự kiện.
Giống như thông tin, hàm log () triển khai cơ số 2 và các đơn vị là bit. Thay vào đó, một lôgarit tự nhiên có thể được triển khai.
Entropy thấp nhất được tính cho một biến ngẫu nhiên có một sự kiện duy nhất với xác suất là 1,0, một điều chắc chắn. Entropy lớn nhất cho một biến ngẫu nhiên sẽ có thể có nếu tất cả các sự kiện được thực hiện có khả năng như nhau.