¿La codificación de Huffman siempre es óptima?

9

El requisito de que la codificación esté libre de prefijos da como resultado árboles grandes debido a que el árbol debe estar completo. ¿Existe un umbral en el que el almacenamiento no codificado de datos de longitud fija sería más eficiente que codificar los datos?

information-theory data-compression Kaveh
fuente
En general 'no'. Para un dato promedio, la frecuencia de cada carácter sería> 1 y es bueno usar Huffman Encoding en lugar de códigos de longitud fija
@arunmoezhi ¿Podría por favor abordar el ejemplo que he proporcionado anteriormente? La frecuencia de cada carácter es mayor que 1, pero la longitud fija es más óptima.
Este ejemplo es interesante. Pero, ¿puede proporcionar ese escenario con las probabilidades de cada personaje en lugar de la frecuencia y asegurarse de que las probabilidades de todos los personajes se sumen a 1
@arunmoezhi He incluido las probabilidades de los personajes y suman 1.

Respuestas:

4

La entropía H(A) para este problema es 1.998. Tanto la codificación de Huffman como la codificación de longitud fija para este problema tienen una longitud de palabra de código promedio como 2. Y para tu información, la codificación que tienes usando Huffman Encoding es incorrecta. Huffman Encoding también produce códigos similares a la longitud fija para este problema. Utiliza un enfoque codicioso. Entonces a, no obtiene un código como, 0sino que lo obtiene 00. Vuelva a trabajar en el árbol que genere usando Huffman Coding. El árbol que debes obtener es:ingrese la descripción de la imagen aquí

arunmoezhi
fuente
Gracias. ¿Podría proporcionar algún tipo de prueba de que la codificación Huffman siempre es más óptima que la longitud fija, o al menos referirme a una?
1
Puede referirse a Introduction to Algorithmspor CLRS. En el capítulo que habla sobre greedy algorithmsusted puede obtener la prueba formal de Huffman algorithm. Es una prueba larga y necesita paciencia para leer.
8

La codificación de Huffman se aproxima a la distribución de la población con potencias de dos probabilidades. Si la distribución verdadera consiste en potencias de dos probabilidades (y los símbolos de entrada no están correlacionados), la codificación de Huffman es óptima. Si no, puede hacerlo mejor con la codificación de rango. Sin embargo, es óptimo entre todas las codificaciones que asignan conjuntos específicos de bits a símbolos específicos en la entrada.

Antimonio
fuente
¿Qué quiere decir con "aproxima la distribución de la población"?
3
Existe una verdadera distribución teórica del mensaje que hipotéticamente podría enviarse. Idealmente, cada mensaje debe codificarse de manera proporcional al registro de su probabilidad, pero dado que los códigos de Huffman son un número entero de bits, eso corresponde implícitamente a las probabilidades que son potencias de dos. De ahí una aproximación. Busque el teorema de codificación de Shannons.
8

Sí, siempre es óptimo.

No, no hay un umbral en el que usaría menos espacio para usar datos no codificados de longitud fija.

Encontré varias pruebas en la Web, pero hay suficiente discusión en el artículo de Wikipedia Codificación Huffman .

Esto también cubre otras técnicas que logran una mayor compresión (trabajar fuera del espacio para el cual el código Huffman es óptimo).

Cade Roux
fuente