Algoritmo de compresion HUFFMAN php

::link1:: Huffman Wikipedia(En)
::link2:: Informacion detallada del algoritmo


La idea que subyace detras del algoritmo es sencilla, primero se crea una tabla con las frecuencias para cada simbolo, se ordena segun su probabilidad, y luego se crea un arbol binario uniendo los nodos desde el primer lugar de a dos, sumergiendo asi los nodos con menos probabilidad de salir en el fondo del arbol, y dejando los nodos con mayor probabilidad en las ramas mas cercanas al nodo central.
Esta compresión sólo será óptima si las probabilidades de todos los símbolos de entrada son potencias enteras de 1/2. Y el peor de todos los casos se presentará cuando alguno de los símbolos posean una probabilidad cercana al 100%.

• Texto a comprimir = "pinocho se comio un bizcocho"

• Grafico de barras de Frecuencias

• Tabla de texto de frecuencias

• Reordenar la tabla en sentido ascendente
  

z(0.0357)u(0.0357)s(0.0357)p(0.0357)m(0.0357)e(0.0357)b(0.0357)
n(0.0714)h(0.0714)
i(0.1071)
c(0.1429)(0.1429)
o(0.2143)

• Ahora iremos uniendo cada dos elementos (empezando por los que tengan probabilidad mas baja de salir) y crearemos un nodo hijo en el lugar que acupaban estos; asi hasta que quede un lugar, este sera el nodo padre. Observamos que los nodos con menor probabilidad quedaran al final del arbol y los de mayor en las ramas cercanas a la raiz, esto implica que cuanto mas probabilidad de salir tenga un nodo, menor numero de bits le asignara el codigo, y cuanto menos probabilidad, mayor numero de bits; aqui reside la potencia de este algoritmo.

• Para obtener la tabla codificadora de cada elemento, realizaremos una busqueda en preorden por los nodos del arbol, asignando un "1" si bajamos por los hijos izquierdos o un "0" si bajamos por los hijos derechos.
  

Implementacion en PHP:

Descargar Codigo Fuente / Download Source Code

Una posible ejecucion del codigo seria:

Descargar Codigo Fuente / Download Source Code