Codificacion Huffman en ruby

En estas vacaciones una de mis metas fue aprender ruby y pues hasta el momento solo he leido lo «basico» de ruby; pero la mejor forma de probar los conocimientos es aplicarlos a un problema real asi pues me parecio buena idea implementar el algoritmo del codigo Huffman.

Bueno un poco de background. La algoritmo de huffman plantea el procedimiento que debe realizar el codificador  para representar los simbolos producidos por la fuente de manera que se optimicen los los codigos. Es un sistema de codificacion «optima» basado en las probabilidades de la fuente. Donde la redundancia se reduce por medio de codificar la n-esima extension de la fuente. La idea principal es En estas vacaciones una de mis metas fue aprender ruby y pues hasta el momento solo he leido lo «basico» de ruby; pero la mejor forma de probar los conocimientos es aplicarlos a un problema real asi pues me parecio buena idea implementar el algoritmo del codigo Huffman.

Bueno un poco de background. La algoritmo de huffman plantea el procedimiento que debe realizar el codificador  para representar los simbolos producidos por la fuente de manera que se optimicen los los codigos. Es un sistema de codificacion «optima» basado en las probabilidades de la fuente. Donde la redundancia se reduce por medio de codificar la n-esima extension de la fuente. La idea principal es asignar al simbolo mas probable el codigo mas corto para optimizar la transmision de los datos.

El algoritmo son 4 simples pasos:

1. Ordenar descendentemente los simbolos en base a sus probabilidades.
2. Se suman los dos ultimos valores(caso binario) y se calcula el total en la siguiente fuente reducida en orden tambien descendente.
3. Se detiene el paso 2 hasta llegar a 2 y se asignaran 0 y 1 respectivamente.
4. Se barre de atras hacia delante colocando el valor del codigo segun el origen de sus probabilidades.

Un ejemplo sencillo. Tomamos la palabra «blzb», que no es en realidad una palabra, sus probabilidades para cada simbolo serian b=2/4, l=1/4, z=1/4; el proceso seria como se ilustra en la siguiente figura:

El numero en rojo seria el codigo asociado a cada simbolo. Una vez que se tiene el diccionario de simbolos y codigo la coficacion se realiza substituyendo cada simbolo con su respectivo codigo. Que para este caso quedaria:

010110

Para el proceso de decodificacion se busca las cadenas binarias en el diccionario y se remplazan por su correspondiente simbolo.

Implementando lo antes mencionado en ruby seria algo mas o menos asi. Primero necesitariamos una clase que contenga cada simbolo, su probabilidad y su codigo.

class Caracter

attr_accessor :caracter, :probabilidad, :codigo, :hijos

def initialize(car=»»,prob=0)

self.caracter = car

self.probabilidad = prob

self.codigo=»»

self.hijos=[]

end

def to_s

«caracter:#{self.caracter}=>#{self.probabilidad}»

end

def calcular

self.hijos.each do |hijo|

self.probabilidad+=hijo.probabilidad
self.caracter<<hijo.caracter

end

end

Capturamos la cadena de texto que se codificara, obtenemos las probabilidades de cada simbolo y lo almacenamos en un array de objetos

DICC={}
base = 2
print «cual es la cadena»
cadena = gets
caracteres = cadena.split(//)
unicos = caracteres.uniq
originales=[]

unicos.each do |i|

originales<<Caracter.new(i,caracteres.count(i))

end

ordenado = originales.sort { |a,b| b.probabilidad a.probabilidad }
puts «ordenados»
puts ordenado
Realizamos el proceso de sumar los dos simbolos menos probables y lo remplazarlos en el array.

while(ordenado.size>base)

nuevo = Caracter.new

base.times do

nuevo.hijos<<ordenado.pop

end

nuevo.hijos.reverse!
nuevo.calcular
ordenado<<nuevo
ordenado.sort! { |a,b| b.probabilidad a.probabilidad }

end

Definimos un metodo recursivo que recorra el «arbol» generado anteriormente y que asigne el codigo correspondiente a cada simbolo y lo almacene en un Hash. Y lo llamamos.

def recorrer(inicio,acumulado=»»)

contador=0

inicio.each do |item|

item.codigo<<acumulado

if(item.codigo<0)

recorrer(item.hijos,item.codigo)

else

DICC[item.caracter]=item.codigo

end

contador+=1

end

end

recorrer(ordenado)

Y con eso ya tenemos nuestro diccionario con los simbolos y codigos asociados.
Para codificarlo solo hay que recorrer la cadena caracter por caracter y concatenar sus codigos.

codificado =»»

caracteres.each do |i|

codificado<<DICC[i]

end

Y para decodificarlo se buscan cadenas de bits y se concatenan los codigos.

decodificar = codificado.split(//)
aux = «»
recuperado = «»
dicc_inv = DICC.invert
p dicc_inv
decodificar.each do |car|

aux<<car

if(dicc_inv.has_key?(aux))

recuperado<<dicc_inv[aux]
aux.replace(«»)

end

end

Debo de agregar que apenas estoy aprendiendo ruby por lo que talvez mi implementacion no sea la mas optima. Sin embargo creo que muestra la idea principal.
Y un comentario final, la codificacion huffman se utiliza por ejemplo en los faxes donde las cadenas de espacios en blanco y en negro mas comunes(para esto se tuvo que hacer un estudio de los textos para obtener dichas probabilidades) se codifican con los codigos mas cortos; esa es la razon por la que una hoja con texto se transmite mas rapido que una imagen.

P.D. Perdon por la falta de identacion pero no se como ponerla en wp. Si alguien quiere el codigo fuente huffman.