Algoritmos eficientes para la construcción de conjuntos óptimos de contextos bi–direccionales

Abstract

La técnica de modelados por contextos usada en problemas de decisión secuencial, como compresión de datos y otros, descompone una secuencia dada entre un conjunto de subsecuencias que son tratadas independientemente. La descomposición se basa en la ocurrencia de ciertas cadenas de símbolos que son elementos de un conjunto finito de contextos. Cada contexto tiene asociado un peso dado por una pérdida numérica generada al procesar la subsecuencia. Por tal motivo es necesario encontrar un conjunto de contextos óptimo (que minimice la pérdida total). En esta tesis los contextos están formados por pares de cadenas y se denominan contextos bi–direccionales. La contribución de este trabajo es presentar estructuras de datos y algoritmos computacionalmente eficientes para encontrar un conjunto óptimo de contextos cuando la longitud de los contextos no está acotada. Se demuestra que el conjunto de todos estos contextos bi–direccionales se puede partir en clases de equivalencia y alcanza con procesar un elemento representativo de cada clase. La estructura presentada es una generalización de árboles de sufijos compactos. Es un grafo enraizado, dirigido, acíclico, donde cada vértice está etiquetado por el elemento representativo de una clase. Recíprocamente a cada clase le corresponde un vértice de este grafo. Las aristas dirigidas (al igual que en los árboles compactos de sufijos) están etiquetados por cadenas de símbolos, con las que se extiende el contexto representado por el vértice origen. Algunos vértices no tienen aristas salientes. Cada uno de los otros vértices tiene dos conjuntos de hijos (cada uno de los cuales extiende una de las direcciones de los contextos). También se describe un algoritmo que reduce la complejidad de orden cúbico a orden cuadrático (en el largo de la cadena). Para ello se hace uso de árboles de sufijos y el cálculo del ancestro común más profundo de varios nodos de un árbol.