Codificación de Huffman

Cuando Huffman propuso esta codificación a principios de la década de 1950, construyó la codificación con la longitud promedio más corta basándose en la probabilidad de aparición de caracteres. Es una codificación de longitud variable. En la codificación, si las longitudes de cada palabra de código se organizan estrictamente en orden inverso a la probabilidad de aparición de los símbolos correspondientes a las palabras de código, la longitud promedio del código será la más pequeña. (Nota: la palabra clave es el código obtenido después de que el símbolo se codifica Huffman. Su longitud varía dependiendo de la probabilidad de que aparezca el símbolo, por lo que la codificación Huffman es un código de longitud variable). Además, la codificación Huffman se basa en sub-El árbol Se refiere al padre, pero su código de lectura es completamente opuesto. Por lo tanto, posteriormente se propuso un método de codificación dinámica de Huffman. La codificación dinámica de Huffman utiliza un árbol de Huffman que cambia dinámicamente. La codificación del carácter t + 1 se basa en el árbol de Huffman obtenido de los primeros t caracteres en los datos originales. Se utiliza la misma codificación y decodificación cada vez. Se procesa un carácter, la codificación y la decodificación utilizan el mismo método para modificar el árbol de Huffman, por lo que no es necesario guardar la información del árbol de Huffman para la decodificación. El tiempo necesario para codificar y decodificar un carácter es proporcional a la longitud de codificación del carácter, por lo que la codificación dinámica de Huffman se puede realizar en tiempo real. La codificación dinámica de Huffman es mucho más complicada que la codificación estática de Huffman. Los lectores interesados ​​pueden consultar libros sobre estructuras de datos y algoritmos.

La codificación Huffman se usa en el JPEG mencionado anteriormente. Esto no significa que JPEG solo use la codificación Huffman, sino que una imagen obtiene su columna de valores después de múltiples pasos, y Huffman codifica estos valores. para almacenamiento o transmisión. El método de codificación de Huffman es relativamente fácil de entender. Puede escribir sus propios programas de codificación y decodificación de Huffman basándose en su método de codificación.

Algoritmo de construcción del árbol de Huffman.

const maxvalue= 10000; {define el peso máximo}

maxleat=30; {define el número de nodos de hoja en el árbol de Huffman}

maxnode = maxleaf*2-1;

tipo HnodeType=registro

peso: entero;

padre: entero;

lniño: entero;

rchild: entero;

end;

HuffArr:matriz[0..maxnode] de HnodeType;

var ……

procedimiento CreatHaffmanTree(var HuffNode: HuffArr); {algoritmo de construcción del árbol de Huffman}

var i,j,m1,m2,x1,x2,n: entero;

begin

readln(n); {Ingrese el número de nodos hoja}

for i:=0 to 2*n-1 do {array HuffNode[ ]Inicialización}

comenzar

HuffNode.weight=0;

HuffNode.parent=-1;

HuffNode.lchild=- 1;

HuffNode.rchild=-1;

end;

para i:=0 a n-1 lea(HuffNode.weight); { Ingrese los pesos de n nodos de hoja}

para i:=0 a n-1 hacer {Construir árbol de Huffman}

comenzar

m1 :=MAXVALUE m2:=MAXVALUE; ;

x1:=0; x2:=0;

para j:=0 a n+i-1 hacer

if (HuffNode[j] .weight

comienza m2:=m1; x2:=x1;

m1:=HuffNode[j] .weight; x1:=j;

end

si no (HuffNode[j].weight

begin m2:=HuffNode[j].weight; x2:=j; end;

{Fusionar los dos subárboles encontrados en un árbol}

HuffNode[x1] ].parent:=n+i; HuffNode[x2].parent:=n+i;

HuffNode[n+i].weight:= HuffNode[x1].peso+HuffNode[x2]. peso;

HuffNode[n+i].lchild:=x1; HuffNode[n+i].rchild:=x2;

end;

end ;