Puedo resolver un problema similar con 4 símbolos. Pero no puedo resolverlo cuando el número de símbolos es de más de 4. Sin embargo, aquí es la probabilidad de los símbolos:
Tengo que desarrollar una óptima código con el método de Huffman.
El árbol que tengo se parece a esto:
Aquí es cómo puedo reducir los símbolos:
Solo sigue el siguiente algoritmo: combinar el menos frecuente de pareja, y seguir haciéndolo. Aquí las menos frecuentes son las $X_1$$X_{11}$; que se combinan para hacer un nuevo nodo $\{X_1,X_{11}\}$ peso $0,01+0,02=0,03$. Ahora la lista de nodos que se parece a esto, después de reordenar por peso:
$$\begin{array}{rcc} X_i:&X_8&\{X_1,X_{11}\}&X_7&X_5&X_3&X_{10}&X_{12}&X_2&X_6&X_9&X_4\\ p_i:&0,03&0,03&0,04&0,05&0,06&0,07&0,08&0,1&0,11&0,2&0,23 \end{array}$$
The smallest two are $X_8$ and $\{X_1,X_{11}\}$, so we combine them to make a new node $\{X_1,X_8,X_{11}\}$ of weight $0,03+0,03=0,06$, and we now have the following list:
$$\begin{array}{rcc} X_i:&X_7&X_5&X_3&\{X_1,X_8,X_{11}\}&X_{10}&X_{12}&X_2&X_6&X_9&X_4\\ p_i:&0,04&0,05&0,06&0,06&0,07&0,08&0,1&0,11&0,2&0,23 \end{array}$$
Now combine $X_7$ and $X_5$ to make a node $\{X_5,X_7\}$ of weight $0,09$, reducing the list to this:
$$\begin{array}{rcc} X_i:&X_3&\{X_1,X_8,X_{11}\}&X_{10}&X_{12}&\{X_5,X_7\}&X_2&X_6&X_9&X_4\\ p_i:&0,06&0,06&0,07&0,08&0,09&0,1&0,11&0,2&0,23 \end{array}$$
The next step combines $X_3$ with $\{X_1,X_8,X_{11}\}$, and the one after that combines $X_{10}$ and $X_{12}$ to produce the list
$$\begin{array}{rcc} X_i:&\{X_5,X_7\}&X_2&X_6&\{X_1,X_3,X_8,X_{11}\}&\{X_{10},X_{12}\}&X_9&X_4\\ p_i:&0,09&0,1&0,11&0,12&0,15&0,2&0,23 \end{array}$$
En esta etapa de su gráfico se parece a esto:
* * * * * * *
/ \ X2 X6 / \ / \ X9 X4
/ \ / \ / \
X5 X7 * * X10 X12
X3 / \
/ \
* *
/ \ X8
/ \
* *
X1 X11
Se puede terminar de hacerlo ahora? Sólo seguir haciendo lo mismo hasta que se convierte en un árbol. Hay siete piezas separadas ahora, así que va a tomar más de seis pasos. Una vez que tenga el árbol, podemos preocuparse acerca de cómo obtener el actual código Huffman de ella.
Agregado: Hay dos posibles árboles; he aquí un boceto de uno de ellos.
Este algoritmo es muy simple, como la de otros puestos de punto. Haciendo su ejemplo sobre el papel lleva casi tan larga como la escritura de un programa, así que aquí está el programa.
En primer lugar, algunos ejemplos de pistas incluyendo su ejemplo.
$ ./huffman.pl 0.1 0.1 0.1 0.4 0.3 X01 0.100000 1110 X02 0.100000 1111 X03 0.100000 110 X04 0.400000 0 X05 0.300000 10 $ ./huffman.pl 0.01 0.1 0.06 0.23 0.05 0.11 0.04 0.03 0.2 0.07 0.02 0.08 X01 0.010000 011110 X02 0.100000 1111 X03 0.060000 0110 X04 0.230000 10 X05 0.050000 11101 X06 0.110000 010 X07 0.040000 11100 X08 0.030000 01110 X09 0.200000 00 X10 0.070000 1100 X11 0.020000 011111 X12 0.080000 1101 $ ./huffman.pl 15 7 6 6 5 escala por un factor de 39 en ./huffman.pl la línea 35. X01 0.384615 0 X02 0.179487 111 X03 0.153846 101 X04 0.153846 110 X05 0.128205 100
El algoritmo de la siguiente manera, implementado en Perl. No hay mucho que decir al respecto: comenzar con un bosque de singleton árboles y de forma iterativa mantener la fusión de los dos con la suma más pequeña de valor, el registro de las sumas acumulativas. Recorrer el árbol resultante con la ruta de acceso a una hoja de dar el código Huffman de la hoja.
#! /usr/bin/perl -w
#
sub buildcode {
my ($cref, $pref, $t) = @_;
si(existe($t->{etiqueta})){
$cref->{$t->{label}} = $pref;
de retorno;
}
buildcode($cref, $pref . '0', $t->{izquierda});
buildcode($cref, $pref . '1', $t->{derecho});
}
PRINCIPAL: {
mi @freq = @ARGV;
mueren "se necesitan al menos un símbolo "
si escalares(@freq) == 0;
mi $n = escalar(@freq);
mi $total = 0;
para(mi $pos=0; $pos<$n; $pos++){
mi $val = $frec[$pos];
morir "no es un número decimal de: $val"
si $val !~ /^\d+(\.\d*)?$/;
$total += $frec[$pos];
}
if(abs(1-$total) > 1e-12){
advertir "a escala por un factor de $total";
para(mi $pos=0; $pos<$n; $pos++){
$frec[$pos] /= $total;
}
}
mi @de la piscina;
para(mi $pos=0; $pos<$n; $pos++){
push @a la piscina,
{ suma => $frec[$pos], etiqueta => "X" . ($pos+1), };
}
@pool = sort { $a->{suma} <=> $b->{suma} } @de la piscina;
mientras(escalares(@pool) >= 2){
my ($ma $mb);
$ma = shift @de la piscina; $mb = shift @de la piscina;
mi $node = {
suma => $ma->{suma} + $mb->{suma},
izquierda => $ma, derecho => $mb
};
mi $pos;
for($pos = 0; $pos<escalar(@pool); $pos++){
última si $nodo->{suma} < $piscina[$pos]->{suma};
}
empalme @piscina, $pos, 0, $nodo;
}
mi $code = {};
buildcode $código, ", $piscina[0];
para(mi $pos=0; $pos<$n; $pos++){
printf "X%02d %05f %s\n", $pos+1,
$frec[$pos], $código->{'X' . ($pos+1)};
}
1;
}
En respuesta a la solicitud de un dibujo del árbol en lugar de una lista que yo voy a enviar algo de código en Perl que genera una ASCII árbol. Espero que pueda ser de utilidad para el estudio de los códigos de Huffman y tal vez hacer que sea más fácil entender lo que está pasando.
Aquí están algunos ejemplos:
$ ./huffman-tree.pl 0.1 0.1 0.1 0.4 0.3 +-0--X004 0.400000 0 | +-1--+-0--X005 0.300000 10 | +-1--+-0--X003 0.100000 110 | +-1--+-0--X001 0.100000 1110 | +-1--X002 0.100000 1111 $ ./huffman-tree.pl 0.01 0.1 0.06 0.23 0.05 0.11 0.04 0.03 0.2 0.07 0.02 0.08 +-0--+-0--X009 0.200000 00 | | | +-1--+-0--X006 0.110000 010 | | | +-1--+-0--X003 0.060000 0110 | | | +-1--+-0--X008 0.030000 01110 | | | +-1--+-0--X001 0.010000 011110 | | | +-1--X011 0.020000 011111 | +-1--+-0--X004 0.230000 10 | +-1--+-0--+-0--X010 0.070000 1100 | | | +-1--X012 0.080000 1101 | +-1--+-0--+-0--X007 0.040000 11100 | | | +-1--X005 0.050000 11101 | +-1--X002 0.100000 1111 $ ./huffman-tree.pl 15 7 6 6 5 escala por un factor de 39 en ./huffman-tree.pl línea 87. +-0--X001 0.384615 0 | +-1--+-0--+-0--X005 0.128205 100 | | | +-1--X003 0.153846 101 | +-1--+-0--X004 0.153846 110 | +-1--X002 0.179487 111
Este es el código.
#! /usr/bin/perl -w
#
sub max {
my ($a, $b) = @_;
return ($a<$b ? $b : $a);
}
sub calc_dims {
my ($path, $t) = @_;
$t->{path} = $path;
si(existe($t->{etiqueta})){
$t->{sumstr} = sprintf "%05f", $t->{suma};
$t->{ancho} = 2 + longitud($t->{etiqueta}) + longitud($path)
+ longitud($t->{sumstr});
$t->{altura} = 1;
de retorno;
}
calc_dims($path . '0', $t->{izquierda});
calc_dims($path . '1', $t->{derecho});
$t->{ancho} =
5 + max($t->{izquierda}{ancho}, $t->{derecho}{ancho});
$t->{altura} =
1 + $t->{izquierda}{altura} + $t->{derecho}{altura};
}
sub draw_tree {
my ($b, $x, $y, $t) = @_;
si(existe($t->{etiqueta})){
mi (@cartas) =
split(//, $t->{etiqueta} . '' . $t->{sumstr} .
'' . $t->{path});
para(mi $ltr=0; $ltr<escalar(@cartas); $ltr++){
$b->[$y][$x+$ltr] = $letras[$ltr];
}
de retorno;
}
$b->[$y][$x] = '+';
$b->[$y][$x+1] = '-';
$b->[$y][$x+2] = '0';
$b->[$y][$x+3] = '-';
$b->[$y][$x+4] = '-';
draw_tree($b, $x+5, $y, $t->{izquierda});
mi $pos;
for($pos=1; $pos<=$t->{izquierda}{altura}; $pos++){
$b->[$s+$pos][$x] = '|';
}
$y += $pos;
$b->[$y][$x] = '+';
$b->[$y][$x+1] = '-';
$b->[$y][$x+2] = '1';
$b->[$y][$x+3] = '-';
$b->[$y][$x+4] = '-';
draw_tree($b, $x+5, $y, $t->{derecho});
}
PRINCIPAL: {
mi @freq = @ARGV;
mueren "se necesitan al menos un símbolo "
si escalares(@freq) == 0;
mi $n = escalar(@freq);
mi $total = 0;
para(mi $pos=0; $pos<$n; $pos++){
mi $val = $frec[$pos];
morir "no es un número decimal de: $val"
si $val !~ /^\d+(\.\d*)?$/;
$total += $frec[$pos];
}
if(abs(1-$total) > 1e-12){
advertir "a escala por un factor de $total";
para(mi $pos=0; $pos<$n; $pos++){
$frec[$pos] /= $total;
}
}
mi @de la piscina;
para(mi $pos=0; $pos<$n; $pos++){
mi $label = sprintf "X%03d", ($pos+1);
push @a la piscina,
{ suma => $frec[$pos], etiqueta => $etiqueta };
}
@pool = sort { $a->{suma} <=> $b->{suma} } @de la piscina;
mientras(escalares(@pool) >= 2){
my ($ma $mb);
$ma = shift @de la piscina; $mb = shift @de la piscina;
mi $node = {
suma => $ma->{suma} + $mb->{suma},
izquierda => $ma, derecho => $mb
};
mi $pos;
for($pos = 0; $pos<escalar(@pool); $pos++){
última si $nodo->{suma} < $piscina[$pos]->{suma};
}
empalme @piscina, $pos, 0, $nodo;
}
calc_dims(", $piscina[0]);
mi $board = [];
para(mi $fila=0; $fila<$piscina[0]->{altura}; $fila++){
push @$bordo, [('a ') x ($piscina[0]->{ancho})];
}
draw_tree($bordo, 0, 0, $piscina[0]);
para(mi $fila=0; $fila<$piscina[0]->{altura}; $fila++){
para(mi $col=0; $col<$piscina[0]->{ancho}; $col++){
print $tabla->[$fila][$col];
}
print "\n";
}
1;
}
En respuesta al comentario del usuario con respecto a la disposición del árbol binario creo que en un caso puede ser hecho por la disposición a ser de vuelta, con un bit cero se va a la izquierda y un bit a la derecha. He implementado este diseño del árbol de abajo. Es importante recordar que Huffman los árboles producidos por el algoritmo básico no son únicas. Por lo tanto, también he modificado el programa para imprimir todos los Huffman árboles. Advertencia: esto va a producir una gran cantidad de la producción. Trate de pequeños conjuntos de frecuencias en primer lugar. Podríamos imponer restricciones adicionales para reducir el número de soluciones, por ejemplo, que los valores más pequeños siempre van en la izquierda. El único resto de la ambigüedad en ese caso sería cuando la izquierda es igual a la derecha.
#! /usr/bin/perl -w
#
sub max {
my ($a, $b) = @_;
return ($a<$b ? $b : $a);
}
sub numeq {
my ($a, $b) = @_;
retorno (abs($a-$b) < 1e-10 ? 1 : 0);
}
sub alltrees {
my ($poolref, $solref) = @_;
si(escalares(@$poolref) == 1){
push @$solref, $poolref->[0];
de retorno;
}
mi $prefijo = [shift(@$poolref)];
mi $par = undef;
mi $val = $prefix->[0]->{suma};
mientras(escalares(@$poolref)>0 && numeq($poolref->[0]->{suma}, $val)){
push @$prefijo, shift(@$poolref);
}
si(escalares(@$prefix)==1){
$par = 1;
$val = $poolref->[0]->{suma};
mientras(escalares(@$poolref)>0 && numeq($poolref->[0]->{suma}, $val)){
push @$prefijo, shift(@$poolref);
}
}
mi $preflen = escalar(@$prefijo);
mi $total = $prefix->[0]->{suma} + $prefix->[1]->{suma};
mi $pos;
for($pos = 0; $pos<escalar(@$poolref); $pos++){
última si $total < $poolref->[$pos]->{suma};
}
para(mi $i=0; $i<(define($par) ? 1 : $preflen); $i++){
para(mi $j=$i+1; $j<$preflen; $j++){
my ($ma $mb) = ($prefix->[$i], $prefix->[$j]);
my ($nodo, @newpool);
$node = {
suma => $total,
izquierda => $ma, derecho => $mb
};
@newpool =
(@$poolref[0..($pos-1)],
$nodo,
@$poolref[$pos..$#$poolref]);
para(mi $k=0; $k<$preflen; $k++){
unshift(@newpool, $prefix->[$k])
si $k != $i && $k != $j;
}
alltrees(\@newpool, $solref);
}
}
}
sub calc_dims {
my ($path, $t) = @_;
$t->{path} = $path;
si(existe($t->{etiqueta})){
$t->{sumstr} = sprintf "%05f", $t->{suma};
$t->{ancho} = 2 + longitud($t->{etiqueta}) + longitud($path)
+ longitud($t->{sumstr});
$t->{altura} = 1;
de retorno;
}
calc_dims($path . '0', $t->{izquierda});
calc_dims($path . '1', $t->{derecho});
$t->{ancho} =
5 + max($t->{izquierda}{ancho}, $t->{derecho}{ancho});
$t->{altura} =
1 + $t->{izquierda}{altura} + $t->{derecho}{altura};
}
sub draw_tree {
my ($b, $x, $y, $t) = @_;
si(existe($t->{etiqueta})){
mi (@cartas) =
split(//, $t->{etiqueta} . '' . $t->{sumstr} .
'' . $t->{path});
para(mi $ltr=0; $ltr<escalar(@cartas); $ltr++){
$b->[$y][$x+$ltr] = $letras[$ltr];
}
de retorno;
}
$b->[$y][$x] = '+';
$b->[$y][$x+1] = '-';
$b->[$y][$x+2] = '1';
$b->[$y][$x+3] = '-';
$b->[$y][$x+4] = '-';
draw_tree($b, $x+5, $y, $t->{derecho});
mi $pos;
for($pos=1; $pos<=$t->{derecho}{altura}; $pos++){
$b->[$s+$pos][$x] = '|';
}
$y += $pos;
$b->[$y][$x] = '+';
$b->[$y][$x+1] = '-';
$b->[$y][$x+2] = '0';
$b->[$y][$x+3] = '-';
$b->[$y][$x+4] = '-';
draw_tree($b, $x+5, $y, $t->{izquierda});
}
PRINCIPAL: {
mi @freq = @ARGV;
mueren "se necesitan al menos un símbolo "
si escalares(@freq) == 0;
mi $n = escalar(@freq);
mi $total = 0;
para(mi $pos=0; $pos<$n; $pos++){
mi $val = $frec[$pos];
morir "no es un número decimal de: $val"
si $val !~ /^\d+(\.\d*)?$/;
$total += $frec[$pos];
}
if(abs(1-$total) > 1e-12){
advertir "a escala por un factor de $total";
para(mi $pos=0; $pos<$n; $pos++){
$frec[$pos] /= $total;
}
}
mi @de la piscina;
para(mi $pos=0; $pos<$n; $pos++){
mi $label = sprintf "X%03d", ($pos+1);
push @a la piscina,
{ suma => $frec[$pos], etiqueta => $etiqueta };
}
mi @allsols;
@pool = sort { $a->{suma} <=> $b->{suma} } @de la piscina;
alltrees(\@piscina, \@allsols);
foreach my $sol (@allsols){
calc_dims(", $sol);
mi $board = [];
para(mi $fila=0; $fila<$sol->{altura}; $fila++){
push @$bordo, [('a ') x ($sol->{ancho})];
}
draw_tree($bordo, 0, 0, $sol);
para(mi $fila=0; $fila<$sol->{altura}; $fila++){
para(mi $col=0; $col<$sol->{ancho}; $col++){
print $tabla->[$fila][$col];
}
print "\n";
}
print "\n";
}
1;
}
Esto produce la siguiente salida.
$ ./huffman-tree-order.pl 0.01 0.1 0.06 0.23 0.05 0.11 0.04 0.03 0.2 0.07 0.02 0.08 +-1--+-1--+-1--+-1--X002 0.100000 1111 | | | | | | | +-0--+-1--X005 0.050000 11101 | | | | | | | +-0--X007 0.040000 11100 | | | | | +-0--+-1--X012 0.080000 1101 | | | | | +-0--X010 0.070000 1100 | | | +-0--X004 0.230000 10 | +-0--+-1--+-1--+-1--+-1--+-1--X011 0.020000 011111 | | | | | | | | | +-0--X001 0.010000 011110 | | | | | | | +-0--X008 0.030000 01110 | | | | | +-0--X003 0.060000 0110 | | | +-0--X006 0.110000 010 | +-0--X009 0.200000 00 +-1--+-1--+-1--+-1--X002 0.100000 1111 | | | | | | | +-0--+-1--X005 0.050000 11101 | | | | | | | +-0--X007 0.040000 11100 | | | | | +-0--+-1--X012 0.080000 1101 | | | | | +-0--X010 0.070000 1100 | | | +-0--+-1--+-1--+-1--+-1--X011 0.020000 101111 | | | | | | | | | +-0--X001 0.010000 101110 | | | | | | | +-0--X008 0.030000 10110 | | | | | +-0--X003 0.060000 1010 | | | +-0--X006 0.110000 100 | +-0--+-1--X004 0.230000 01 | +-0--X009 0.200000 00 $ ./huffman-tree-order.pl 0.1 0.1 0.1 0.4 0.3 +-1--+-1--+-1--+-1--X002 0.100000 1111 | | | | | | | +-0--X001 0.100000 1110 | | | | | +-0--X003 0.100000 110 | | | +-0--X005 0.300000 10 | +-0--X004 0.400000 0 +-1--+-1--+-1--+-1--X003 0.100000 1111 | | | | | | | +-0--X001 0.100000 1110 | | | | | +-0--X002 0.100000 110 | | | +-0--X005 0.300000 10 | +-0--X004 0.400000 0 +-1--+-1--+-1--+-1--X003 0.100000 1111 | | | | | | | +-0--X002 0.100000 1110 | | | | | +-0--X001 0.100000 110 | | | +-0--X005 0.300000 10 | +-0--X004 0.400000 0 $ ./huffman-tree-order.pl 15 7 6 6 5 escala por un factor de 39 en ./huffman-tree-order.pl línea 153. +-1--+-1--+-1--X002 0.179487 111 | | | | | +-0--X004 0.153846 110 | | | +-0--+-1--X003 0.153846 101 | | | +-0--X005 0.128205 100 | +-0--X001 0.384615 0 +-1--+-1--+-1--X002 0.179487 111 | | | | | +-0--X003 0.153846 110 | | | +-0--+-1--X004 0.153846 101 | | | +-0--X005 0.128205 100 | +-0--X001 0.384615 0
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
