Métodos de Diccionario: Byte Pair Encoding

Teoría de la Información y Métodos de Codificación
Puntos Extra

Veamos un ejemplo sencillo de compresión de información usando el método Byte Pair Encoding.

Codificación

La cadena de texto que voy a decodificar es la siguiente:

bbadefedbbafecedbbade

• La parte que más se repite en el texto es bba y la sustituimos por W.
  WdefedWfecedWde
• Luego tenemos cuatro posibles alternativas, sustituir ed, fe, Wde y edW ya que aparecen la misma cantidad de veces, pero como las últimas dos tienen más caracteres será mejor elegir uno de ellos. Cambiaré Wde por X.
  XfedWfecedX
• Y como ya no hay muchos elementos que se repiten cambiaremos fe por Y.
  XYdWYcedX

Nos resulta una tabla para decodificación como sigue.

W = bba
X = Wde
Y = fe

Y la cadena codificaca resulto así:
XYdWYcedX

Decodificación

Entonces si partimos de la tabla anterior, podemos recuperar la cadena original.

• De XYdWYcedX primero cambiamos las Y por fe.
  XfedWfecedX
• Ahora cambiamos las X por Wde.
  WdefedWfecedWde
• Y por último la W la cambiamos por bba.
  bbadefedbbafecedbbade

Y con esto logramos llegar a la cadena de texto original.

Referencias:
Byte Pair Encoding