jueves, 25 de abril de 2013

Byte pair encoding

Compresión

Este método es un método de compresión muy simple, este consiste en buscar las repeticiones de pares de letras diferentes dentro de una cadena, por ejemplo la siguiente:
asdasdasadaasdad
  • Por lo tanto el primer par que tenemos es:

                                                                asdasdasadaasdad
 y lo asignamos a Z entonces tenemos que Z= as
  • Después sustituimos dentro de la cadena:

                                                             ZdZdZadaZdad
  • Ahora buscamos el siguiente que mas se repite y lo asignamos a la Y y tenemos que Y=ad 

                                                             ZdZdZadaZdad
  • Y sustituimos:

                                                             ZdZdZYaZdY
  • Ahora tomamos el siguiente par de repeticiones y lo asignamos a W , W=Zd
                                                      ZdZdZdYaZdY
  • Y tenemos lo siguiente:
                                                        WWWYaWY
Y con esto tenemos una cadena de 16 caracteres a 7 caracteres.

Descompresión

Para descomprimir la cadena resultante se utiliza el diccionario que se crea al momento de comprimirlo.(Letras Mayúsculas utilizadas(en este caso)).
  • Z=as
  • Y=ad
  • W=Zd
Después sustituimos cada carácter dentro de la cadena:
                                           WWWYaWY ----> ZdZdZdYaZdY

Después tomamos el siguiente carácter guardado dentro del diccionario y sustituimos en lo que se obtuvo anteriormente:
                                      ZdZdZdYaZdY ------> ZdZdZdadaZdad

Y por ultimo sustituimos la letra restante dentro del diccionrio:
                                     ZdZdZdadaZdad ------> asdasdasdadaaddad

Y listo tenemos la cadena original :)

Referencias: 


1 comentario: