Lz77
| ||||||
LZ77 o denominado como lz1 es un compresor basado en algoritmo sin pérdida se utilizan cuando la información a comprimir es crítica y no se puede perder información, por ejemplo en los archivos ejecutables, tablas de bases de datos, o cualquier tipo de información que no admita pérdida. El modelo lz77 es muy usado porque es fácil de implementar y es bastante eficiente.
Sumario
Historia
En 1977 Abraham Lempel y Jacob Ziv presentaron su modelo de compresión basado en diccionario, para compresión de texto se refiere a la compresión sin pérdida para cualquier tipo de datos. Hasta la fecha todos los algoritmos de compresión desarrollados eran básicamente compresores estáticos. El nuevo modelo fue llamado lz77 (lz son la iniciales de sus creadores y 77 el año en que se creó).
Funcionamiento
En este algoritmo el codificador analiza el texto como una secuencia de caracteres, mediante una ventana deslizable compuesta por dos partes; un buffer de anticipación que es la opción que está a punto de ser codificada y un buffer de búsqueda (la ventana en sí), que es la parte dónde se buscan secuencias iguales a las existentes en el buffer de anticipación. Para codificar el contenido, o parte de él, del buffer de anticipación, se busca la secuencia igual en el buffer de búsqueda y la codificación resulta en indicar esta repetición como una tripleta [offset, longitud, carácter siguiente].
Donde:
- Offset es la distancia desde el principio del buffer de anticipación hasta el comienzo de la secuencia repetida.
- Longitud es la cantidad de caracteres repetidos.
- Carácter siguiente es el símbolo siguiente a la secuencia en el buffer de anticipación.
Pero, ¿cómo sabe el descompresor si lo que lee es un par desplazamiento/tamaño o un byte sin comprimir?. La respuesta es simple, usamos un prefijo, un bit que actúa como una bandera, de forma similar a un interruptor con dos estados que nos permite saber qué tipo de datos vienen a continuación. Si el prefijo es 0, entonces lo que viene es un byte sin comprimir. Si, por el contrario, el prefijo es 1, entonces lo que sigue a continuación es un par desplazamiento/tamaño. A estos prefijos también se les llama “banderas”. El par desplazamiento/tamaño es llamado una palabra clave. Una palabra clave es un grupo de bits (o bytes) que contienen alguna clase de información usada por el compresor y el descompresor. La otra salida posible de LZ77 es un literal, la cual es simplemente un byte sin comprimir, de manera que la salida de LZ77 puede ser de tres formas:
- Literales: son simplemente bytes sin comprimir.
- Palabras clave: en nuestro caso son pares tamaño/desplazamiento.
- Banderas: simplemente nos indican si los datos que hay a continuación son literales o palabras clave.
Ahora, como ejemplo, veamos de nuevo nuestra cadena y una salida real de un algoritmo LZ77:
#Obtener ‘a’. Sin coincidencia. Bandera 0. Literal ’a’. #Obtener ‘b’. Sin coincidencia. Bandera 0. Literal ’b’. #Obtener ‘ ’. Sin coincidencia. Bandera 0. Literal ’ ’. #Obtener ‘a’. Coincidencia. Bandera 1. Palabra clave: desplazamiento = 0, tamaño = 2.
Como puede verse la bandera sólo tiene dos estados posibles, de manera que sólo necesitamos un bit para representarla. Ahora no deberíamos representar las banderas como bytes completos, deberíamos trabajar con bits. La salida de esta compresión es llamada un flujo de bits, porque es un flujo de símbolos de tamaño variable, y la unidad mínima es el bit.
Ejemplo
Comprimiendo
Imaginemos que estamos comprimiendo el texto “ab ab”, leemos hasta “ab ” y lo escribimos sin comprimir, luego leemos “ab” y escribimos lo siguiente: con el “desplazamiento” de 0 se halló una coincidencia de dos bytes repetidos. Quedaría así “ab <3,2,eof)> ” (eof fin de fichero).
Descomprimiendo
Para descomprimir “ab <3,2,eof)> ” Lo primero que tenemos es “ab ” después de la posición 0 que es a se toman dos caracteres que serían ab en entonces la cadena quedaría “ab ab”.
Seudo Código
Recordemos cómo trabaja lz77, uno se encuentra en una posición dada y trata de hallar hacia atrás (porque se está seguro de que el descompresor ya ha decodificado esos bytes cuando uno se encuentra en dicha posición) una coincidencia, bytes que son iguales a los bytes en la posición actual; si se encuentran se escribe una palabra clave, de otra forma se escribe una literal para poder seguir comprimiendo.
Secuencia básica: Compresor
- Guardar el tamaño del archivo a comprimir.
- Repetir hasta que no hayan más bytes para comprimir.
- Escanear el buffer de entrada comenzando en posición_actual - tamaño_de_ventana_corrediza hasta el byte actual que estamos comparando. (Notar que el descompresor no puede copiar bytes de una posición desde donde sus bytes no han sido previamente definidos).
- ¿Hemos encontrado un byte igual al actual?
- Caso Si:
- Caso Si:
- Caso No:
- Continúa la búsqueda.
- Caso No:
- Si no se encuentra ninguna coincidencia, simplemente se escribe un byte sin comprimir (también se escribe un literal si no hay datos en la ventana corrediza).
- Debe recordar poner la bandera a 0.
Secuencia básica: Descompresor
- Se lee el tamaño del archivo sin comprimir.
- Se repite hasta que se ha descomprimido todo el archivo.
- Se lee un bit (la bandera).
- Si es 0:
- Si es 1:
Código en C#
Comprimir
A este método se le pasa por parámetro la longitud de la ventana, el tamaño del buffer de búsqueda y la cadena a comprimir y el retorna otra cadena con los valores después de la compresión. BB -> Tamaño del buffer de búsqueda. BA -> Tamaño del buffer de anticipación.
public string Metodo_LZ77_Comprimir(int Long_Ventana, int BB, string cadena)
{
string lista = "";
int pos_cursor = 0;
int BA=Long_Ventana-BB;
while (pos_cursor < cadena.Length)
{
int longitud = 0;
int offset = 0;
string carat = cadena[pos_cursor].ToString();
int w = pos_cursor - 1;
int temp = BB;
int temp2;
int otra = 0;
while (w >= 0 && temp-- > 0)
{
temp2 = BA;
if (cadena[w] == cadena[pos_cursor])
{
int offset_temp = otra + 1;
int pos = pos_cursor + 1;
int b = w + 1;
int lon = 1;
while (pos < cadena.Length && cadena[b] == cadena[pos] && temp2-- > 2)
{ b++; lon++; pos++; }
if (lon >= longitud)
{
longitud = lon;
offset = offset_temp;
if (pos == cadena.Length)
carat = "eof";
else
carat = cadena[pos].ToString();
}
} w--; otra++;
}
lista += string.Format("<{0},{1},{2}>", offset, longitud, carat);
pos_cursor += longitud + 1;
}
cadenas_comprimidas.Add(lista);
return lista;
}
Descomprimir
Este se le pasa por parámetro la cadena a descomprimir y este retorna la cadena deseada.
public string Metodo_LZ77_Descomprimir_arreglado(string ca)
{
string cinta = "";
int pos_inicio = 0, pos_fin = 0;
for (int i = 0; i < ca.Length-1; i++)
{
if (ca[i] == '<' && char.IsDigit(ca[i + 1]))
{ pos_inicio = i + 1; break; }
else
cinta += ca[i];
}
string final = "";
for (int i = ca.Length - 1; i > 1; i--)
{
if (ca[i] == '>' && (ca[i - 2] == ',' || char.IsLetterOrDigit(ca[i - 1])))
{ pos_fin = i; break; }
else
final += ca[i];
}
List<Datos> lista = new List<Datos>();
int cont = 0;
string temp="";
int offset = 0;
int lon = 0;
string carat = "";
if (pos_fin - pos_inicio > 4)
{
for (int i = pos_inicio; i <= pos_fin; i++)
{
if (ca[i] == ',' && cont < 2)
{
if (cont == 0)
offset = int.Parse(temp);
else
lon = int.Parse(temp);
temp = "";
cont++;
}
else if (ca[i] == '>' && temp.Length > 0)
{
carat = temp;
i++;
Datos dat = new Datos(offset, lon, carat);
lista.Add(dat);
offset = 0; lon = 0; carat = ""; cont = 0; temp = "";
}
else
{
temp += ca[i];
}
}
}
for (int i = 0; i < lista.Count; i++)
{
int pos = cinta.Length - lista[i].Offset;
int lone = lista[i].Longitud;
string cade = "";
if (lista[i].Cod_carater != "eof")
cade = lista[i].Cod_carater;
while (lone-- > 0)
cinta += cinta[pos++];
cinta += cade;
}
cinta += final;
return cinta;
}
