Saltar a contenido

Codificación Hu-Tucker

Definición

La codificación Hu-Tucker, propuesta por T. C. Hu y Alan C. Tucker , es un algoritmo de compresión de datos estadístico que genera códigos libres de prefijo. Recibe un alfabeto de entrada de tamaño fijo, y devuelve una salida con códigos de tamaño variable, donde ningún código del alfabeto de salida es prefijo de otro.

Lo que se destaca de esta codificación es el poder crear Alphabetic Binary Search Trees Óptimos, lo que minimiza el tiempo de desencriptación para las consultas.

¿Cómo funciona su algoritmo?

A simple vista, se ve como una alteración a los códigos de Huffman. Sin embargo, a pesar de que ambas dependen de las frecuencias del alfabeto entregado, y ambas hacen uso de estos para crear un Binary Tree, ¡no podrían ser más distintas!.

La codificación Hu-Tucker se divide en tres partes fundamentales; Combinación, Asignación de Niveles y Reconstrucción.

Combinación

Es similar a la combinación de Huffman; Se ordenan los carácteres en orden de frecuencia (a los caracteres les llamaremos nodos), y se agrupan en parejas, por propiedad de un Binary Tree, donde se forman "bloques", los cuales guardan la suma de sus frecuencias. Sin embargo, a diferencia de la combinación de Huffman, hay dos nuevas reglas;

  1. Sólo se pueden combinar dos bloques si no hay un nodo original entre medio
  2. Sólo se pueden combinar si el nodo izquierdo es el de menor frecuencia disponible para el derecho, y el derecho es el de menor frecuencia para el izquierdo. En caso de un empate, se elige el que esté más a la izquierda.

Tomemos, por ejemplo, el string "BANANAS_NANAS", cuyas frecuencias para [_,A,B,N,S] son [1,5,1,4,2]

Local Image

Local Image

Local Image

Asignación de niveles

Si te has fijado en las figuras anteriores, te darás cuenta que he anotado los pesos de los nodos en azul. Esto es para esta fase, en donde les asignamos el peso de las hojas (los símbolos) con respecto a la raíz;

Símbolo Frequencia Peso
_ 1 3
A 5 2
B 1 3
N 4 2
S 2 2

Con esto en mano, podemos pasar a la siguiente fase.

Reconstrucción

Hay dos maneras de hacerlo, por el método "Level by Level" o la del stack.

En la forma de Level by Level se toma la secuencia dada,{3,3,2,2,2}, y se agrupan los nodos que tengan el mismo nivel, de menor a mayor, en parejas. En caso que haya un número impar de nodos, se agrupa el último del nivel analizado, con el primero del siguiente nivel a analizar. El último nodo que quede en la secuencia, será del nivel cero.

En la forma del stack, se crea un queue que guarde, en orden ascendente, los pesos, (En nuestro ejemplo, sería {B,N,S,_,A}) un stack vacío. Para la reconstrucción, se sigue el siguiente patrón:

  1. Si los dos elementos en el tope del stack son del mismo nivel 'b', son colocados en el árbol como dos nodos hijos y en su lugar en el stack habrá un peso de 'b-1'
  2. Si lo anterior no se cumple, se elimina el elemento del frente del queue y se pasa al stack.

Siguiendo con nuestro ejemplo, el proceso sería:

    • Queue: 2(A) ,2(N) ,2(S) ,3(_) ,3(B)
  2. Stack:
    • Queue: 2,2,3,3
  2. Stack: 2
    • Queue: 2,3,3
  2. Stack: 2,2
    • Queue: 2,3,3
  2. Stack: 1
    • Queue: 3,3
  2. Stack: 1,2
    • Queue: 3
  2. Stack: 1,2,3
    • Queue:
  2. Stack: 1,2,3,3
    • Queue:
  2. Stack: 1,2,2
    • Queue:
  2. Stack: 1,1
    • Queue:
    • Stack:

Ambos métodos nos llevan al mismo árbol. Una vez obtenido este árbol, a los hijos izquierdos le damos '0' como bit de terminación, y '1' para los derechos :

Local Image

Lo que, codificado, es:

Símbolo Código
_ 000
A 01
B 001
N 10
S 11

Y el string de "BANANAS_NANAS" pasa a ser "0010110011001110001001100111", el cual es libre de prefijo.

Implementación

Para el siguiente código se usó como base el código de Francisco Claude, Rodrigo Canovas y Miguel A. Martinez-Prieto (referencia [5]), la cual es una implementación completa de la codificación Hu Tucker. Para más detalles, se puede ver dicha implementación aquí.

El código apuntado es de alta complejidad, por lo que a continuación estará una re-interpretación simplificada de dicha implementación, parte por parte, de los tres procesos hechos para mostrar su funcionamiento.

Combinación

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Node {       //Estructura para el nodo
    int frequency;
    char symbol;
    Node* left;
    Node* right;
    bool stat; 
    int weight;

    Node(int freq, char sym, int w){
        frequency = freq; 
        symbol= sym; 
        left = nullptr; 
        right = nullptr;
        stat = true; //Si es true, no está combinado. En caso contrario, si está combinado
        weight = w; // Para la fase de combinación, consideraremos este árbol como invertido. Osea, el root tendrá el mayor peso
    }
};

//Los sortings son hechos con Selection Sort porque se busca que el código sea fácil de comprender.

vector<Node*> sortByFrequency(vector<Node*> array){
    int n = array.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n ; ++j) {
            if (array[j]->frequency < array[i]->frequency) {
                swap(array[j],array[i]);
            }
        }
    }
    return array;
}

Node* merge(Node* x, Node* y, int weight){
   //Función que forma al nodo padre, sumando sus frecuencias
    Node* w = new Node(x->frequency + y->frequency,x->symbol + y->symbol, weight);
    w->left = x;
    w->right = y;
    w->stat = false;
    return w;
}



int findMinimum(vector<Node*> array, Node* n1, int iterator){ //Función que nos encuentra el mínimo nodo posible para el nodo que estamos analizando
    Node* n2 = n1;
    int aux = iterator;
    for(int i = iterator; i < array.size() ; ++i){
        if(array[i]->frequency <= n2->frequency){
            aux = i;
            n2 = array[i];
        }
    }
    return aux;
}

bool isCompatible(vector<Node*> array, int x, int y){
    Node* aux;
    for(int i = x + 1; i < y ; ++i){
        if(array[i]->stat == true){
            return false;
        }
    }
    return true;    
}

Node* combine(vector<int>& frequencies, vector<char>& symbols) {
    vector<Node*> nodes;

    for (size_t i = 0; i < frequencies.size(); ++i) {
        nodes.push_back(new Node(frequencies[i], symbols[i],0));
    } //Se crea la secuencia, cabe mencionar que todos los nodos tienen peso 0.

    nodes = sortByFrequency(nodes); //Ordenamiento por frecuencia
    int i = 0;int level = 0;
    while (nodes.size() > 1){ //El último nodo que quedará será el de la raíz

            int iterator = findMinimum(nodes,nodes[i],i); 
            if(i > iterator){ // Asegurar que x sea menor que iterator
                swap(i,iterator);
            }      
            if(isCompatible(nodes,i,iterator)){   //Si es compatible, se produce el merge
                Node* aux1 = nodes[i];
                Node* aux2 = nodes[iterator];
                Node* aux3 = merge(aux1,aux2,aux1->weight + 1);
                nodes.erase(nodes.begin()+i-1);
                nodes.erase(nodes.begin()+iterator-1);
                nodes.insert(nodes.begin()+i,aux3);
            }
            ++i; // Y se analiza otro nodo
            if(i >= nodes.size() - 1){ // Funcion para que el analisis sea circular
                i = 0;
            }
        }
    return nodes[0]; //Retorna la raiz
}

Asignación de niveles

Nota: Esta función no compila con la etapa anterior, porque al eliminar elementos con vector.erase() se pierden los datos.

vector<Node*> sortByWeight(vector<Node*> array){ //Selection sort para ordenar un vector seguns sus pesos
    int n = array.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n ; ++j) {
            if (array[j]->weight < array[i]->weight) {
                swap(array[j],array[i]);
            }
        }
    }
    return array;
}



vector<Node*> levelAssignment(Node* root,vector<Node*> array_weights){
    //El nodo principal es el de root, y el array_weights es para guardar la secuencia de pesos

    cout<<"a"<<endl;
    if (root->stat == false)
    {
        // Si es falso, significa que es un nodo mergeado. Por lo que
      // No es un carácter 

        levelAssignment(root->left, array_weights);
        levelAssignment(root->right, array_weights); //loops

    }
    else
    {
        // Encontramos una hoja

      cout<<"a"<<endl;
        array_weights.push_back(root); // Agregamos nuestra hoja a la nueva secuencia
    }

    sortByWeight(array_weights); //La ordenamos para preparar el siguiente proceso. Nuevamente, es con selection sort.

    for (size_t i = 0; i < array_weights.size(); ++i) {
        std::cout << array_weights[i]->weight << " ";
    }

    cout << endl;

    return array; //se devuelve la nueva secuencia
}

Reorganización

Se ocupa el método de stack. Nuevamente, no se puede aplicar el código de Asignación de niveles porque le falta el array principal, pero sí funciona dándole un vector de nodos.

Node* reconstruct(vector<Node*>& weights){
    weights = sortByWeight(weights); //En el Level by Level, se supone que ya está ordenado por sus pesos, pero igual estará aca para recordar
    queue<Node*> Q; //El queue
    stack<Node*> S; //El stack
    for (int i = 0; i < weights.size(); ++i) {
        Q.push(weights[i]); //Se llena la queue primero
    }

    while (!Q.empty()) { //Nuestro primer objetivo es vaciar la queue
        Node* x = Q.front(); // x va a ser el frente de la queue 
        Q.pop(); //Independiente de lo que pase, x ya no seguirá en la queue, esta es la condición de avance del loop.
        Node* y = nullptr; // y va a ser la cima del stack
        if(!S.empty()){
            y = S.top();
        }              
        //Si el stack está vacío, o no coincide el front de queue con el del stack, se apila en el stack
        if (S.empty() || (y->weight != x->weight) ) {

            S.push(x);


        } else {

            // Por lo contrario, se crea el nodo padre de x e y, 
            Node* z = new Node(x->frequency + y->frequency, 'a',x->weight - 1);
            z->left = x;
            z->right = y;
            z->stat = false;
            S.pop(); // Se elimina y
            S.push(z); // Se agrega su nodo padre al stack

        }

    }
    while(S.size() != 1){ //Nuestro segundo objetivo es dejar vacío el stack, mergeando los nodos que queden
        Node* x = S.top();
        S.pop();
        Node* y = S.top();
        Node* z = new Node(x->frequency + y->frequency, 'a',x->weight - 1);
        z->left = x;
        z->right = y;
        z->stat = false;
        S.pop();
        S.push(z);   // Se sigue así hasta llegar al nodo con peso 0; La raiz
    }
    // Y Se devuelve la raiz, que tiene todos los hijos
    return S.top();
}

Finalmente, para codificar se usa 'obtainCodewords()' en el código original, y consiste en agregarles bits de terminación según su posición respecto al padre; si es un nodo izquierdo (terminación 0) o derecho (terminación 1).

Referencias

[1] Rochester Institute of Technology, 'Hu-Tucker algorithm for building optimal alphabetic binary search trees'. Disponible en: https://scholarworks.rit.edu/theses/6484/

[2] T.C. Hu, Lawrence L. Larmore, and J. David Morgenthaler; 'Optimal Integer Alphabetic Trees in Linear Time'. Disponible en: https://cse.hkust.edu.hk/mjg_lib/bibs/DPSu/DPSu.Files/9my26xpaakxbrecx.pdf

[3] mit.edu, Clase de Profesor Kleitman 'Finding Efficient Compressions; Huffman and Hu-Tucker Algorithms' . Disponible en: https://math.mit.edu/~djk/18.310/18.310F04/huffman_algorithms.html

[4] mit.edu, 'The Hu-Tucker Algorithm: Shortest Alphabetical Codes.' Apuntes de un alumno anónimo sobre la clase del artículo anterior. Disponible en: https://math.mit.edu/~djk/18.310/Lecture-Notes/PeterShor-hu-tucker.html

[5] Repositorio de Gihub 'libCSD', Algoritmo Hu-Tucker de Francisco Claude, Rodrigo Canovas y Miguel A. Martinez-Prieto. Disponible en: https://github.com/migumar2/libCSD/blob/master/HuTucker/HuTucker.cpp