¿Por qué Huffman codifica el código con la tasa de compresión más alta?

Supongamos que el mensaje utilizado para la comunicación consta de letras del conjunto de caracteres {a, b, c, d, e, f, g, h}. respectivamente {0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.

La codificación de Huffman se puede obtener según la tabla de codificación anterior: ?a:1001 ?b:01 ?c:10111 ?d:1010 ?e:11 ?f:10110 ?g:00 ?h: 1000 ?

La longitud promedio de la codificación de igual longitud que utiliza una progresión binaria de tres dígitos es 3, mientras que la longitud promedio del código basada en la codificación del árbol de Huffman es: 4*0,07+2*0,19+5*0,02+ 4 *0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 ?2.61/3=0.87=87% La longitud promedio del código es el 87% del código de igual longitud, por lo que la tasa de compresión promedio es 13 %.

Debido a que la codificación de longitud fija ya utiliza el mismo número de dígitos, esta condición garantiza que la codificación de cualquier carácter no se convertirá en un prefijo para otras codificaciones, por lo que esta situación solo ocurrirá en la codificación de longitud variable. Para evitar esta situación,

se debe utilizar una condición para definir la codificación de longitud fija. Esta condición es que para convertirse en una codificación comprimida, la codificación de longitud variable debe ser una codificación de prefijo. -La codificación de prefijo llamada es cualquier carácter. Ninguna codificación puede ser un prefijo de otra codificación de caracteres.

Información ampliada:

En aplicaciones prácticas, además de utilizar la limpieza de tiempo para eliminar la difusión de errores y el almacenamiento en búfer para resolver la coincidencia de tasas, el principal problema es resolver la coincidencia estadística de pequeños conjuntos de símbolos.

Por ejemplo, para la coincidencia estadística de fuentes de fax en blanco y negro (0), se utilizan tiradas de diferentes longitudes de 0 y 1 para formar una fuente de conjunto de símbolos ampliada. La longitud de ejecución se refiere a la longitud del mismo elemento de código (como la longitud o el número de una cadena continua de 0 o una cadena de 1 en código binario). Según el estándar CCITT, es necesario contar 2 × 1728 tipos de ejecuciones (longitudes).

De esta manera, la cantidad de almacenamiento durante la implementación es demasiado grande. De hecho, la probabilidad de una ejecución larga es muy pequeña, por lo que el CCITT también estipula: Si l representa la duración de la ejecución, entonces l = 64q + r. Entre ellos, q se denomina código principal y r es el código base. Al codificar, la longitud de ejecución de al menos 64 se compone del código principal y el código base. Y cuando l es un múltiplo entero de 64, solo se usa el código del código principal y no hay ningún código del código base.

Enciclopedia Baidu-Codificación Huffman