Puntos extra: LZW algoritmo de compersion con diccionario.

Algoritmo de codificación

1. Inicializar el diccionario para todos los bloques de una longitud (D = {O, V, E​​}).
2. Buscar el bloque más largo W que ha aparecido en el diccionario.
3. Codificar W por su índice en el diccionario.
4. Añadir W seguido por el primer símbolo de la manzana siguiente al diccionario.
5. Vaya al paso 2.

Estos son los paso que se hacen para realizar el algoritmo, pero explicare mejor con un poco de representación.

Primero tenemos los datos(generados con random en python en mi caso puede ser un texto escrito):

Datos: V, O, E, E, O, V, O, V, V, O

y el diccionario con las letras que aparecen con el índice del 1 al 3 ya que son 3 letras diferentes

Así exactamente:

       Diccionario.

índice             entrada                                                          
    1                           V
    2                           O
    3                           E              

Se irán agregando índices y nuevas combinaciones de letras conforme vayamos barriendo los datos.

- > Ahora empezamos a revisar los datos dándoles el valor que corresponde a su índice

Datos: V, O, E, E, O, V, O, V, V, O

Entonces V = 1 dando el valor que se encuentra en el diccionario. (como podemos ver anteriormente)

Seguimos barriendo los datos, checando la letra anterior y la letra que le sigue, si no estan en nuestro diccionario los agregamos.

Datos: V, O, E, E, O, V, O, V, V, O 

       Diccionario.

índice             entrada                                                          
    1                           V
    2                           O
    3                           E
    4                          VO

Después de agregar al diccionario le damos el valor a la letra O que seria igual a 2.

- > Seguimos barriendo los datos, de igual manera

Datos: V, O, E, E, O, V, O, V, V, O 

Pasando a la siguiente letra en conjunta a la que le hemos dado valor y agregamos al diccionario si no esta.

       Diccionario.

índice             entrada                                                          
    1                           V
    2                           O
    3                           E
    4                          VO
    5                          EO

Y le damos el valor a E según nos muestra el diccionario en este caso 3.


- > Seguimos barriendo los datos de igual manera

Datos: V, O, E, E, O, V, O, V, V, O 

De igual manera en conjunto con la letra ya evaluada con la que sigue y si no se encuentra en el diccionario agregamos.

       Diccionario.
índice             entrada                                                          
    1                           V
    2                           O
    3                           E
    4                          VO
    5                          EO
    6                          EE

y le damos el valor al E que en este caso es 3 nuevamente.

-> Ahora viene algo interesante cuando vamos a checar las siguientes letras nos damos cuenta de que estas si están en nuestro diccionario.

 Datos: V, O, E, E, O, V, O, V, V, O

Entonces este no se agrega y solamente se le da el valor que se encuentra en nuestro diccionario.  Que es el valor de 5 como vemos en en la tabla anterior

- > Ahora como hemos elegido una datos que si estaban en el diccionario se agarraran 3

 Datos: V, O, E, E, O, V, O, V, V, O

Y como no esta en el diccionario lo agregamos.

       Diccionario.
índice             entrada                                                          
    1                           V
    2                           O
    3                           E
    4                          VO
    5                          EO
    6                          EE
    7                         EOV

- >  Ahora cuando vamos a evaluar  otra letra que existe solo le damos su valor. En este caso 4

  Datos: V, O, E, E, O, V, O, V, V, O

      Diccionario.
índice             entrada                                                          
    1                         V
    2                         O
    3                         E
    4                        VO
    5                        EO
    6                        EE
    7                       EOV

- > Así nos seguimos hasta terminar el texto.

Así nos queda nuestro diccionario.

      Diccionario.

índice             entrada                                                          
   1                            V
   2                            O
   3                            E
   4                           VO
   5                           EO
   6                           EE
   7                          EOV
   8                          VOV
   9                           VV

y el resultado codificado es: 1 2 3 3 5 1 4 1 4

Y para decodificarlo es solo de mirar el diccionario 


Referencia:
http://www.data-compression.com/lempelziv.html (otorgado por la doctora)