Métodos de diccionario-Byte pair encoding

Este método consiste en encontrar el par de bytes que más se repita en la cadena y sustituirlo por otro carácter que no se este usando.

Compresión
El string que usaré es "cdabcaabfeedefeede"

• El que más se repite que podemos ver es el par "ee", entonces sustituimos este por X, lo qe nos da 
• cdabcaabfXdefXde
• X = ee
• Ahora el que más se repite es "de" y lo podemos sustituir con Y, 
• cdabcaabfXYfXY
• Y = de
• "XY" es ahora si el que más se repite y podemos sustituirlo con Z, de la siguiente manera:
• cdabcaabfZfZ
• Z = XY
• "fZ" es ahora el que más se repite y cambiamos "fZ" por M, lo que nos da:
• cdabcaabMM
• M = fZ
• El siguiente que hay que sustituir es "aa", lo podemos hacer con Q, y queda así:
• cdabcQbMM
• Q = aa
• Y por último se sustituye "MM" por algun otro que puede ser R:
• cdabcQbR
• R = MM

Lo que nos da como resultado de "cdabcaabfeedefeede" a "cdabcQbR" se redujo de 18 a 8 bytes.

Descompresión

Para esto se usa el diccionario que ya tenemos que es el siguiente:

• R = MM
• Q = aa
• M = fZ
• Z = XY
• Y = de
• X = ee
  
  
•  Comenzamos con "cdabcQbR" y se tiene que R = MM:
• cdabcQbMM
• Lo siguiente es sistituir la "Q" por "aa"
• cdabcaabMM
• Ahora la M por fZ:
• cdabcaabfZfZ
• Enseguida se sustituye la "Z" por "XY"
• cdabcaabfXYfXY
• Despues "Y" por "de"
• cdabcaabfXdefXde
• Y por ultimo "X" por "ee" y tenemos la cadena inicial:
• cdabcaabfeedefeede

 Referencias

Byte pair encoding (). . [ONLINE] Available at: http://www.csse.monash.edu.au/cluster/RJK/Compress/problem.html. [Last Accessed 25 de abril de 2013].