Codificación Huffman

Esquema de codificación

El proceso de codificación y decodificación se llama codificación. Codificación y decodificación El proceso de compresión de datos se llama codificación, que convierte cada carácter del archivo en una cadena binaria única; el proceso de descompresión de datos se llama decodificación, que convierte la cadena binaria en los caracteres correspondientes.

Esquema de codificación de longitud igual y esquema de codificación de longitud variable

. Esquema de codificación de longitud igual y esquema de codificación de longitud variable Para un conjunto de caracteres C determinado, puede haber múltiples esquemas de codificación () Esquema de codificación de longitud igual El esquema de codificación de longitud igual establece la longitud de codificación de cada carácter en el conjunto de caracteres C determinado a [ lg|C|] |C| representa el tamaño del juego de caracteres Ejemplo: el archivo de datos a comprimir *** tiene un carácter y estos caracteres se toman del juego de caracteres C={a b c d e f}. Codificación de igual longitud. Se requieren tres bits binarios para representar seis caracteres, por lo que todo el archivo se codifica para tener una longitud de un bit.

() Esquema de codificación de longitud variable El esquema de codificación de longitud variable establece que la codificación de caracteres de alta frecuencia sea más corta y la codificación de caracteres de baja frecuencia sea más larga. El número de veces que aparece cada carácter en el archivo (frecuencia) se muestra en la tabla. Problema de codificación de caracteres Carácter a b c d e f Frecuencia (miles) ? Codificación de longitud fija Frecuencia de aparición de codificación de longitud variable (en miles) Según la fórmula ( * * * * * * * )* = ¿El archivo completo está codificado en bits, con? longitud fija Puede ahorrar aproximadamente espacio de almacenamiento en comparación con la codificación. Tenga en cuenta que la codificación de longitud variable puede provocar dicotomías al decodificar, ya que algunos caracteres pueden codificarse de la misma manera que otros caracteres (llamados prefijos).

Esquema de codificación de prefijos. ¿Esquema de codificación de prefijo? Al codificar un juego de caracteres, se requiere que la codificación de cualquier carácter en el juego de caracteres no sea un prefijo de otras codificaciones de caracteres. Esta codificación se llama código de prefijo. Tenga en cuenta que la codificación de igual longitud es el código de prefijo

. Mejor código de prefijo El código de prefijo con la longitud promedio de código o longitud total de archivo más pequeña se denomina mejor código de prefijo. donde pi es la probabilidad del i-ésimo carácter li es el ejemplo de longitud del código. Si los archivos que se muestran en la tabla se utilizan como muestras estadísticas, la longitud promedio del código de la codificación de longitud variable es mejor que la de la codificación de longitud fija (. la longitud promedio del código de codificación de longitud fija es)

Construcción de códigos Huffman a partir de árboles binarios óptimos

Es fácil derivar la longitud promedio del código y su probabilidad para un conjunto de caracteres determinado ( La longitud promedio del código es) del árbol de Huffman. El código de prefijo óptimo para un conjunto de caracteres determinado y su distribución de probabilidad (o frecuencia) La codificación de Huffman es una técnica de compresión de datos muy eficaz y ampliamente utilizada que comprime archivos de datos, dependiendo de las características del archivo que se está comprimiendo

() Construya un árbol de Huffman usando los caracteres ci como la hoja pi o fi como el peso de la hoja ci, y etiquete las ramas izquierda y derecha del árbol respectivamente como y () La ruta desde la raíz hasta la hoja. El enlace simbólico de arriba es la codificación del carácter representado por la hoja. El código de prefijo óptimo de la codificación de Huffman es el código obtenido del árbol de Huffman. La razón por la que el código es el código de prefijo óptimo es que ① la longitud de codificación de cada carácter de hoja ci es exactamente la longitud de codificación promedio de la longitud de ruta li del. raíz a la hoja (o la longitud total del archivo) es la longitud de ruta ponderada WPL del árbol binario, y el árbol de Huffman es el árbol binario con la longitud de ruta ponderada más pequeña WPL, por lo que la longitud promedio del código (o la longitud total). longitud del archivo) también es la más pequeña ② Ninguna hoja es la raíz de una hoja, pero también lo es. No hay otras hojas que no sean raíces de hojas, por lo que la longitud promedio del código (o longitud total del archivo) también es la pequeñísimo. Una hoja es el antepasado de otra hoja en el árbol. El código correspondiente a cada hoja no puede ser el prefijo de otros códigos de hoja, es decir, el código anterior es un código de prefijo binario

. Algoritmo de codificación de Huffman () ideas y métodos Después de generar un árbol de Huffman para un conjunto determinado de caracteres, el proceso de implementación específico de la codificación de Huffman es: comenzando desde la hoja T [i] (≤i≤n) a su vez, retroceda hasta la raíz hasta que se toma la rama izquierda para generar el código y se toma la rama derecha para generar el código durante el proceso de retroceso.

(ii) Cuando se complete la codificación de caracteres, copie el código desde el punto inicial del vector temporal al bit correspondiente del carácter. (iii) Dado que el tamaño del juego de caracteres es n, la longitud del código de longitud variable no puede exceder n más el terminador. El tamaño de los bits debe ser n

() ¿Estructura y algoritmo de codificación del juego de caracteres? typedef struct {? char ch //almacenar caracteres? char bits[n] //almacenar cadenas de bits codificadas }CodeNode? typedef CodeNode HuffmanCode[n] ?void CharSetHuffmanEncoding(HuffmanTree T HuffmanCode H) {/Busque la tabla de codificación Huffman H basada en el árbol Huffman T int c p i //c y p indican la posición del niño y de los dos padres en T respectivamente; ?char cd[n] //almacenar temporalmente la codificación? int start //indicar la posición inicial del código en cd? cd[n]= \ //Fin del carácter de codificación?for(i= ilt; n i ){ / /encontrar secuencialmente la codificación de la hoja T[i] H[i] ch=getchar() //leer el carácter correspondiente a la hoja T[i] start=n //valor inicial de la posición inicial de la codificación c=i //retroceder arriba desde la hoja T[i] while((p=T[c] parent)gt;= ){/hasta retroceder hasta T[c] ¿es la raíz del árbol? // Si T[c] es T[p ] Si el nodo secundario izquierdo es el nodo secundario izquierdo, entonces genere código; de lo contrario, genere código cd[start]=(T[p) child==C)? } strcpy(H[i] bits amp; cd[start]) //¿copiar cadena de bits codificada?}///endfor?}///CharSetHuffmanEncoding La codificación y decodificación del archivo utiliza la tabla de juego de caracteres Huffman para procesar los datos archivo El proceso de codificación consiste en leer el carácter c en el archivo en secuencia y luego encontrar el carácter en la tabla Huffman H. Si H [i] ch = c, convierte el carácter c en el carácter codificado almacenado en H [i] bits. Para decodificar un archivo de datos comprimidos tenemos que utilizar un árbol de Huffman T. El proceso de decodificación consiste en leer el código binario del archivo en orden, comenzando desde el nodo raíz del árbol de Huffman (es decir, T [m]). Si se está leyendo actualmente, léalo en el nodo secundario izquierdo; de lo contrario, léalo en el right Una vez que un nodo secundario lee una determinada hoja T[i], decodificará el H[i] ch correspondiente. Luego, comenzamos desde el nodo raíz y continuamos decodificando hasta que se decodifica el archivo. /p> lishixinzhi/Article/program/sjjg/201311/22941