Saltar a contenido

PPM (Prediction by Partial Matching)

Definición del Algoritmo

PPM es un método basado en la predicción y codificación aritmética. El objetivo del algoritmo es predecir el siguiente símbolo en una secuencia basándose en los símbolos anteriores. Para esto, PPM utiliza un modelo de orden variable que almacena las probabilidades de ocurrencia de cada símbolo en el contexto de los caracteres previos. En lugar de asignar una probabilidad fija a cada símbolo, PPM ajusta el modelo conforme se procesa la secuencia, permitiendo adaptarse a patrones específicos del contenido.

PPM se clasifica en distintos órdenes de contexto (por ejemplo, orden-0, orden-1, etc.), en donde el orden determina el número de símbolos anteriores que se utilizan para predecir el siguiente. El modelo aritmético entonces utiliza estas probabilidades para codificar los datos en un formato comprimido, que luego puede ser descomprimido con la misma probabilidad.

Ejemplo de Uso

Imaginemos que queremos comprimir una cadena de texto con el contenido: ABABAC. Al usar PPM de orden-1:

  1. El algoritmo comienza analizando cada símbolo y su contexto anterior de un símbolo (orden-1).
  2. Si se encuentra A, el contexto previo es B, por lo que se incrementa la probabilidad de A después de B.
  3. Así, conforme se procesa la cadena, PPM construye un modelo en el cual A es más probable que aparezca después de B, y C es menos probable.

El siguiente ejemplo es más complejo y demuestra cómo manejar contextos más largos y variados, y cómo las cadenas reales pueden ser comprimidas y descomprimidas correctamente utilizando PPM.

Cadena:

BANANA_BANDANA

Desglose del Modelo

  1. Orden 3 (Contexto de longitud 3):
  2. 'BAN' → A (1)
  3. 'ANA' → N (1), D (1)
  4. 'NAN' → A (1)

  5. '_BA' → N (1)

  6. Órdenes menores (longitudes 2 y 1):

  7. 'BA' → N (1)
  8. 'AN' → A (2), D (1)

  9. 'NA' → N (1), D (1)

  10. Contexto vacío (frecuencias globales):

  11. 'B (2), A (6), N (4), _ (1), D (2)'

Detalles

Compresión

La cadena se comprime considerando el contexto de mayor orden disponible. Cada símbolo se codifica utilizando el modelo generado. Si no hay suficiente información para un contexto dado, se recurre a un escape para usar un contexto de menor orden.

Descompresión

La cadena descomprimida es idéntica a la original porque el modelo captura correctamente las relaciones entre los símbolos en cada contexto.

Este ejemplo muestra cómo el uso de contextos de orden variable en PPM permite capturar patrones y generar un modelo adaptativo para la compresión.

Para imágenes, PPM puede ser efectivo en aquellas con patrones repetitivos de color. Los valores de los píxeles en una imagen en escala de grises o de un canal de color en imágenes en color se pueden representar como secuencias de datos. PPM entonces puede usarse para comprimir la imagen al predecir los valores de píxeles basados en los píxeles previos en la secuencia.

Implementación del Algoritmo

La implementación básica de un compresor PPM requiere:

  1. Crear un modelo de contexto: almacenar las probabilidades de símbolos en diferentes órdenes de contexto.
  2. Codificación aritmética: utilizar la probabilidad de cada símbolo en el contexto actual para codificar los datos.
  3. Escape y actualización de contexto: cuando un símbolo no aparece en el contexto actual, se usa un mecanismo de “escape” para un contexto de menor orden.

Esta es una implementación en C++ para un compresor PPM simplificado de orden-1 que utiliza un modelo de contexto para comprimir datos.

#include <map>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

// Función para construir el modelo PPM basado en el contexto
map<string, map<char, int>> construirModeloPPM(const string& cadena, int orden) {
    map<string, map<char, int>> modelo;

    for (int i = 0; i < cadena.size() - orden; i++) {
        string contexto = cadena.substr(i, orden);
        char simbolo = cadena[i + orden];

        // Si el contexto no existe en el modelo, inicializa un nuevo mapa para él
        if (modelo.find(contexto) == modelo.end()) {
            modelo[contexto] = map<char, int>();
        }

        // Incrementa la frecuencia del símbolo en el contexto dado
        modelo[contexto][simbolo]++;
    }

    return modelo;
}

// Función para predecir el próximo símbolo basándose en el modelo PPM y el contexto
char predecirSimbolo(const map<string, map<char, int>>& modelo, const string& contexto) {
    if (modelo.find(contexto) != modelo.end()) {
        auto probabilidades = modelo.at(contexto);

        // Encuentra el símbolo con la mayor frecuencia en el contexto
        auto simbolo = max_element(probabilidades.begin(), probabilidades.end(),
            [](const pair<char, int>& a, const pair<char, int>& b) {
                return a.second < b.second;
            });

        return simbolo->first;
    } else {
        return '\0'; // Retorna un símbolo de escape o vacío si no hay predicción
    }
}

int main() {
    string cadena = "ABABAC";
    int orden = 1;

    // Construye el modelo de contexto para el orden dado
    auto modelo = construirModeloPPM(cadena, orden);

    // Muestra el modelo de predicción generado
    for (const auto& contexto : modelo) {
        cout << "Contexto: " << contexto.first << " -> ";
        for (const auto& simbolo : contexto.second) {
            cout << simbolo.first << ": " << simbolo.second << " ";
        }
        cout << endl;
    }

    // Ejemplo de predicción
    string contexto = "A";
    char simboloPredicho = predecirSimbolo(modelo, contexto);
    cout << "Simbolo predicho para el contexto '" << contexto << "': " << simboloPredicho << endl;

    return 0;
}

Descripción del Pseudocódigo

Función construirModeloPPM

Crea un modelo de contexto de orden-1 (un mapa de contextos y símbolos) a partir de una cadena de entrada. Cada contexto de tamaño orden se asocia con un símbolo, almacenando la frecuencia de ocurrencia de ese símbolo en el contexto.

Función predecirSimbolo

Predice el próximo símbolo basado en el contexto actual y el modelo de contexto. Si el contexto está en el modelo, devuelve el símbolo con la mayor probabilidad de aparecer en base a la frecuencia de ocurrencia.

main

Construye el modelo de contexto a partir de una cadena y luego imprime el modelo. También realiza una predicción para un contexto dado.

Complejidades del Algoritmo PPM

El algoritmo PPM (Prediction by Partial Matching) tiene varias etapas clave: construcción del modelo, predicción, codificación y descompresión. Las complejidades asociadas dependen de cómo se implementen estas etapas y de los parámetros como el orden del modelo y el tamaño del alfabeto.

1. Construcción del Modelo

La construcción del modelo implica analizar la secuencia de entrada y construir los contextos con sus probabilidades.

Proceso

  • Iterar sobre la secuencia de longitud \(n\).
  • Para cada posición \(i\), generar un contexto de longitud \(k\) (orden del modelo) y actualizar las frecuencias de los símbolos.

Complejidad

\(\(O(n \cdot k)\)\) - \(n\): Tamaño de la secuencia. - \(k\): Orden del modelo.

En el peor caso, la complejidad puede crecer si los contextos no se repiten, ya que se requiere insertar nuevos contextos en el modelo.

2. Predicción

La predicción implica buscar un contexto en el modelo para predecir el siguiente símbolo.

Proceso

  • Consultar el modelo para obtener el contexto y su distribución de probabilidades.
  • Si no se encuentra el contexto, realizar un "escape" al contexto de menor orden.

Complejidad

\(\(O(k)\)\) - En el peor caso, se necesitan \(k\) consultas (para cada nivel de contexto hasta el orden 0).

3. Codificación Aritmética

La compresión utiliza las probabilidades almacenadas para codificar los símbolos mediante codificación aritmética.

Proceso

  • Para cada símbolo, ajustar los intervalos basados en las probabilidades del modelo.

Complejidad

\(\(O(n \cdot \log(|\Sigma|))\)\) - \(n\): Longitud de la secuencia. - \(|$\Sigma$|\): Tamaño del alfabeto.

La codificación aritmética tiene una dependencia logarítmica del tamaño del alfabeto \(|$\Sigma$|\), ya que divide los intervalos para cada símbolo.

4. Actualización del Modelo

Después de cada símbolo, el modelo se actualiza para reflejar las nuevas frecuencias.

Proceso

  • Incrementar los conteos en el contexto actual y todos los contextos de menor orden.

Complejidad

\(\(O(k)\)\) - Cada símbolo requiere actualizar \(k\) contextos.

5. Descompresión

La descompresión invierte el proceso de codificación aritmética y utiliza los mismos contextos para reconstruir la secuencia original.

Complejidad

\(\(O(n \cdot k)\)\) La descompresión tiene una complejidad similar a la construcción del modelo, ya que también necesita buscar contextos y realizar operaciones de codificación aritmética.

Complejidad Total

Sumando las etapas principales, la complejidad global para el algoritmo PPM es aproximadamente:

\(\(O(n \cdot (k + \log(|\Sigma|)))\)\) - \(n\): Longitud de la secuencia. - \(k\): Orden del modelo. - \(|$\Sigma$|\): Tamaño del alfabeto.

Factores que Impactan el Rendimiento

  1. Orden del modelo (k): A mayor orden, se necesita más memoria y tiempo para almacenar y buscar contextos.
  2. Tamaño del alfabeto (|\(\Sigma\)|): Afecta directamente la eficiencia de la codificación aritmética.
  3. Tamaño del texto (n): Secuencias más largas incrementan proporcionalmente los costos de construcción y codificación.
  4. Repetición en la secuencia: Secuencias con más patrones repetidos reducen los costos, ya que el modelo almacena menos contextos únicos.

Optimización

  • Memoria: Usar estructuras de datos eficientes (como tries o hashmaps).
  • Tiempo: Limitar el orden del modelo o precomputar contextos comunes.
  • Codificación: Optimizar la implementación de la codificación aritmética para reducir el impacto del tamaño del alfabeto.

Referencias

Libros

  • "Text Compression" de Timothy C. Bell, John G. Cleary, y Ian H. Witten: Este libro cubre varios algoritmos de compresión, incluyendo el PPM, y ofrece una explicación detallada de los modelos probabilísticos y de la codificación aritmética.
  • "Data Compression: The Complete Reference" de David Salomon: Este libro proporciona un panorama completo sobre compresión de datos y cubre tanto técnicas de compresión sin pérdida como con pérdida, con un capítulo dedicado a PPM.

Artículos Académicos

  • Cleary, J.G., & Witten, I.H. (1984). Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications. Este es el artículo original donde se describe PPM, explicando el mecanismo de adaptación y actualización de contexto.
  • Moffat, A. (1990). Implementing the PPM data compression scheme. IEEE Transactions on Communications. Este artículo detalla la implementación práctica de PPM y aborda los problemas comunes en la codificación aritmética.

Recursos en línea

  • Wikipedia: Prediction by Partial Matching: Proporciona una visión general del algoritmo y explica los conceptos básicos para su comprensión.
  • Implementaciones en GitHub: Existen varias implementaciones de PPM en lenguajes como Python y C++ que pueden ser útiles para estudiar ejemplos de código en mayor profundidad.