Codificación de Huffman

idea:

1. se calcula las frecuencias relativas de los símbolos de la fuente
2. se genera un árbol para obtener el código usando una cola de prioridad

sea s un arreglo de símbolos $(i,p)$ con $i$ como índice y $p$ como probabilidad, pq una cola de prioridad de los símbolos basada en las probabilidades, graph un árbol con nodos atribuidos con $i$

  for(i=0;i<number_of_symbols;i++) {
    pq.insert(s[i]);
    graph.node_insert(s[i]);
  }
  n=i;
  while(pq.size()>1)
    s_i=pq.delete_min();
    s_j=pq.delete_min();
    s_k=(n,s_i.p+s_j.p);
    pq.insert(s_k);
    graph.node_insert(n);
    n++;
  }

al final, las hojas del árbol contienen los símbolos originales, a cada uno se asiña el código binario obtenido bajando desde la raíz hacia la hoja y tomando el cero para la rama izquierda y el uno para la rama derecha (o al revés)

el codificador de Huffman tiene las siguientes propriedades

• es optimal si las probabilidades de los símbolos son potencias de 2
• es mejor que el codificador de Shannon-Fano, si las frecuencias relativas no son muy dispersas
• no codifica bien si pocos símbolos aparecen muy frecuente, en este caso, mejor anteponer una codificación de repeticiones