En la teoría de la codificación , la desigualdad de Kraft-McMillan da una condición necesaria y suficiente para la existencia de un código prefijo [1] (en la versión de Leon G. Kraft) o un código decodificable de forma única (en la versión de Brockway McMillan ) para un conjunto dado de longitudes de palabras de código . Sus aplicaciones para prefijar códigos y árboles a menudo encuentran uso en la informática y la teoría de la información .
La desigualdad de Kraft se publicó en Kraft (1949) . Sin embargo, el artículo de Kraft solo analiza los códigos de prefijo y atribuye el análisis que conduce a la desigualdad a Raymond Redheffer . El resultado se descubrió de forma independiente en McMillan (1956) . McMillan prueba el resultado para el caso general de códigos decodificables unívocamente, y atribuye la versión de los códigos de prefijo a una observación hablada en 1955 por Joseph Leo Doob .
Aplicaciones e intuiciones
La desigualdad de Kraft limita la longitud de las palabras de código en un código de prefijo : si se toma una exponencial de la longitud de cada palabra de código válida, el conjunto de valores resultante debe verse como una función de masa de probabilidad , es decir, debe tener una medida total menor o igual que a uno. La desigualdad de Kraft se puede pensar en términos de un presupuesto limitado que se gastará en palabras clave, siendo las palabras clave más cortas más caras. Entre las propiedades útiles que se derivan de la desigualdad se encuentran las siguientes afirmaciones:
- Si la desigualdad de Kraft se mantiene con una desigualdad estricta, el código tiene cierta redundancia .
- Si la desigualdad de Kraft se cumple con la igualdad, el código en cuestión es un código completo. [2]
- Si la desigualdad de Kraft no se cumple, el código no se puede decodificar de forma única .
- Para cada código decodificable de forma única, existe un código de prefijo con la misma distribución de longitud.
Declaración formal
Deje que cada símbolo de origen del alfabeto
codificarse en un código decodificable único sobre un alfabeto de tamaño con longitudes de palabras en clave
Luego
Por el contrario, para un conjunto dado de números naturales satisfaciendo la desigualdad anterior, existe un código decodificable único sobre un alfabeto de tamaño con esas longitudes de palabras en clave.
Ejemplo: árboles binarios
Se puede considerar que cualquier árbol binario define un código de prefijo para las hojas del árbol. La desigualdad de Kraft establece que
Aquí la suma se toma sobre las hojas del árbol, es decir, los nodos sin hijos. La profundidad es la distancia al nodo raíz. En el árbol de la derecha, esta suma es
Prueba
Prueba de códigos de prefijo
Primero, demostremos que la desigualdad de Kraft se cumple siempre que el código para es un código de prefijo.
Suponer que . Dejar ser el completo -arbol de profundidad (así, cada nodo de a nivel posee niños, mientras que los nodos a nivel son hojas). Cada palabra de longitud sobre un -ary alfabeto corresponde a un nodo en este árbol en profundidad . Lala palabra en el código de prefijo corresponde a un nodo; dejar ser el conjunto de todos los nodos hoja (es decir, de nodos en profundidad ) en el subárbol de arraigado en . Ese subárbol siendo de altura, tenemos
Dado que el código es un código de prefijo, esos subárboles no pueden compartir hojas, lo que significa que
Por lo tanto, dado que el número total de nodos en profundidad es , tenemos
de donde se sigue el resultado.
Por el contrario, dada cualquier secuencia ordenada de números naturales,
satisfaciendo la desigualdad de Kraft, se puede construir un código de prefijo con longitudes de palabras de código iguales a cada eligiendo una palabra de longitud arbitrariamente, descartando luego todas las palabras de mayor longitud que lo tengan como prefijo. Allí, de nuevo, interpretaremos esto en términos de nodos hoja de un-arbol de profundidad . Primero elija cualquier nodo del árbol completo en profundidad; corresponde a la primera palabra de nuestro nuevo código. Dado que estamos construyendo un código de prefijo, todos los descendientes de este nodo (es decir, todas las palabras que tienen esta primera palabra como prefijo) se vuelven inadecuados para su inclusión en el código. Consideramos a los descendientes en profundidad(es decir, los nodos de hojas entre los descendientes); existentales nodos descendientes que se eliminan de la consideración. La siguiente iteración elige un nodo (superviviente) en profundidad y quita más nodos de hoja, y así sucesivamente. Después iteraciones, hemos eliminado un total de
nodos. La pregunta es si necesitamos eliminar más nodos hoja de los que realmente tenemos disponibles.en total - en el proceso de construcción del código. Dado que la desigualdad de Kraft se mantiene, de hecho tenemos
y así se puede construir un código de prefijo. Tenga en cuenta que, dado que la elección de los nodos en cada paso es en gran medida arbitraria, en general se pueden construir muchos códigos de prefijo adecuados diferentes.
Prueba del caso general
Ahora demostraremos que la desigualdad de Kraft se mantiene siempre que es un código decodificable de forma única. (No es necesario probar lo contrario, ya que ya lo hemos probado para los códigos de prefijo, que es una afirmación más sólida).
Denotar . La idea de la prueba es obtener un límite superior en por y demuestre que solo puede durar para todos Si . Volver a escribir como
Considere todas las potencias m , en forma de palabras , dónde son índices entre 1 y . Tenga en cuenta que, dado que se supuso que S era decodificable de forma única, implica . Esto significa que cada sumando corresponde exactamente a una palabra en. Esto nos permite reescribir la ecuación para
dónde es el número de palabras de código en de longitud y es la longitud de la palabra de código más larga en . Por un-Alfabeto de letras solo hay posibles palabras de longitud , entonces . Usando esto, llegamos al límite superior:
Tomando el -th root, obtenemos
Este límite es válido para cualquier . El lado derecho es 1 asintóticamente, por lo que debe mantenerse (de lo contrario, la desigualdad se rompería por un ).
Construcción alternativa para el inverso
Dada una secuencia de números naturales,
satisfaciendo la desigualdad de Kraft, podemos construir un código de prefijo como sigue. Defina la i- ésima palabra de código, C i , para que sea la primeradígitos después del punto de base (por ejemplo, punto decimal) en la base r representación de
Tenga en cuenta que según la desigualdad de Kraft, esta suma nunca es mayor que 1. Por lo tanto, las palabras de código capturan el valor total de la suma. Por tanto, para j > i , la primeralos dígitos de C j forman un número mayor que C i , por lo que el código no tiene prefijos.
Notas
- ^ Portada, Thomas M .; Thomas, Joy A. (2006), "Compresión de datos", Elementos de la teoría de la información (2ª ed.), John Wiley & Sons, Inc, págs. 108-109, doi : 10.1002 / 047174882X.ch5 , ISBN 978-0-471-24195-9
- ^ De Rooij, Steven; Grünwald, Peter D. (2011), "LA SUERTE Y EL ARREPENTIMIENTO EN LA INFERENCIA DE LONGITUD DE DESCRIPCIÓN MÍNIMA", Filosofía de la Estadística (1ª ed.), Elsevier, p. 875, ISBN 978-0-080-93096-1
Referencias
- Kraft, Leon G. (1949), Un dispositivo para cuantificar, de agrupación, y la codificación de amplitud modulada pulsos , Cambridge, MA: MS Tesis, Departamento de Ingeniería Eléctrica, Instituto de Tecnología de Massachusetts , hdl : 1721,1 / 12390.
- McMillan, Brockway (1956), "Dos desigualdades implícitas en descifrabilidad única", IEEE Trans. Inf. Theory , 2 (4): 115-116, doi : 10.1109 / TIT.1956.1056818.