En la teoría de la codificación , la desigualdad de Kraft-McMillan proporciona una condición necesaria y suficiente para la existencia de códigos separables y prefijos que tienen un conjunto determinado de longitudes de palabras clave.
Sean dados dos conjuntos finitos arbitrarios , que se denominan, respectivamente, alfabeto codificado y alfabeto codificado . Sus elementos se denominan caracteres , y las cadenas (secuencias de longitud finita) de caracteres se denominan palabras . La longitud de una palabra es el número de caracteres que la componen.
Como alfabeto de codificación, a menudo se considera un conjunto: el llamado alfabeto binario o binario.
Un esquema de codificación alfabética (o simplemente código (alfabético) ) es cualquier mapeo de los caracteres del alfabeto codificado en palabras del alfabeto de codificación, que se denominan palabras de código . Usando el esquema de codificación, cada palabra del alfabeto codificado se puede asociar con su código , la concatenación de palabras de código correspondientes a cada carácter de esta palabra.
Un código se denomina separable (o únicamente decodificable ) si no se pueden asociar dos palabras del alfabeto codificado con el mismo código.
Un código de prefijo es un código alfabético en el que ninguna de las palabras del código es un prefijo de ninguna otra palabra del código. Cualquier código de prefijo es separable.
Teorema de Macmillan (1956) . Se dan los alfabetos codificados y codificadores que consisten en y símbolos, respectivamente, y se dan las longitudes deseadas de las palabras de código: . Entonces, una condición necesaria y suficiente para la existencia de códigos separables y prefijos con un conjunto dado de longitudes de palabras clave es el cumplimiento de la desigualdad: |
Esta desigualdad se conoce como desigualdad de Craft-MacMillan . Fue deducida por primera vez por Leon Kraft en su tesis de maestría en 1949 [1] , pero consideró solo los códigos de prefijo, por lo que cuando se analizan los códigos de prefijo, esta desigualdad a menudo se denomina simplemente desigualdad de Kraft . En 1956, Brockway Macmillan demostró la necesidad y suficiencia de esta desigualdad para una clase más general de códigos, los códigos separables. [2]
Cualquier árbol binario arraigado puede verse como una descripción gráfica de un código de prefijo sobre un alfabeto binario: los caracteres del alfabeto codificado corresponden a las hojas del árbol, y la ruta en el árbol desde la raíz hasta la hoja especifica su código ( el camino consiste en una secuencia de movimientos "izquierda" y "derecha" que corresponden a los caracteres 0 y 1).
Para tales árboles, la desigualdad de Kraft-McMillan establece que:
donde es el conjunto de hojas del árbol, y es la profundidad de la hoja , el número de aristas en el camino desde la raíz hasta .
Para el árbol de la figura de la derecha, tenemos: