[IT] Extra points: Dictionary based encoding

Un método de codificación que encontré para está actividad se llama Byte-Pair encoding.

Es uno de los métodos por diccionario más simples que existen.

El procedimiento es muy simple, cuando se encuentran un par de bytes consecutivos y ducho par se repite varias veces en el texto, entonces dicho par de bytes es reemplazado por un byte que no se éste utilizando.
El algoritmo se detiene cuando ya no hay más pares de bytes consecutivos.
Es necesario almacenar el diccionario para poder recuperar la información

Ejemplo 

Codificación

Iniciamos con una cadena de caractéres, con un largo aleatorio, por ejemplo

dcbdbdababdbacbbdabaaaacacacaa

Nuestro alfabeto sería:

 alpha = [a,b,c,d]

Por lo que tenemos los bytes desde "e" hasta "z" si quitamos los caractéres de control y signos de puntuación.

Comienzamos a recorrer la lista para buscar por pares de caractéres:

Iteración 1: Encontramos el par que más se repite bd, asignamos un byte no utilizado:

bd : e

Identificamos:

d c b d b d a b a b d b a c b b d a b a a a a c a c a c a a
     e   e                     e

Sustituimos:

d c e e a b a b d b a c b e a b a a a a c a c a c a a

Iteración 2: Encontramos el par que más se repite ab, asignamos un byte no utilizado:

ab : f

Identificamos:

d c e e a b a b d b a c b e a b a a a a c a c a c a a
         f   f               f

Sustituímos:

d c e e f f d b a c b e f a a a a c a c a c a a

Iteración 3: Encontramos el par que más se repite ca, asignamos un byte no utilizado:

ca : g

Identificamos:

d c e e f f d b a c b e f a a a a c a c a c a a
                                   g   g   g
Sustituímos:

d c e e f f d b a c b e f a a a a g g g a

Iteración 4: Encontramos el par que más se repite aa, asignamos un byte no utilizado:

aa : h

Identificamos:

d c e e f f d b a c b e f a a a a g g g a
                           h   h

Sustituímos:

d c e e f f d b a c b e f h h g g g a

Iteración 5: Encontramos el par que más se repite, aqui encontramos varios pares que se repiten solo una vez (ee, ff, hh, gg), asignamos un byte no utilizado a cada una:

ee : i
ff : j
hh : k
gg : l

Identificamos:

d c e e f f d b a c b e f h h g g g a
     i   j                 k   l

Sustituímos:

d c i j d b a c b e f k l g a

Como ya no hay bytes juntos que se repitan, entonces podemos terminar la ejecución, los resultados serían:

dcbdbdababdbacbbdabaaaacacacaa = 30 carácteres
dcijdbacbefklga = 15 caractéres.

Y el diccionario quedaria

• bd : e
• ab : f
• ca : g
• aa : h
• ee : i
• ff : j
• hh : k
• gg : l

Decodificación

Para la decodificación, primeo debemos girar el diccionario y ordenarlo de forma inversa para buscar por las coincidencias hasta que no encontremos ninguna más:

Cadena original: dcijdbacbefklga

Identificamos: l
Sustituimos por: gg

d c i j d b a c b e f k l g a

Queda:

d c i j d b a c b e f k g g g a

Identificamos: k
Sustituimos por: hh

d c i j d b a c b e f k l g a

Queda:

d c i j d b a c b e f h h g g g a

Identificamos: j
Sustituimos por: ff

d c i j d b a c b e f h h g g g a
Queda:

d c i f f d b a c b e f h h g g g a

Identificamos: i
Sustituimos por: ee

d c i f f d b a c b e f h h g g g a

Queda:

d c e e f f d b a c b e f h h g g g a

Identificamos: h
Sustituimos por: aa

d c i f f d b a c b e f h h g g g a

Queda:

d c e e f f d b a c b e f a a a a g g g a

Identificamos: g
Sustituimos por: ca

d c e e f f d b a c b e f a a a a g g g 

Queda:

d c e e f f d b a c b e f a a a a c a c a c a a
Identificamos: f
Sustituimos por: ab

d c e e f f d b a c b e f a a a a c a c a c a a

Queda:

d c e e a b a b d b a c b e a b a a a a c a c a c a a


Identificamos: e
Sustituimos por: bd

d c e e a b a b d b a c b e a b a a a a c a c a c a a

Queda:

d c b d b d a b a b d b a c b b d a b a a a a c a c a c a a

Y asi se hace el deflate de los datos.


Referencias:

[PDF] Byte pair encoding: a text compression scheme that accelerates pattern matching.

Yusuke Shibatay, 

Masayuki Takeday, 

Takuya Kiday, Shuichi Fukamachiz, 

Ayumi Shinoharay, Takeshi Shinoharaz, 

Setsuo Arikaway

Dept. of Informatics, Kyushu University 33, Fukuoka 812-8581, Japan

f yusuke, kida, takeda, ayumi, arikawag @i.kyushu-u.ac.jp

Dept. of Arti cial Intelligence, Kyushu Institute of Technology, Iizuka 320-8520, Japan

f fukamati, shinog @ai.kyutech.ac.jp