En general, aproximadamente el 50% de la secuencia de símbolos entrantes debería consistir en un símbolo dado para que Huffman lo codificara como un solo bit. La razón de esto es que debido a cómo funciona la codificación de Huffman (la codificación de un símbolo no puede ser el prefijo de otro), al codificar un símbolo con un solo bit, se requiere que el primer bit para cada otro símbolo sea lo opuesto valor (es decir, si un símbolo está codificado como 0, todo lo demás debe comenzar con 1 más al menos un bit más). Como está eliminando la mitad del espacio de codificación posible para cualquier longitud de bit dada, necesita obtener una forma de codificar al menos la mitad de los símbolos que se ingresan para alcanzar el punto de equilibrio.
Tenga en cuenta que hay un caso especial en el que el espacio de símbolos solo consta de 3 símbolos. En tal caso, el símbolo que tenga la mayor frecuencia se codificará con 1 bit (ya que los otros dos serán las variaciones de 2 bit de cualquier valor de primer bit que no se elija) - si 2 o más tienen una probabilidad igualmente mayor, cualquiera de los dos podría estar codificado. Por lo tanto, en el caso de 3 símbolos es posible que un símbolo con, digamos, 34% de probabilidad pueda codificarse teóricamente como un solo bit (por ejemplo, 0) mientras que los otros dos pueden tener 33% o menores probabilidades y codificarse como 10 y 11.
Así que si está considerando todas las posibilidades de, entonces técnicamente cualquier cosa de 1/3 o superior podría codificarse como un solo bit (en el caso de 3 símbolos).
Excepto por el caso binario trivial: si solo hay 2 símbolos, Huffman siempre asigna 1 bit a cada símbolo, sin importar las frecuencias. –
Hay una prueba de esto incluido como apéndice en [esta preimpresión de arxiv] (https://arxiv.org/pdf/cs/0508039.pdf). Lamentablemente, no puedo seguir el razonamiento ... No entiendo por qué es necesariamente cierto que el nodo etiquetado "u" se fusionó antes que los nodos etiquetados como "v1" y "v2". –