Anonymous user
Huffman coding: Difference between revisions
m
{{out}}
No edit summary |
m ({{out}}) |
||
Line 408:
end Main;</lang>
{{out}}
<pre> = 101
a = 1001
Line 486:
NEXT
END</lang>
{{out}}
<pre>
101
Line 565:
)
& out$("decoded:" str$(decode$(str$!encoded)));</lang>
{{out}}
<pre>(L=
(" ".101)
Line 890:
return 0;
}</lang>
{{out}}
<pre>' ': 000
'a': 1000
'c': 01101
Line 910 ⟶ 912:
'x': 01001
encoded: 0111111010011110000000111100000100010100001010100110001111100110100010101000001011101001000011010111000100010111110001010000101101011011110011000011101010000
decoded: this is an example for huffman encoding</
=={{header|C sharp}}==
<lang csharp>using System;
Line 1,348 ⟶ 1,351:
}</lang>
{{out}}
<pre> 110
a 1001
Line 1,410 ⟶ 1,412:
</lang>
{{out}}
<pre>
SYMBOL WEIGHT HUFFMAN CODE
Line 1,523 ⟶ 1,525:
</lang>
{{out}}
<pre>
> coffee huffman.coffee
---- this is an example for huffman encoding
Line 1,560 ⟶ 1,561:
101 : c (4)
11 : d (8)
▲</lang>
=={{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.)
<lang lisp>(defstruct huffman-node
Line 1,975 ⟶ 1,976:
io:format("~w", [Bit]),
print_bits(Rest).</lang>
{{out}}
<pre> : 111
a: 1011
Line 2,035 ⟶ 2,036:
printfn "Symbol\tWeight\tHuffman code";
printTree ([], tree)</lang>
{{out}}
<pre>Symbol Weight Huffman code
p 1 00000
Line 2,159 ⟶ 2,160:
</lang>
{{out}}
<pre>
From "this is an example for huffman encoding"
Line 2,435 ⟶ 2,436:
printCodes(tree, []byte{})
}</lang>
{{out}}
<pre>
SYMBOL WEIGHT HUFFMAN CODE
Line 2,594 ⟶ 2,595:
println decoded
</lang>
{{out}}
<pre>
g: 00000
Line 2,646 ⟶ 2,647:
freq :: Ord a => [a] -> [(Int, a)]
freq = map (length &&& head) . group . sort</lang>
{{out}}
<lang haskell>*Main> test "this is an example for huffman encoding"
'p' : 00000
Line 2,684 ⟶ 2,685:
===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:
<lang haskell>import Data.List (sortBy, insertBy, sort, group)
import Control.Arrow (second, (&&&))
Line 2,765 ⟶ 2,767:
end</lang>
{{out}}
<pre>Input String : "this is an example for huffman encoding"
char freq encoding
Line 3,001 ⟶ 3,003:
}</lang>
{{out}}
<pre>SYMBOL WEIGHT HUFFMAN CODE
d 1 00000
Line 3,113 ⟶ 3,115:
print("is decoded string same as original? " + (s==t));</lang>
{{out}}
<pre style='width: full; overflow: scroll'>this is an example for huffman encoding
'n': 000
Line 3,309 ⟶ 3,311:
}</lang>
{{out}}
<pre>
SYMBOL WEIGHT HUFFMAN CODE
Line 3,488 ⟶ 3,490:
say .perl for huffman('this is an example for huffman encoding');</lang>
{{out}}
<pre>"d" => "000000"
"c" => "000001"
Line 3,518 ⟶ 3,520:
$rx = eval '/' ~ $rx ~ '/';
say $huf.subst(/<$rx>/, -> $/ {%dec{~$/}}, :g);</lang>
{{out}}
<pre>this is an example for huffman encoding
0111111100001100001000011000010011010101000110000101101101100111111000110100010110010010010111001110001000101101011010101000111010000011100000000000110111111
Line 3,557 ⟶ 3,559:
?></lang>
{{out}}
<pre>
Symbol Weight Huffman Code
Line 3,602 ⟶ 3,604:
(recurse (cadr P) (cons 0 L))
(recurse (cddr P) (cons 1 L)) ) ) )</lang>
{{out}}
<pre>n 000
m 0100
Line 3,882 ⟶ 3,884:
End;</lang>
{{out}}
<pre>The list of nodes:
id c oc l r f d t
Line 3,998 ⟶ 4,000:
run(V, [Other|RRest], [1,V], [Other|RRest]):-
dif(V, Other).</lang>
{{out}}
<pre> ?- huffman.
Symbol Weight Code
Line 4,108 ⟶ 4,110:
CloseConsole()</lang>
{{out}}
<pre> 110
n 000
Line 4,162 ⟶ 4,164:
print "%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1])</lang>
{{out}}
<pre>Symbol Weight Huffman Code
6 101
Line 4,561 ⟶ 4,563:
End
Return</lang>
{{out}}
<pre>We encode this string:
this is an example for huffman encoding
Line 4,760 ⟶ 4,762:
}</lang>
{{out}}
<pre>
Char Weight Encoding
Line 4,840 ⟶ 4,841:
(define tree (huffman-tree (nodeify freq-table)))
(list-encodings tree (map car freq-table))</lang>
{{out}}
<pre>
t:(1 0 0 1 1)
Line 5,096 ⟶ 5,097:
puts $str
puts [string map $encoding $str]</lang>
{{out}}
<pre style='width:full; overflow:scroll'>n 4 000
6 101
Line 5,146 ⟶ 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
{{out}}
<pre><
`r: '00000',
| |||