LZ78

Definición

El algoritmo LZ78 es un método de compresión sin pérdida desarrollado por Abraham Lempel y Jacob Ziv en 1978. Es uno de los algoritmos de compresión más famosos y ha servido de base para múltiples formatos y aplicaciones, como el compresor compress de Unix y el formato de imagen GIF. El algoritmo es parte de la familia de compresión Lempel-Ziv y es conocido por su estructura regular, lo que lo hace adecuado para representaciones comprimidas que permiten acceso óptimo y para índices de texto comprimido que soportan búsqueda de patrones.

Funciona construyendo un diccionario dinámico de subcadenas a medida que procesa la secuencia de entrada. La idea principal es identificar patrones repetidos y sustituirlos por referencias a un diccionario. Implementaciones comunes implican el uso de un trie (LZ Trie) o diccionarios (hashmap).

Complejidades

Espacio: \(O(z \log n)\), donde \(z\) es el tamaño del diccionario.
Tiempo: \(O(n \log \sigma)\), siendo \(n\) la longitud del texto y \(\sigma\) el tamaño del alfabeto.

Compresión

El algoritmo LZ78 comprime un texto \(T[1...n]\) segmentándolo en una secuencia de frases únicas. Consideremos la comprensión del texto \(T\) donde se ha procesado \(T[1...i-1]\) en \(r\) frases \(B_0,B_1,B_2,...,B_{r-1}\), donde \(B_0\) representa la cadena vacía.

Para determinar la siguiente frase \(B_r\):

Encontrar el prefijo más largo \(T[i...j-1]\) de \(T\) que coincida con alguna frase previa \(B_q\) donde \(q < r\).
Definir \(B_r = B_q\times T_j\) donde \(T[j]\) es el siguiente símbolo en el texto.
Representar \(B_r\) como el par \((q,T[j])\).
Avanzar en el texto desde la posición \(j+1\).

Descompresión

Crear un diccionario \(D\) vacío donde \(D[0]\) representa la cadena vacía.
Procesar cada par \((q,c)\) en la secuencia de entrada:
Si \(q=0\), c es una frase nueva y se añade como \(D[i]=c\), donde \(i\) es el índice actual.
Si \(q \neq 0\), esto indica que \(D[i]=D[q]+c\), donde \(D[q]\) es la frase previa y \(c\) el carácter.
Añadir \(D[r]\) al diccionario y actualizar el índice \(i\).
Concatenar el texto \(D[r]\)
Repetir hasta completar todos los pares en la entrada comprimida.

Ejemplo de uso

\(T = aababcaabbac\)

Compresión

\(T = a|ab|abc|aa|b|ba|c\)

\(i\)	\(\text{Factor}\)	\(\text{Encoding}\)
\(1\)	\(a\)	\((0, a)\)
\(2\)	\(ab\)	\((1, b)\)
\(3\)	\(abc\)	\((2, c)\)
\(4\)	\(aa\)	\((1, a)\)
\(5\)	\(b\)	\((0, b)\)
\(6\)	\(ba\)	\((5, a)\)
\(7\)	\(c\)	\((0, c)\)

\(S=\{(0, a),(1, b),(2, c) , (1, a) , (0, b) , (5, a) , (0, c)\}\)


\(\text{LZ Trie para } T = aababcaabbac\)

Descompresión

\(i\)	\(\text{Encoding}\)	\(\text{Descompresión}\)	\(\text{String}\)
\(1\)	\((0, a)\)	\(D[1] = a\)	\(a\)
\(2\)	\((1, b)\)	\(D[2] = D[1] + b = ab\)	\(aab\)
\(3\)	\((2, c)\)	\(D[3] = D[2] + c = abc\)	\(aababc\)
\(4\)	\((1, a)\)	\(D[4] = D[1] + a = aa\)	\(aababcaa\)
\(5\)	\((0, b)\)	\(D[5] = b\)	\(aababcaab\)
\(6\)	\((5, a)\)	\(D[6] = D[5] + a = ba\)	\(aababcaabba\)
\(7\)	\((0, c)\)	\(D[7] = c\)	\(aababcaabbac\)

Implementación

class LZ78Compressor:
    def __init__(self):
        self.dictionary = {0: ""}
        self.next_index = 1

    def compress(self, input_string):
        output = []
        current_prefix = ""

        for char in input_string:
            if (current_prefix + char) in self.dictionary:
                current_prefix += char
            else:
                output.append((self.dictionary.get(current_prefix, 0), char))
                self.dictionary[current_prefix + char] = self.next_index
                self.next_index += 1
                current_prefix = ""

        if current_prefix:
            output.append((self.dictionary.get(current_prefix, 0), ""))

        return output

    def decompress(self, compressed_data):
        self.dictionary = {0: ""}
        self.next_index = 1
        output = ""

        for index, char in compressed_data:
            current_string = self.dictionary[index] + char
            output += current_string

            self.dictionary[self.next_index] = current_string
            self.next_index += 1

        return output

compressor = LZ78Compressor()
compressed_data = compressor.compress("aababcaabbac")
print(compressed_data)

decompressed_data = compressor.decompress(compressed_data)
print(decompressed_data)

Referencias

Ziv, J., Lempel, A. (1977). A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory.
Ziv, J., Lempel, A. (1978). Compression of Individual Sequences via Variable-Rate Coding. IEEE Transactions on Information Theory.
Arroyuelo, D., Cánovas, R., Navarro, G., & Raman, R. (2017). LZ78 Compression in Low Main Memory Space. In Lecture Notes in Computer Science (pp. 38–50). Springer International Publishing.
Arroyuelo, D., Cánovas, R., Fischer, J., Köppl, D., Löbel, M., Navarro, G., & Raman, R. (2021). Engineering Practical Lempel-Ziv Tries. In ACM Journal of Experimental Algorithmics (Vol. 26, pp. 1–47). Association for Computing Machinery (ACM).
Zhao, F. & Muthusamy, N. (2012). 5418 Parallel Computer Architecture and Programming Project Report: Implementation and Comparison of Parallel LZ77 and LZ78 Algorithms.