Codificación de Tunstall

En informática y teoría de la información , la codificación de Tunstall es una forma de codificación entrópica que se utiliza para la compresión de datos sin pérdidas .

La codificación de Tunstall fue el tema de la tesis doctoral de Brian Parker Tunstall en 1967, mientras estudiaba en el Instituto Tecnológico de Georgia. El tema de esa tesis fue "Síntesis de códigos de compresión sin ruido" ^{[ 1 ].}

Su diseño es un precursor del Lempel-Ziv .

A diferencia de los códigos de longitud variable , que incluyen la codificación Huffman y Lempel-Ziv , la codificación Tunstall es un código que asigna símbolos fuente a un número fijo de bits. ^{[ 2 ]}

Tanto los códigos de Tunstall como los códigos de Lempel-Ziv representan palabras de longitud variable mediante códigos de longitud fija. ^{[ 3 ]}

A diferencia de la codificación de conjuntos típica , la codificación de Tunstall analiza una fuente estocástica con palabras clave de longitud variable.

Se puede demostrar que, para un diccionario suficientemente grande, el número de bits por letra de origen puede ser arbitrariamente cercano a${\displaystyle H(U)}$, la entropía de la fuente. ^{[ 4 ]}

El algoritmo requiere como entrada un alfabeto de entrada.${\displaystyle {\mathcal {U}}}$junto con una distribución de probabilidades para cada palabra de entrada. También requiere una constante arbitraria.${\displaystyle C}$, que es un límite superior al tamaño del diccionario que calculará. El diccionario en cuestión,${\displaystyle D}$Se construye como un árbol de probabilidades, en el que cada arista está asociada a una letra del alfabeto de entrada. El algoritmo es el siguiente:

D := árbol de${\displaystyle |{\mathcal {U}}|}$hojas, una por cada letra en${\displaystyle {\mathcal {U}}}$. Mientras${\displaystyle |D|<C}$: Convertir la hoja más probable en árbol con${\displaystyle |{\mathcal {U}}|}$hojas.

Imaginemos que queremos codificar la cadena "hola, mundo". Supongamos además (de forma algo irrealista) que el alfabeto de entrada es${\displaystyle {\mathcal {U}}}$ Contiene únicamente caracteres de la cadena "hello, world" — es decir, 'h', 'e', ​​'l', ',', ' ', 'w', 'o', 'r', 'd'. Por lo tanto, podemos calcular la probabilidad de cada carácter basándonos en su aparición estadística en la cadena de entrada. Por ejemplo, la letra L aparece tres veces en una cadena de 12 caracteres: su probabilidad es${\displaystyle 3 \over 12}$.

Inicializamos el árbol, comenzando con un árbol de${\displaystyle |{\mathcal {U}}|=9}$hojas. Cada palabra está, por lo tanto, directamente asociada a una letra del alfabeto. Las 9 palabras que obtenemos así se pueden codificar en una salida de tamaño fijo de${\displaystyle \lceil \log _ {2}(9)\rceil =4}$bits.

Luego tomamos la hoja de mayor probabilidad (aquí,${\displaystyle w_{1}}$), y convertirlo en otro árbol de${\displaystyle |{\mathcal {U}}|=9}$hojas, una por cada carácter. Recalculamos las probabilidades de esas hojas. Por ejemplo, la secuencia de dos letras L ocurre una vez. Dado que hay tres ocurrencias de letras seguidas de una L, la probabilidad resultante es${\displaystyle {1 \over 3}\cdot {3 \over 12}={1 \over 12}}$.

Obtenemos 17 palabras, cada una de las cuales puede codificarse en una salida de tamaño fijo.${\displaystyle \lceil \log _ {2}(17)\rceil =5}$bits.

Tenga en cuenta que podríamos iterar más, aumentando el número de palabras en${\displaystyle |{\mathcal {U}}|-1=8}$cada vez.

La codificación de Tunstall requiere que el algoritmo conozca, antes de la operación de análisis, cuál es la distribución de probabilidades para cada letra del alfabeto. Este problema es común a la codificación de Huffman .

El hecho de que requiera una salida de bloque de longitud fija la hace inferior a Lempel-Ziv , que tiene un diseño similar basado en diccionarios, pero con una salida de bloque de tamaño variable.

Este es un ejemplo de un código Tunstall que se utiliza para leer (para transmitir) cualquier dato que esté codificado, por ejemplo, mediante codificación polinómica. Este ejemplo en particular ayuda a modificar la base de los datos de 2 a 3 en un flujo, evitando así costosas rutinas de modificación de base. Con la modificación de base estamos particularmente limitados por la 'eficiencia' de las lecturas, donde idealmente${\textstyle \log _{n}}$Los bits se utilizan en promedio para leer el código. Esto garantiza que al utilizar la nueva base, que está obligada a utilizar en la mejor...${\textstyle \log _{n}}$En términos de bits por código, nuestras lecturas no reducen el margen de eficiencia de la transmisión, razón por la cual empleamos la modificación de la base. Por lo tanto, podemos utilizar el mecanismo de lectura para modificar la base y transmitir datos de manera eficiente a través de canales con bases diferentes. Por ejemplo, transmitir datos binarios a través de canales MLT-3 con mayor eficiencia en comparación con el mapeo de códigos (con un gran número de códigos sin usar).

Básicamente, estamos leyendo datos binarios perfectamente codificados o "datos implícitos" con el propósito de transmitirlos mediante canales de base 3. Consulte los nodos hoja en el árbol ternario de Tunstall. Como podemos ver, la lectura dará como resultado que el primer dígito sea "B" el 25% de las veces, ya que tiene una probabilidad implícita del 25%, siendo de longitud 2 al intentar leer datos implícitos. Una "B" de este tipo de lectura no continúa, pero con una probabilidad del 75% leemos "A" o "C", lo que requiere otro código. Por lo tanto, la eficiencia de la lectura es 2,75 (longitud promedio del código Huffman de tamaño 7) / 1,75 (longitud promedio del código Tunstall de base 3 de 1 o 2 dígitos) =${\textstyle 1.57142857}$lo cual es según el requisito muy cercano a${\textstyle \log _ {2}3=1.5849625}$lo que se calcula en una eficiencia de${\textstyle 99.15\%}$. De esta forma, podemos transmitir los símbolos utilizando canales de base 3 de manera eficiente.