Métodos adaptativos

Métodos adaptativos de compresión

Hola, esta entrada trata sobre los métodos adaptativos de compresión de datos, para esta actividad se nos encargó inventar, implementar y evaluar nuestro propio método adaptativo de compresión.

Como ya lo había comentado en mi post anterior (no está de más); la compresión de información es el proceso de codificar de una manera efectiva con el objetivo de reducir el número de bits necesarios para representar cierta información.

En la tarea pasada vimos un algoritmo que cumple con las tareas antes mencionadas, pero esta vez se nos pidió desarrollar un método de compresión dinámico o adaptativo.

Esto quiere decir que no hay un cálculo de frecuencia de los símbolos usados (como la pasada tarea en codificación de Huffman), estos métodos adaptativos son principalmente usados en el streaming de información ya que se adaptan a los cambios que se localizan en las características de los datos.

Debo mencionar que a mi no se me ocurrió ningún algoritmo donde pudiera implementar este tipo de método, sin embargo; en previas lecturas cuando realicé la tarea anterior (Huffman) conocí algunos tipos de compresión adaptativos, por ejemplo el LZW (Lempel-Ziv-Welsh) que es un sistema adaptativo del LZ (de Lempel y Jacob Ziv).

Con el sistema LZW es posible crear "al vuelo" y en una sola pasada un diccionario de cadenas que se encuentren dentro del texto a comprimir mientras al mismo tiempo se procede a su codificación.

Para explicar de una manera práctica este método podemos comenzar con un diccionario de 3 caracteres, cada uno con una codificación del 1 al 3.

Tomemos de entrada la siguiente cadena: ABABBABCABABBA

 El algoritmo de compresión LZW hace lo siguiente:

Toma el primer caracter de entrada (s), luego toma el que le sigue(c), la salida (output), que será el código que representará a la cadena original, será el equivalente al valor del código que tiene el caracter s en nuestro diccionario, luego el código para nuestro nuevo string va aumentando una unidad y el nuevo string se guarda en nuestro diccionario (junto con su valor de código) para poder contar con patrones que luego se puedan repetir. El método hace lo mismo hasta que el contenido de nuestro mensaje sea nulo.

Para la descompresión podemos pintar una tabla similar, porque prácticamente se sigue el mismo proceso:

Noten que ahora la columna de output es la cadena original que introducimos.

Bien, yo codifiqué en python este método:

En algunas de las notas que leí, mencionan que la relación de compresión de este método es de aproximadamente de un tercio del archivo; también mencionan que se utiliza en formatos universales como el GIF o el TIFF.

Yo realicé unas sencillas pruebas midiendo la proporción de compresión:

Prueba 1

---

Prueba 2

---

Prueba 3

---

Prueba 4

Conclusiones

Bueno, como lo mencioné antes, en algunas notas mencionan que la relación de compresión es de aproximádamente un tercio del archivo. En mis pruebas lo máximo que obtuve fue comprimir a más de la mitad y seguía conforme iba aumentando el largo del mensaje original.

Una de las desventajas es que hay que agregar al diccionario los caracteres que vas a usar, y haciendo un diagnóstico más detallado nos podemos dar cuenta que muchos de los caracteres que agregamos ni siquiera se usan, ocupando demasiada memoria de una manera inecesaria en el diccionario.
 

Mi repositorio de git: https://github.com/eddypre/M-todosCodificaci-n

Bibliografía:

Compression adaptive
http://elisa.dyndns-web.com/~elisa/teaching/comp/info/adaptive.pdf

Cualquier duda o aclaración pueden ponerla en los comentarios. 

Saludos a todos!

Algoritmo de Huffman

Algoritmo de Huffman 

Hola en esta entrada hablaré sobre el algoritmo de Huffman, este algoritmo se usa precisamente para construir códigos de Huffman, lo que hace es tomar un alfabeto de n símbolos, también toma las frecuencias para cada símbolo, luego produce un código de Huffman con estos elementos.

El objetivo de construir códigos de Huffman es el de la compresión de datos, es decir, expresar de una manera distinta (más corta, obviamente) la misma información.

---

A continuación explicaré a detalle el funcionamiento del algoritmo.

Vamos a obtener el código de Huffman de la palabra: "ingeniero".
Lo primero a realizar es obtener las frecuencias de cada elemento de la sentencia, es decir, las veces que aparece cada caracter en nuestra palabra u oración, dependiendo el caso.

En nuestro caso quedaría de la siguiente manera.

Lo siguiente es ordenar estos caracteres en función a las frecuencias obtenidas, de menor a mayor y dejándo solo el caracter con su correspondiente frecuencia, quedaría de la siguiente manera.

Lo siguiente es la construcción de un árbol binario mediante la unión de nodos que contienen el caracter y su respectiva frecuencia, los nodos que tenemos hasta ahorita son los siguientes.

Ahora lo que toca hacer es ir uniendo los nodos consecutivos en pares, sumaremos las frecuencias de esos dos nodos y luego con ellos crearemos un nuevo nodo. El nuevo nodo contendrá un caracter "null", seguido de la frecuencia obtenida al sumar las 2 frecuencias de los nodos con que se formó. Para entender mejor el concepto realizaremos este paso con los primeros 2 nodos de nuestro conjunto. El resultado es el siguiente.

Noten que ahora el inicio es de nuestra lista es otro, ahora está al inicio el tercer nodo que teníamos en nuestra lista anterior, los nodos que retiramos ahora se encuentran dentro del nuevo nodo que formamos con la suma de sus respectivas frecuencias. El nuevo nodo es colocado al final de la lista.

Ahora, si seguimos el mismo procedimiento podemos concluir que obtendremos un árbol binario, donde las hojas del mismo serán los caracteres de nuestra palabra. Al seguir realizando el mismo procedimiento obtendremos lo siguiente.

Luego.

Hacemos el mismo procedimiento con los nodos nuevos, se crea un nodo nuevo con la suma de las frecuencias, y le antecede un null.

Al final queda un árbol binario de la siguiente manera.

Lo siguiente es asignar ceros y unos a las ramas del árbol, las de la izquierda serán ceros, mientras que las de la derecha serán unos.

Mediante esta asignación de números podemos determinar el camino para llegar al caracter deseado, por ejemplo si queremos llegar a n, el recorrido es 00, mientras que para e, el recorrido es 01. Podemos hacer lo mismo para obtener el código de las demás letras de nuestra palabra, a continuación muestro una tabla con los caracteres, su frecuencia y su código de Huffman correspondiente a esta palabra.

---

Yo implementé el algoritmo de Huffman en python, el siguiente es el código fuente:

'''
    Algoritmo de Huffman
    Compresion de datos
'''
def huff():
 text = raw_input("Put your text: ")
 let = dict()
 large1 = len(text)
 for i in range (large1):
     if text[i] in let:
  let[text[i]] += 1
     else:
  let[text[i]] = 1
 k = let.items()

 large2 = len(k)
 for i in range(large2):
     men = k[i][1] #menor
     for j in range(len(k)):
  if k[j][1] > men:
      men,let2 = k[j][1],k[j][0]
      a,b = k[i][1],k[i][0]
      k[j] = (b,a)
      k[i] = (let2,men)         
 num = [] 
 lett = []             
 comb = [] 

 for i in range(len(k)):
     num.append(k[i][1])
     lett.append(k[i][0])
     comb.append((k[i][0],0,0))
 tam = 0 

 #Finish - tree
 size = len(num)

 while (len(num) > 1):
     m = num[0] # 
     z = 0
     a = lett[0]
     for i in range(len(num)):
  if num[i] < m:
      m = num[i]
      a = lett[i]
      z = i        
     lett.pop(z)        
     num.pop(z)
     mini = num[0] 
     j = 0
     b = lett[0]
     for i in range(len(num)):
  if num[i] < mini:
      mini = num[i]
      b = lett[i]
      j = i
     add = m + mini
     lett[j] = tam
     num[j] = add
     comb.append((tam,0,0))
     if m >= mini:
  counter = 1 
  con = 0
     else:
  counter = 0
  con = 1
     for q in range(len(comb)):
  if comb[q][0] == a:
      comb[q] = (a,counter,tam)
  if comb[q][0] == b:    
      comb[q] = (b,con,tam)
     tam += 1

 #Finish1

 num = [] #
 leng = len(comb)
 last = comb[leng-1][0]
 k = 0
 for i in range(size):
     num.append([])
     a,b,c = comb[i]
     num[i].append(str(b))
     q = i
     cont = 0
     while(q <= leng-2): 
  if(comb[q][0] == c):
      c = comb[q][2]
      num[i].append(str(comb[q][1]))
      cont = c
      if cont == last:
          break
  q += 1
     num[i] =num[i][::-1]
 #Finish2-
 code = [] 
 for i in range(len(text)):
     last = 0
     while (last <= size):
  if comb[last][0] == text[i]:
      break
  last += 1
     cads = "".join(num[last])
     code.append((cads))

 #print "Code: ",code
 new = []

 for i in range(len(code)):
     new.append(str(code[i]))
 new = "".join(new)
 cal = []
 j, k, i, l = 0,0,0,0 #another
 temp = []
 while(i < len(new)):
     l = 1
     j = 0
     while(j < len(num) ):
  k = 0
  if new[i] == num[j][k]:
      k += 1
      if len(num[j]) == k:
          l = k
          temp.append(comb[j][0])
      while (k < len(num[j])):
          if new[i+k] == num[j][k]:
              k += 1
              if k == len(num[j]):
                  temp.append(comb[j][0])
                  l = k
          else:
              k = len(num[j])        
  j += 1
     i += l
 lenew = len(new)
 trans = "".join(temp)
 print "Binary: ",new
 #print "Code: ",code
 print "Translate: ",trans

 print "\nLength of text: ", large1
 print "In bytes: ", large1

 bytecomp = float(lenew/8.0)
 print "Bytes affter compression: ", bytecomp 
 print "Relation: ", float(large1/bytecomp)

if __name__ == '__main__':
 huff()

Y este es el resultado de la ejecución del script.

Para "hello huffman":

Para "arsenal fc"

Para "Facultad de Ingenieria Mecanica y Electrica"

---

Para medir la efectividad de compresión de datos por el algoritmo de Huffman partimos de la idea de la equivalencia de un caracter y un byte, es decir el largo de caracteres de la cadena introducida será el valor de bytes de la misma, seguido de eso podemos obtener el valor de bytes después de la compresión, dividiendo la cadena binaria obtenida entre 8.
Por último imprimí también la relación entre la entrada y salida, quedando los resultados de la siguiente manera:

El resultado es una compresión de cerca del doble.
Veamos ahora con cadenas más largas.

Podemos observar nuevamente que la relación es cercana al doble, tomando en cuenta que existe un mayor número de caracteres.
Es todo por esta entrada. Cualquier duda o aclaración pueden dejarla en comentarios. 

Bibliografía:


http://www.alegsa.com.ar/Diccionario/C/1048.php
https://www.youtube.com/watch?v=8Gf8wutvS1w


Liga hacia mi git: https://github.com/eddypre/M-todosCodificaci-n

Saludos!