Codificacion Huffman en ruby

Estándar

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.

Que buen semestre

Estándar

Bueno no he puesto nada en este blog pues creo que durante todo el semestre pero tuve muchas cosas que hacer, mucha tarea; sin embargo este fue el mejor semestre que he tenido en mucho tiempo creo que durante toda mi estancia en el politecnico habia obtenido 10 de promedio pero esta vez lo consegui jajaja. Bueno como recuerdo para la posteridad.

Bueno espero poder agregar mas cosas a este blog proximamente.

reseña de profesores UPIITA

Estándar

ahora que ya he concluido el sexto semestre me parece justo hacer una breve reseña acerca de los profesores de los que he recibido clase. Las opiniones que acontinuacion se presenta se basan en mi experiencia personal y no refleja la opinion de la comuidad de upiita.

VAZQUEZ CIANCA CESAR

Excelente profesor con amplios conocimientos de su area, es buena onda y se puede obtener una buena calificacion relativamente facil simplemente con cumplir las tareas y estudiar para el examen. Tal vez el unico aspecto desfavorables sea que si ya se tienen conocimientos de la materia puede ser aburrido ya que explica con mucho detenimiento.

FLORES URBINA JULIO CESAR

Muy buen maestro. Conoce bien las materias que imparte y las clases son muy amenas y el tiempo se va muy rapido ya que no solo se centra en la materia, tambien hace bromas o habla de cosas de fisica muy fumadas pero que captan la atencion de los alumnos.

HERNANDEZ PEREZ ALBERTO

No muy buen profesor. Sus tecnicas de enseñanaza no son las mejores y es muy estricto al calificar los examenes (por un ; puede esta mal todo un problema de examen) y no calfica el empeño o calidad que le pones a los trabajos solo que cumplan con lo que pidio.

GARAY JIMENEZ LAURA IVOONE

Excelente profesora, muy didactica y clases mas practicas que teoricas. Algunos puntod desfavorables son que algunas veces se equivoca en el algebra de los problemas y que deja mucha tarea. Pero solo representan fallas menores.

ZAMORA GOMEZ ERIK

Buen maestro pero deja muuucha tarea y practicas lo que hace dificil obtener una buena calificacion si no las entregas un poco ambisioso en terminos de sus objetivos en clase.

GOMEZ CORONEL SANDRA LUZ

Buena maestra, buena onda en general pero aveces sin razon aparente cambia de animo, las clases son fluidas, pero con muchas practicas y proyectos que algunas veces tardan mucho en funcionar.

EL FILALI BRAHIM

Buen profesor, conoce bien su area sin embargo algunas veces no es facil entender lo que explica, muchas practicas,  los examenes generalmente los escribe en el pizarron en el momento y son bastante complicados y laboriosos; un poco irrespetuoso hacia los alumnso pero eso es cuestion de opinion.

CALZADA TRUJILLO RAFAEL

Muy buen maestro, sabe explicar  los temas, bastante comprensivo en terminos de calificaciones, muchas practicas la mayoria largas.

TORRES CRUZ NOE

Excelente profesor, conoce muy bien las materias que imparte por lo que sabe que temas son mas complicados de entender y se enfoca en ellos durante la clase, generalmente deja listas de problemas que son la base para lo examenes, es buena onda y de actitud despreocupada.

HERNANDEZ ZAVALA ANTONIO

Muy buen maestro, sabe mucho de arquitectura de computadoras, sus clases son sencillas pero con los temas necesarios, las practicas en general son sencillas si pones atencion en clase, es relativamente facil obtener una buena calificacion.

MUÑOZ RODRIGUEZ CESAREO JAVIER

Muy buen maestro, domina las materias que imparte, las practicas se basan en lo visto en clase, los examenes pueden ser un poco complicados.

RICO JIMENEZ BLANCA ALICIA

Excelente maestra, muy didactica, sabe explicar los temas complejos de manera simple, toma en cuenta la calidad de los trabajos, examenes de lo que se ve en clase tanto toeria como practica.

MADRIGAL BRAVO JUAN MANUEL

Buen maestro, domina sus temas, sin embargo deja tareas y trabajos que requiren investigacion del alumno, algunos proyectos pueden ser muy complicados si se dejan para ultimo momento, los examenes son algo complicados.

ROJAS BELTRAN JORGE

Muy buen maestro, sabe mucho de los temas que enseña en especial teoria de la informacion, aunque puede ser complicado si no se pone atencion en clase; es exigente en cuanto a practicas y examenes  pero nada imposible. La clase es muy amena y se pasa muy rapido.

DE LA CRUZ SOSA CARLOS

Excelente profesor domina varios temas en cuanto a programacion, algunos de los temas teoricos pueden ser tediosas. Es algo exigente en proyectos pero valora el trabajo y empeño que se ponga en ellos.

CARRILLO TENORIO ARIADNA BERENICE

Una maestra muy amigable y muy comprensiva con sus alumnos. Le gusta dar su clase con dinamicas que hagan la clase mas amena. No es exigente en cuanto a calificaciones.

MARTINEZ LIMON JOSE ANTONIO

Es uno de los mejores profesores de toda la escuela, en mi muy humilde opinion, domina muchos temas que son bastante complicados como antenas y teoria electromagnetica. Puede que sus metodos puedan ser un poco dificiles para algunos, pero personalmente prefiero que un maestro que diga callate estas mal a que me diga pues estas medio bien y nunca me saque de mi duda. Es un maestro que le gusta combinar la parte teorica y la practica. Es de los pocos maestros que pone calificaciones de acuerdo al desempeño academico en general sin importar las calificaciones de examenes o cuanto participes en clase.

modelos 3ds

Estándar

Bueno en esta ocacion compartire con ustedes imagenes de algunos modelos que hace ya mucho tiempo hice en 3d studio; de las cuales estoy muy orgulloso sin hahaha. La idea original era hacer un juego 3d con directx y vb sin embargo nunca se logro y solo quedaron estas imagenes como recuerdos.

lanza2

tridente

ojo

nanchu

hacha

oz2

arco

araña2

espada

escudo

tortuga

EL ASESINO DE SANTA CLAUS

Estándar

Por Arthur Alan Gore

El pequeño Ismael estaba seguro que Santa Claus existía, porque el mismo lo había degollado la noche anterior. Al acercarse la hora del recreo, el niño se inquieto, pues su mochila apestaba. Entre los olores de tortas, quesadillas y fruta picada que el resto de los alumnos guardaban en sus loncheras, bajo los pupitres, se fue colando el tufo a muerto de la mochila de Ismael inundando el salón entero. El muchacho apretó el bulto entre las piernas. Faltaban cinco minutos para que sonara el timbre que anunciaba el recreo. Sería el último día en que Vanesa se burlara de él, porque a sus 11 años seguía creyendo en santa Claus. En medio de el recreo, la llamaría para que se metieran juntos al laboratorio de química y le pediría que cerrara los ojos… pondría la cabeza cercenada en las manos del estúpida niña. Entonces sonó la campana.

La estampida conocía de sobre el camino hacia el patio, en donde la tienda cooperativa podría surtir de golosinas a quienes no habían traído comida de su casa, ya esas horas sus tripas se deshacían en gruñidos. Ismael fue el único que se levanto despacio, ceremoniosamente. Vanesa paso caminando junto a su pupitre con un contoneo que pretendía ser sensual, pero a sus 10 años parecía francamente ridículo, más con las calcetas subidas para cubrir los raspones de sus rodillas. Llevaba un frutsi de uva abierto con los dientes por la base y lo succionaba con delicadeza.

Ismael se le quedo mirando, mientras se echaba la mochila al hombro. Vanesa se retiro el envase de los labios y le mostro una sonrisa amplia, en donde destellaban sus frenos como hojas de hoces. Después le mostro la lengua; estaba morada.

-Faltan dos días para que salgamos de vacaciones… eso significa, dos semanas para Nochebuena y… ¿Qué le vas pedir a Santa pequeñuelo?-le dijo la niña con toda su mala leche. Ismael se rio para sus adentros.

-Nada en especial, oye, ¿Por qué no nos vemos en el laboratorio de química en dos minutos? Vanesa sorbió prolongadamente del bote de frutsi.

-Vaya, con qué quieres estas solito conmigo… ¿y no te da pena que vayan a decir que somos novios, tontín?- mientras hablaba, enredaba sus dedos en una de sus amarillas trenzas.

Ismael pasó enfrente de ella, con la mochila al hombro:

-Te tengo una sorpresa, pero antes necesito pasar al baño. Después salió del salón. Camino al baño con la cabeza de Santa Claus en medio del cuaderno de matemáticas y el de civismo, Ismael pensó en lo mucho que le dolían los dedos. Incluso le había salido llagas. Todo por querer desprender el solo la cabeza del cuerpo de Santa Claus. Obviamente no había podido. El duende tuvo que echarle una mano. Mientras Ismael había propinado había propinado cuchilladas inútiles, al duende le basto con tres buenos golpes con el hacha que traía en la cintura. Afortunadamente la cabeza ya no sangraba, así que Ismael no ensucio el camino del aula hasta el baño. Cerró la puerta, se bajo el cierre y comenzó a orinar.

-¿Quihubo, pinche Isma… ya le dejaste tus dientes al ratón?- un chico le propino un manotazo en la nuca antes de salir corriendo de el baño. Ismael sintió que la rabia lo invadía.

-Es el ultimo día que se burlan de mi- se dijo mientras imaginaba a Vanesa, huyendo de el laboratorio después de haber tocado la cabeza inerte de Santa Claus. Ismael no le hecho agua al mingitorio ni se lavo las manos. Esperó en vano a que el duende acudiera a su cita y como no lo hizo salió antes de que el recreo concluyera.

-Ya vendrá después- dijo al salir del baño.

Cuando ya no había nadie, una cabecita verde salió de uno de los retretes y grito desesperadamente  escupiendo un poco de agua:

-¡Niño… pronto… ven aquí! ¡Nos descubrieron!

Antes de que otro niño penetrara en el baño, algo jalo al duende de los pies y lo volvió a zambullir en el agua.

Ismael encontró a Vanesa admirando los instrumentos de laboratorio. Cuando entro la niña se sobresalto.-Ah pensé que me ibas a dejar plantada. Ismael se acerco, corriendo el cierre de su mochila

-Cierra los ojos, Vane…te traje un regalito. La niña lo obedeció. Detrás de los gruesos lentes de fondo de botella, a sus ojos verdes los cubrieron los parpados como si fueran dos telones de teatro. Paro los labios en espera de un beso.

Ismael tomo la cabeza por el cabello. Ni siquiera le había quitado el gorro rojo. Ya disfrutaba anticipadamente el grito que pegaría la niña. En ese momento la profesora Ángela entro en el laboratorio:

-¡Ismael, que bueno que esas aquí!

Vanesa dio un brinco hacia atrás:

-¡Yo no hice nada!

La maestra tomo al chico del brazo y se lo llevo a jalones. El trataba de cerrar la mochila para que la profesora no alcanzara a ver su contenido.

Mientras esperaba a solas en la dirección, Ismael recordó el día en que el duende se le apareció. Fue poco después de jalar la cadena del retrete en el baño de la escuela. Le dijo que solo así podía salir a este mundo.

-Lo vamos a matar, tenemos un plan- le confió la criatura.

-¿Y por qué yo, porque he de ayudarte?- inquirió Ismael.

– Porque eres el número uno en la lista negra.

Entonces la lista negra existía. Por eso Santa Claus nunca le traía nada. Pero Ismael lo veía, atreves de las ventanas, dejando juguetes en la casa de los niños que se portaban bien y que no creían en su existencia. Como Vanesa, quien lo delato por toda la escuela como un niño ingenuo después de que él se negó a darle un beso. Pero siempre estrenaba muñecas en 25 de diciembre.

A Ismael nadie lo mandaba a dormir en Nochebuena. Papa siempre estaba de viaje y mama, encerrada en su cuarto con dolor de cabeza. El duende le había explicado todo.

El no es ningún viejo regordete y bonachón. Es un oso gruñón y dictatorial que duerme todo el año, mientras nos obliga a fabricar los juguetes. En la Nochebuena se levanta, reparte los obsequios y se para el cuello con la gloria que debe corresponder a los duendes. “Ahora hemos decidido asesinarlo”. Pero debe ser de este lado de el mundo, porque de él otro lado el es intocable. El duende había dicho que junto con un grupo de insurrectos se había puesto de acuerdo para adelantar un par de semanas el reloj que despertaba a Santa Claus antes de navidad. Los duendes insurrectos borrarían el nombre de Ismael de la lista negra y lo pondrían en la de niños buenos. Así, sería el primer niño que Santa visitaría para dejarle sus regalos, pero con dos semanas antes de navidad. Ismael lo espero en su casa, escondido como le aconsejo el duende. Y cuando Santa Claus entro a su casa, el niño se le fue encima con el bastón con que su padre aseguraba el coche. Los duendes insurrectos, que se había ocultado después de salir por el retrete de la casa de Ismael, se llevaron el cuerpo de Santa Claus. Antes, lo degollaron con un hacha, como Ismael lo había solicitado, teniendo cuidado de no manchar la alfombra de sangre. Los duendes le entregaron la cabeza de santa Claus y se retiraron. Ismael les dijo que les entregaría la cabeza al día siguiente, en el baño de la escuela, después de asustar a Vanesa. Los duendes se encargarían de desaparecerla.

Ellos le aseguraron, que de ahora en adelante, llevarían obsequios a los niños malos en navidad, mientras que los buenos se quedarían con las manos vacías. La idea emocionaba al niño. Mama entro en la oficina del director. Tenía la cara hinchada de tanto llorar. Se sentó junto a Ismael; le explico que algo horrible había sucedido y que papa no regresaría a la casa con ellos nunca más.

-Tu padre adelanto su viaje, hijo, para darte una sorpresa de navidad…

Ismael apretó la mochila contra el pecho. Creyó comprenderlo todo de golpe. Vanesa decía la verdad…

-Mama,…yo. Dijo con un nudo en la garganta.

En ese momento papa entro en la oficina, hecho un energúmeno.

-¡Clara, no te le acerques a mi hijo!

-Por favor, Enrique, aquí no…-suplico la madre. El padre fuera de sí jaloneo a su mujer por lo hombros:

-¡Dile! ¡Dile, que al fin ya esta grande! ¡Dile que aprovechabas mis viajes para acostarte con tu amante! ¡Dile que eres una cerda pervertida que le pidió que se disfrazara de Santa Claus para hacer el amor!

-¿Qué?-pregunto confundido Ismael.

El padre volteo a mirarlo con los ojos inyectados.

-Hoy por la mañana encontraron el cuerpo de el muy cabron, sin cabeza. Parece que alguien se me adelanto para hacer justicia-resalto las últimas palabras para herir a su esposa- la policía encontró una foto de tu mama y una carta de amor entre las ropas de el muerto. Llamarón a la casa y tu madre tuvo que ir a declarar que efectivamente, lo estaba esperando la noche anterior. Yo llegue a casa poco después y fue ella quien me lo conto todo. Y en algún lugar del polo norte un grupo de duendes insurrectos era sometido a las más crueles torturas.

Sockets TCP en java

Estándar

Este es un ejemplo muy sencillo de un programa con sockets TCP; para el servidor solo se tiene que dar el numero del puerto que se va a usar y para el cliente la direccion ip(localhost si se esta probando en una sola maquina) y el puerto. El programa permitira enviar mensajes desde el servidor a el cliente y terminara la conexion cuando se escriba bye.

java_sockets_tcp