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.

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 frecuencia.

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.

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.