Codificación
Para realizar el proceso de codificación, utilizamos la codificación de Huffman\cite{python}, la cual a partir de la generación de una tabla de códigos (diccionario) de largo variable permite codificar un símbolo en una secuencia binaria. Esto nos permite representar toda la información en una tira binaria. En el proceso de codificación también ocurre la compresión de datos.
Generación del diccionario y árbol de Huffman
Es necesario crear el árbol de Huffman para poder generar nuestro diccionario. El árbol de Huffman es un árbol binario en las que cada una de sus hojas es uno de los símbolos contenidos dentro de la matriz de datos cuantizados.
El algoritmo dice lo siguiente:
- Se ordena cada símbolo según su probabilidad
- Se escogen los dos símbolos con menor probabilidad y se agrupan, formando un nuevo nodo. Ese nodo representa la suma de las probabilidades de los dos elementos que fueron agrupados. El nuevo nodo se convertirá en el padre de los nodos escogidos, donde el lado izquierdo (representado por un 0) conectará al hijo con mayor probabilidad y el lado derecho (1) al de menor probabilidad.
- Se repite el paso 2 hasta que el árbol se reduzca a dos conjuntos, los que serán conectados por un nuevo nodo padre de la misma forma que el paso 2.
- Para obtener el código binario de cada hoja basta con realizar el recorrido desde la raíz del árbol concatenando los 0's y 1's en el orden que aparecen.