26 de abril de 2013

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

1 comentario:

  1. OK; 2+2. En la explicación sería bueno aclarar de qué largo son los candidatos de repetición y cómo se generan.

    ResponderEliminar

Nota: solo los miembros de este blog pueden publicar comentarios.