Un código de afijo es un código que es simultáneamente un código de prefijo y sufijo. Es decir, ninguna palabra de código no es ni el prefijo ni el sufijo de ninguna otra palabra de código. Los códigos de fijación se pueden decodificar instantáneamente en ambas direcciones (hacia adelante y hacia atrás).
Quiero crear uno que comprima de manera óptima una distribución de símbolos de entrada dada, dado un conjunto de símbolos de salida.
El algoritmo de Huffman (que crea códigos de prefijo) se acerca más, pero debido a su codiciosa estrategia, parece inadecuado para modificaciones con este fin.
¿Cómo se pueden encontrar los códigos de afijo óptimos?
FWIW, me parece probable que haya un PTAS para el problema, siguiendo la idea básica de este documento . (Esto no responde exactamente a su pregunta, pero aún describiré el PTAS aquí en la sección de respuestas, ya que es demasiado largo para caber en un comentario).
Arregle cualquier constante . Sea una instancia del problema, es decir, una distribución de probabilidad en .p [ n ]ϵ>0 p [n]
Digamos que un código (un conjunto de palabras de código) está libre de -fix si ninguna palabra de código en el código que tiene una longitud o menor es un prefijo o sufijo de otra palabra de código.K KK
K p n SK=⌈1/ϵ2⌉ K p n S K K C(S) |S| p S n−|S| K S n−|S| n−|S| S C(S) C0 S C0 K p
fuente