Huffman coding: Difference between revisions

Content added Content deleted
No edit summary
m ({{out}})
Line 408: Line 408:
end Main;</lang>
end Main;</lang>


{{out}}
Output:
<pre> = 101
<pre> = 101
a = 1001
a = 1001
Line 486: Line 486:
NEXT
NEXT
END</lang>
END</lang>
{{out}}
'''Output:'''
<pre>
<pre>
101
101
Line 565: Line 565:
)
)
& out$("decoded:" str$(decode$(str$!encoded)));</lang>
& out$("decoded:" str$(decode$(str$!encoded)));</lang>
{{out}}
Output:
<pre>(L=
<pre>(L=
(" ".101)
(" ".101)
Line 890: Line 890:


return 0;
return 0;
}</lang>output<lang>' ': 000
}</lang>
{{out}}
<pre>' ': 000
'a': 1000
'a': 1000
'c': 01101
'c': 01101
Line 910: Line 912:
'x': 01001
'x': 01001
encoded: 0111111010011110000000111100000100010100001010100110001111100110100010101000001011101001000011010111000100010111110001010000101101011011110011000011101010000
encoded: 0111111010011110000000111100000100010100001010100110001111100110100010101000001011101001000011010111000100010111110001010000101101011011110011000011101010000
decoded: this is an example for huffman encoding</lang>
decoded: this is an example for huffman encoding</pre>

=={{header|C sharp}}==
=={{header|C sharp}}==
<lang csharp>using System;
<lang csharp>using System;
Line 1,348: Line 1,351:
}</lang>
}</lang>


{{out}}
Sample output:

<pre> 110
<pre> 110
a 1001
a 1001
Line 1,410: Line 1,412:
</lang>
</lang>


{{out}}
Program Output:
<pre>
<pre>
SYMBOL WEIGHT HUFFMAN CODE
SYMBOL WEIGHT HUFFMAN CODE
Line 1,523: Line 1,525:
</lang>
</lang>


{{out}}
output
<pre>

<lang>
> coffee huffman.coffee
> coffee huffman.coffee
---- this is an example for huffman encoding
---- this is an example for huffman encoding
Line 1,560: Line 1,561:
101 : c (4)
101 : c (4)
11 : d (8)
11 : d (8)
⚫
</pre>

⚫
</lang>



=={{header|Common Lisp}}==
=={{header|Common Lisp}}==


This implementation uses a tree built of <code>huffman-node</code>s, and a hash table mapping from elements of the input sequence to <code>huffman-node</code>s. The priority queue is implemented as a sorted list. (For a more efficient implementation of a priority queue, see the [[Heapsort]] task.)
This implementation uses a tree built of <code>huffman-node</code>s,
and a hash table mapping from elements of the input sequence to <code>huffman-node</code>s.
The priority queue is implemented as a sorted list.
(For a more efficient implementation of a priority queue, see the [[Heapsort]] task.)


<lang lisp>(defstruct huffman-node
<lang lisp>(defstruct huffman-node
Line 1,975: Line 1,976:
io:format("~w", [Bit]),
io:format("~w", [Bit]),
print_bits(Rest).</lang>
print_bits(Rest).</lang>
{{out}}
Output:
<pre> : 111
<pre> : 111
a: 1011
a: 1011
Line 2,035: Line 2,036:
printfn "Symbol\tWeight\tHuffman code";
printfn "Symbol\tWeight\tHuffman code";
printTree ([], tree)</lang>
printTree ([], tree)</lang>
{{out}}
Output:
<pre>Symbol Weight Huffman code
<pre>Symbol Weight Huffman code
p 1 00000
p 1 00000
Line 2,159: Line 2,160:
</lang>
</lang>


{{out}}
Output:
<pre>
<pre>
From "this is an example for huffman encoding"
From "this is an example for huffman encoding"
Line 2,435: Line 2,436:
printCodes(tree, []byte{})
printCodes(tree, []byte{})
}</lang>
}</lang>
{{out}}
Example output:
<pre>
<pre>
SYMBOL WEIGHT HUFFMAN CODE
SYMBOL WEIGHT HUFFMAN CODE
Line 2,594: Line 2,595:
println decoded
println decoded
</lang>
</lang>
{{out}}
Output:
<pre>
<pre>
g: 00000
g: 00000
Line 2,646: Line 2,647:
freq :: Ord a => [a] -> [(Int, a)]
freq :: Ord a => [a] -> [(Int, a)]
freq = map (length &&& head) . group . sort</lang>
freq = map (length &&& head) . group . sort</lang>
{{out}}
Example output:
<lang haskell>*Main> test "this is an example for huffman encoding"
<lang haskell>*Main> test "this is an example for huffman encoding"
'p' : 00000
'p' : 00000
Line 2,684: Line 2,685:


===A non-tree version===
===A non-tree version===
This produces the output required without building the Huffman tree at all, by building all the trace strings directly while reducing the histogram:
This produces the output required without building the Huffman tree at all,
by building all the trace strings directly while reducing the histogram:
<lang haskell>import Data.List (sortBy, insertBy, sort, group)
<lang haskell>import Data.List (sortBy, insertBy, sort, group)
import Control.Arrow (second, (&&&))
import Control.Arrow (second, (&&&))
Line 2,765: Line 2,767:
end</lang>
end</lang>


{{out}}
Sample output:
<pre>Input String : "this is an example for huffman encoding"
<pre>Input String : "this is an example for huffman encoding"
char freq encoding
char freq encoding
Line 3,001: Line 3,003:
}</lang>
}</lang>


{{out}}
Example output:
<pre>SYMBOL WEIGHT HUFFMAN CODE
<pre>SYMBOL WEIGHT HUFFMAN CODE
d 1 00000
d 1 00000
Line 3,113: Line 3,115:
print("is decoded string same as original? " + (s==t));</lang>
print("is decoded string same as original? " + (s==t));</lang>


{{out}}
output
<pre style='width: full; overflow: scroll'>this is an example for huffman encoding
<pre style='width: full; overflow: scroll'>this is an example for huffman encoding
'n': 000
'n': 000
Line 3,309: Line 3,311:
}</lang>
}</lang>


{{out}}
Example output:
<pre>
<pre>
SYMBOL WEIGHT HUFFMAN CODE
SYMBOL WEIGHT HUFFMAN CODE
Line 3,488: Line 3,490:


say .perl for huffman('this is an example for huffman encoding');</lang>
say .perl for huffman('this is an example for huffman encoding');</lang>
{{out}}
Output:
<pre>"d" => "000000"
<pre>"d" => "000000"
"c" => "000001"
"c" => "000001"
Line 3,518: Line 3,520:
$rx = eval '/' ~ $rx ~ '/';
$rx = eval '/' ~ $rx ~ '/';
say $huf.subst(/<$rx>/, -> $/ {%dec{~$/}}, :g);</lang>
say $huf.subst(/<$rx>/, -> $/ {%dec{~$/}}, :g);</lang>
{{out}}
Output:
<pre>this is an example for huffman encoding
<pre>this is an example for huffman encoding
0111111100001100001000011000010011010101000110000101101101100111111000110100010110010010010111001110001000101101011010101000111010000011100000000000110111111
0111111100001100001000011000010011010101000110000101101101100111111000110100010110010010010111001110001000101101011010101000111010000011100000000000110111111
Line 3,557: Line 3,559:
?></lang>
?></lang>


{{out}}
Example output:
<pre>
<pre>
Symbol Weight Huffman Code
Symbol Weight Huffman Code
Line 3,602: Line 3,604:
(recurse (cadr P) (cons 0 L))
(recurse (cadr P) (cons 0 L))
(recurse (cddr P) (cons 1 L)) ) ) )</lang>
(recurse (cddr P) (cons 1 L)) ) ) )</lang>
{{out}}
Output:
<pre>n 000
<pre>n 000
m 0100
m 0100
Line 3,882: Line 3,884:


End;</lang>
End;</lang>
{{out}}
Output:
<pre>The list of nodes:
<pre>The list of nodes:
id c oc l r f d t
id c oc l r f d t
Line 3,998: Line 4,000:
run(V, [Other|RRest], [1,V], [Other|RRest]):-
run(V, [Other|RRest], [1,V], [Other|RRest]):-
dif(V, Other).</lang>
dif(V, Other).</lang>
{{out}}
Output :
<pre> ?- huffman.
<pre> ?- huffman.
Symbol Weight Code
Symbol Weight Code
Line 4,108: Line 4,110:
CloseConsole()</lang>
CloseConsole()</lang>


{{out}}
output:
<pre> 110
<pre> 110
n 000
n 000
Line 4,162: Line 4,164:
print "%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1])</lang>
print "%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1])</lang>


{{out}}
Example output:
<pre>Symbol Weight Huffman Code
<pre>Symbol Weight Huffman Code
6 101
6 101
Line 4,561: Line 4,563:
End
End
Return</lang>
Return</lang>
{{out}}
Output:
<pre>We encode this string:
<pre>We encode this string:
this is an example for huffman encoding
this is an example for huffman encoding
Line 4,760: Line 4,762:
}</lang>
}</lang>


{{out}}
Output:

<pre>
<pre>
Char Weight Encoding
Char Weight Encoding
Line 4,840: Line 4,841:
(define tree (huffman-tree (nodeify freq-table)))
(define tree (huffman-tree (nodeify freq-table)))
(list-encodings tree (map car freq-table))</lang>
(list-encodings tree (map car freq-table))</lang>
Output:


{{out}}
<pre>
<pre>
t:(1 0 0 1 1)
t:(1 0 0 1 1)
Line 5,096: Line 5,097:
puts $str
puts $str
puts [string map $encoding $str]</lang>
puts [string map $encoding $str]</lang>
{{out}}
outputs
<pre style='width:full; overflow:scroll'>n 4 000
<pre style='width:full; overflow:scroll'>n 4 000
6 101
6 101
Line 5,146: Line 5,147:
* <code>~&plrDSLrnPlrmPCAS/'01'</code> otherwise there are two subtrees, hence two lists previously computed results propagating upward, so insert a zero into all of the bit strings in the results on the left, and a one into all the ones on the right, concatenate the left and right results, and propagate the contatenation upward
* <code>~&plrDSLrnPlrmPCAS/'01'</code> otherwise there are two subtrees, hence two lists previously computed results propagating upward, so insert a zero into all of the bit strings in the results on the left, and a one into all the ones on the right, concatenate the left and right results, and propagate the contatenation upward


{{out}}
output:
<pre><
<pre><
`r: '00000',
`r: '00000',
Retrieved from "https://rosettacode.org/wiki/Huffman_coding"