Saltar a contenido

Tunstall Coding

Es un método de compresión de datos que se basa en la sustitución de secuencias de bits por códigos de longitud variable, donde los símbolos más frecuentes se representan con códigos más cortos y los menos frecuentes con códigos más largos. Utiliza una técnica de partición de árbol para asignar códigos a los símbolos según su probabilidad de aparición en el conjunto de datos, lo que permite una compresión eficiente al reemplazar secuencias repetitivas con códigos más cortos, reduciendo así el tamaño total de los datos codificados.

Definición

Algoritmo de compresión que opera sobre una secuencia de datos, representada por un conjunto de símbolos \(S\) de longitud \(n\). Sea \(P\) el conjunto de probabilidades de ocurrencia de cada símbolo en la secuencia, donde \(P_i\) representa la probabilidad del símbolo \(s_i \in S\).

El proceso de codificación Tunstall se realiza en los siguientes pasos:

Construcción del árbol de codificación:

Se comienza con un árbol inicial que contiene todos los símbolos individuales como nodos hoja. Se iteran los siguientes pasos para expandir el árbol:

  • Se identifican los nodos hoja con mayor probabilidad y se seleccionan para expandir. Cada nodo seleccionado se divide en subnodos, donde cada subnodo representa un símbolo y se le asigna una probabilidad proporcional a su frecuencia de aparición.
  • Este proceso se repite hasta alcanzar un número prefijado de nodos o hasta que la tasa de compresión deseada se alcance.

Codificación de la secuencia original:

  • Cada símbolo en la secuencia original se reemplaza por su correspondiente código en el árbol generado durante la etapa de construcción. Los códigos generados tienen longitudes variables dependiendo de la profundidad del árbol para representar los símbolos. El algoritmo Tunstall puede ser revertido utilizando el árbol de codificación para decodificar la secuencia comprimida y recuperar la secuencia original.

La tasa de compresión lograda por Tunstall puede aproximarse a través de la fórmula:

\[ \text{tasa de compresion}=\frac{\text{tamaño original}}{\text{tamaño codificado}} \]

donde el tamaño codificado se refiere al número total de bits necesarios para representar la secuencia después de la codificación Tunstall.

Este es un método de compresión sin pérdida que aprovecha la redundancia estadística en los datos para lograr una representación más compacta de la información original.

Ejemplos de aplicación

Reducción de Datos en Sistemas Embebidos

  • En dispositivos con recursos limitados, como sistemas embebidos o dispositivos IoT (Internet de las cosas), donde el espacio de almacenamiento es escaso, Tunstall Encoding podría aplicarse para comprimir datos generados por sensores. Por ejemplo, en la compresión de lecturas de sensores ambientales (temperatura, humedad, presión) que tienden a repetirse, permitiendo un uso más eficiente de la memoria del dispositivo.

Compresión de Imágenes en Aplicaciones Móviles

  • En aplicaciones móviles o servicios de mensajería que involucran el intercambio de imágenes, Tunstall Encoding podría emplearse para comprimir datos de imágenes. Por ejemplo, representando la frecuencia de colores o patrones en imágenes simples, como logotipos o iconos, permitiendo una rápida transmisión y menor consumo de ancho de banda en dispositivos móviles.

Compresión de Archivos de Audio

  • En aplicaciones de transmisión de audio o servicios de música en línea, Tunstall Encoding podría ser utilizado para comprimir archivos de audio. Por ejemplo, al representar la frecuencia de ciertos patrones de sonido o segmentos musicales recurrentes, reduciendo el tamaño de los archivos de audio y optimizando la transmisión y el almacenamiento de datos de audio.
import heapq
from collections import defaultdict

class Node:
    def __init__(self, symbol, frequency):
        self.symbol = symbol
        self.frequency = frequency
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.frequency < other.frequency

def build_frequency_table(input_string):
    frequency_table = defaultdict(int)
    for c in input_string:
        frequency_table[c] += 1
    return frequency_table

def build_tunstall_tree(frequency_table, max_symbols):
    pq = [Node(symbol, freq) for symbol, freq in frequency_table.items()]
    heapq.heapify(pq)

    while len(pq) > 1 and len(pq) < max_symbols:
        lowest_nodes = heapq.nsmallest(2, pq)
        new_node = Node(None, sum(node.frequency for node in lowest_nodes))
        new_node.left, new_node.right = lowest_nodes

        heapq.heappop(pq)
        heapq.heappop(pq)
        heapq.heappush(pq, new_node)

    return pq[0]  # Return the root of the tree

def generate_codewords(root):
    codewords = {}

    def traverse(node, code):
        if node:
            if node.symbol is not None:
                codewords[node.symbol] = code
            traverse(node.left, code + '0')
            traverse(node.right, code + '1')

    traverse(root, '')
    return codewords

def encode(input_string, codewords):
    encoded = ''.join(codewords[symbol] for symbol in input_string)
    return encoded

def decode(encoded, root):
    decoded = ''
    current = root

    for bit in encoded:
        if bit == '0':
            current = current.left
        else:
            current = current.right

        if current.symbol is not None:
            decoded += current.symbol
            current = root

    return decoded

# Ejemplo de uso
input_string = "ABRACADABRA"
frequency_table = build_frequency_table(input_string)
print(len(set(input_string)))
max_symbols = 100 
root = build_tunstall_tree(frequency_table, max_symbols)

codewords = generate_codewords(root)
print("Codewords:")
for symbol, code in codewords.items():
    print(f"Símbolo: {symbol} - Código: {code}")

encoded = encode(input_string, codewords)
print("Encoded:", encoded)

decoded = decode(encoded, root)
print("Decoded:", decoded)

Referencias