Incremental Encoding

Definición

También conocido como "front compression", "back compression", o "front coding", es un tipo de algoritmo de compresión "delta encoding" donde los prefijos comunes (o sufijos) y sus largos, son almacenados para que no se necesite duplicarlos. Este algoritmo es particularmente útil para comprimir datos ordenados, como por ejemplo una lista de palabras de un diccionario.

Ejemplo:

Input	Prefijo común	Salida comprimida
myxa	sin palabra precedente	0 myxa
myxophyta	'myx'	3 ophyta
myxopod	'myxop'	5 od
nab	sin prefijo común	0 nab
nabbed	'nab'	3 bed
nabbing	'nabb'	4 ing
nabit	'nab'	3 it
nabk	'nab'	3 k
nabob	'nab'	3 ob
nacarat	'na'	2 carat
nacelle	'nac'	3 elle
64 bytes		46 bytes

La codificación utilizada para almacenar el largo del prefijo común varía de una aplicación a otra. Las técnicas típicas incluyen almacenar el valor como un solo byte; "delta encoding", la cual almacena solo el cambio en el largo del prefijo común; y varios códigos universales. Puede ser combinado con otras técnicas de compresión de datos sin pérdida como "entropy encoding" y codificadores de diccionario, para comprimir los restantes sufijos.

Aplicaciones

Bases de Datos e Índices: se utiliza en bases de datos y estructuras de índices (como árboles B o Trie) para reducir el espacio requerido para almacenar cadenas de texto.

Recuperación de Información: En sistemas como motores de búsqueda, la compresión frontal puede almacenar de manera eficiente índices o diccionarios donde muchas palabras comparten raíces o prefijos comunes.

Archivos de Texto: Es útil para comprimir archivos de texto donde ciertos patrones o palabras se repiten con frecuencia.

GNU Locate: se utiliza como punto de partida en un índice de nombres de archivos y directorios

Implementación

Ejemplo C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Función para comprimir una lista de palabras usando "incremental encoding"
vector<string> comprimirFrontal(const vector<string>& palabras) {
    vector<string> resultado;
    if (palabras.empty()) {
        return resultado;
    }

    string palabraAnterior = palabras[0];
    resultado.push_back(palabraAnterior); // Parte con la primera palabra completa

    for (size_t i = 1; i < palabras.size(); ++i) {
        const string& actual = palabras[i];
        size_t j = 0;

        // Encuentra el prefijo común más largo
        while (j < actual.size() && j < palabraAnterior.size() && actual[j] == palabraAnterior[j]) {
            ++j;
        }

        if (j > 0) {
            // Añade la longitud del prefijo común y el sufijo restante
            resultado.push_back(to_string(j) + actual.substr(j));
        } else {
            // No hay prefijo común, añade la palabra completa
            resultado.push_back(actual);
        }

        palabraAnterior = actual;
    }

    return resultado;
}

int main() {
    vector<string> palabras = {"gato", "gatito", "gata", "gatas"};
    auto palabrasComprimidas = comprimirFrontal(palabras);

    cout<<"Lista original:"<<endl;
    for (const auto& palabra : palabras) {
        cout << palabra << endl;
    }

    cout<<"Compresión:"<<endl;
    for (const auto& palabra : palabrasComprimidas) {
        cout << palabra << endl;
    }

    return 0;
}

Referencias

[1] Wikipedia, Incremental Encoding [En línea]. Disponible: https://en.wikipedia.org/wiki/Incremental_encoding

[2] "Introduction to Algorithms" Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein

[3] "Algorithms" Robert Sedgewick y Kevin Wayne

[4] "Database System Concepts" Abraham Silberschatz, Henry F. Korth y S. Sudarshan.