8.2 Compresor

• Un compresor LZ77 trabaja sustituyendo las cadenas que encuentra a la entrada por la referencia donde la cadena aparece en un diccionario. Si dicha referencia ocupa menos bits que la cadena en sí, se produce una compresión de datos.
• La secuencia de símbolos a codificar se procesa de forma secuencial. Para ello se define una ventana deslizante que consta de dos partes: (1) un diccionario y (2) un “buffer”. En el diccionario encontramos las cadenas que ya han sido codificadas y en el buffer, aquellas que van a codificarse.

  

• El compresor emite un código de compresión formado por una terna de enteros ijk, donde i es la posición de la cadena dentro del diccionario, j es la longitud de la cadena y k es el siguiente símbolo que no forma parte de la cadena. A continuación la ventana deslizante se desplaza k + 1 posiciones hacia la dirección del fin de la secuencia de símbolos.
• Una descripción del algoritmo de compresion podría ser:
  1. Sea I el tamaño del diccionario y J el tamaño del buffer, ambos medidos en símbolos.
  2. Introducir los primeros J símbolos en el buffer.
  3. Mientras existan símbolos por codificar:
     1. Sea i la posición de los primeros j símbolos del buffer en el diccionario y k el símbolo que hace que j no pueda ser mas grande.
     2. Escribir ijk.
     3. Introducir los siguientes j + 1 símbolos en el buffer.