Huffman coding: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(26 intermediate revisions by 17 users not shown) | |||
Line 29:
create a program to generate a Huffman encoding for each character as a table.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">T Element
Int weight
[(Char, String)] symbols
F (weight, symbols)
.weight = weight
.symbols = symbols
F <(other)
R (.weight, .symbols) < (other.weight, other.symbols)
F encode(symb2freq)
V heap = symb2freq.map((sym, wt) -> Element(wt, [(sym, ‘’)]))
minheap:heapify(&heap)
L heap.len > 1
V lo = minheap:pop(&heap)
V hi = minheap:pop(&heap)
L(&sym) lo.symbols
sym[1] = ‘0’sym[1]
L(&sym) hi.symbols
sym[1] = ‘1’sym[1]
minheap:push(&heap, Element(lo.weight + hi.weight, lo.symbols [+] hi.symbols))
R sorted(minheap:pop(&heap).symbols, key' p -> (p[1].len, p))
V txt = ‘this is an example for huffman encoding’
V symb2freq = DefaultDict[Char, Int]()
L(ch) txt
symb2freq[ch]++
V huff = encode(symb2freq)
print("Symbol\tWeight\tHuffman Code")
L(p) huff
print("#.\t#.\t#.".format(p[0], symb2freq[p[0]], p[1]))</syntaxhighlight>
{{out}}
<pre>
Symbol Weight Huffman Code
6 101
n 4 010
a 3 1001
e 3 1100
f 3 1101
h 2 0001
i 3 1110
m 2 0010
o 2 0011
s 2 0111
g 1 00000
l 1 00001
p 1 01100
r 1 01101
t 1 10000
u 1 10001
x 1 11110
c 1 111110
d 1 111111
</pre>
=={{header|Ada}}==
Line 34 ⟶ 100:
huffman.ads:
<
with Ada.Containers.Ordered_Maps;
with Ada.Finalization;
Line 116 ⟶ 182:
-- free memory after finalization
overriding procedure Finalize (Object : in out Huffman_Tree);
end Huffman;</
huffman.adb:
<
with Ada.Unchecked_Deallocation;
with Ada.Containers.Vectors;
Line 362 ⟶ 428:
end loop;
end Dump_Encoding;
end Huffman;</
example main.adb:
<
with Huffman;
procedure Main is
Line 413 ⟶ 479:
(Char_Natural_Huffman_Tree.Decode (Tree => Tree, Code => Code));
end;
end Main;</
{{out}}
Line 439 ⟶ 505:
=={{header|BBC BASIC}}==
{{incorrect|BBC BASIC|Huffman code can not contain another code as a prefix}}
{{works with|BBC BASIC for Windows}}
<
SortUp% = FN_sortSAinit(0,0) : REM Ascending
SortDn% = FN_sortSAinit(1,0) : REM Descending
Line 492 ⟶ 559:
ENDIF
NEXT
END</
{{out}}
<pre>
Line 515 ⟶ 582:
t 11010
</pre>
=={{header|Bracmat}}==
<
& 0:?chars
& 0:?p
Line 571 ⟶ 639:
| !arg
)
& out$("decoded:" str$(decode$(str$!encoded)));</
{{out}}
<pre>(L=
Line 596 ⟶ 664:
decoded: this is an example for huffman encoding
</pre>
=={{header|C}}==
This code lacks a lot of needed checkings, especially for memory allocation.
<
#include <stdlib.h>
#include <string.h>
Line 773 ⟶ 842:
return 0;
}</
===Alternative===
Using a simple heap-based priority queue. Heap is an array, while ndoe tree is done by binary links.
<
#include <string.h>
Line 898 ⟶ 967:
return 0;
}</
{{out}}
<pre>' ': 000
Line 923 ⟶ 992:
=={{header|C sharp}}==
<
using System.Collections.Generic;
Line 1,236 ⟶ 1,305:
}
}
}</
[[File:CSharpHuffman.jpg]]
=={{header|C++}}==
Line 1,243 ⟶ 1,312:
This code builds a tree to generate huffman codes, then prints the codes.
<
#include <queue>
#include <map>
Line 1,357 ⟶ 1,426:
}
return 0;
}</
{{out}}
Line 1,382 ⟶ 1,451:
=={{header|Clojure}}==
(Updated to 1.6 & includes pretty-printing). Uses Java PriorityQueue
<
(defn probs [s]
Line 1,415 ⟶ 1,484:
(->> s huffman-encode (sort-by :weight >) print-table))
(display-huffman-encode "this is an example for huffman encoding")</
{{out}}
Line 1,441 ⟶ 1,510:
===Alternate Version===
Uses c.d.priority-map. Creates a more shallow tree but appears to meet the requirements.
<
(require '[clojure.pprint :refer [print-table]])
Line 1,478 ⟶ 1,547:
(->> s huffman-encode (sort-by :weight >) print-table))
(display-huffman-encode "this is an example for huffman encoding")</
{{out}}
<pre>| :sym | :weight | :code |
Line 1,503 ⟶ 1,572:
=={{header|CoffeeScript}}==
<
huffman_encoding_table = (counts) ->
# counts is a hash where keys are characters and
Line 1,589 ⟶ 1,658:
console.log "#{rpad(code, 5)}: #{c} (#{counts[c]})"
console.log()
</
{{out}}
Line 1,627 ⟶ 1,696:
101 : c (4)
11 : d (8)
</pre>
=={{header|Common Lisp}}==
Line 1,636 ⟶ 1,705:
(For a more efficient implementation of a priority queue, see the [[Heapsort]] task.)
<
(weight 0 :type number)
(element nil :type t)
Line 1,694 ⟶ 1,763:
(huffman-node-element node)
(huffman-node-weight node)
(huffman-node-encoding node))))</
Example:
Line 1,722 ⟶ 1,791:
=={{header|D}}==
<
auto encode(alias eq, R)(Group!(eq, R) sf) /*pure nothrow @safe*/ {
Line 1,742 ⟶ 1,811:
foreach (const p; s.dup.sort().group.encode)
writefln("'%s' %s", p[]);
}</
{{out}}
<pre>' ' 101
Line 1,766 ⟶ 1,835:
=={{header|Eiffel}}==
Adapted C# solution.
<
class HUFFMAN_NODE[T -> COMPARABLE]
inherit
Line 1,955 ⟶ 2,024:
end
end
</syntaxhighlight>
{{out}}
Line 1,978 ⟶ 2,047:
x: 01010
</pre>
=={{header|Erlang}}==
The main part of the code used here is extracted from [https://gist.github.com/rmies/2828351 Michel Rijnders' GitHubGist]. See also [http://codingpraxis.com/erlang/2012/10/23/huffman-coding-in-erlang.html his blog], for a complete description of the original module.
<
-export([encode/1, decode/2, main/0]).
Line 2,042 ⟶ 2,112:
print_bits(<<Bit:1, Rest/bitstring>>) ->
io:format("~w", [Bit]),
print_bits(Rest).</
{{out}}
<pre> : 111
Line 2,068 ⟶ 2,138:
=={{header|F_Sharp|F#}}==
{{Trans|OCaml}}
<
| Leaf of int * 'a
| Node of int * 'a HuffmanTree * 'a HuffmanTree
Line 2,102 ⟶ 2,172:
let tree = charFreqs |> Map.toList |> buildTree
printfn "Symbol\tWeight\tHuffman code";
printTree ([], tree)</
{{out}}
<pre>Symbol Weight Huffman code
Line 2,124 ⟶ 2,194:
e 3 1101
6 111</pre>
=={{header|Factor}}==
<syntaxhighlight lang="factor">
USING: kernel sequences combinators accessors assocs math hashtables math.order
sorting.slots classes formatting prettyprint ;
IN: huffman
! -------------------------------------
! CLASSES -----------------------------
! -------------------------------------
TUPLE: huffman-node
weight element encoding left right ;
! For nodes
: <huffman-tnode> ( left right -- huffman )
huffman-node new [ left<< ] [ swap >>right ] bi ;
! For leafs
: <huffman-node> ( element -- huffman )
1 swap f f f huffman-node boa ;
! --------------------------------------
! INITIAL HASHTABLE --------------------
! --------------------------------------
<PRIVATE
! Increment node if it already exists
! Else make it and add it to the hash-table
: huffman-gen ( element nodes -- )
2dup at
[ [ [ 1 + ] change-weight ] change-at ]
[ [ dup <huffman-node> swap ] dip set-at ] if ;
! Curry node-hash. Then each over the seq
! to get the weighted values
: (huffman) ( nodes seq -- nodes )
dup [ [ huffman-gen ] curry each ] dip ;
! ---------------------------------------
! TREE GENERATION -----------------------
! ---------------------------------------
: (huffman-weight) ( node1 node2 -- weight )
[ weight>> ] dup bi* + ;
! Combine two nodes into the children of a parent
! node which has a weight equal to their collective
! weight
: (huffman-combine) ( node1 node2 -- node3 )
[ (huffman-weight) ]
[ <huffman-tnode> ] 2bi
swap >>weight ;
! Generate a tree by combining nodes
! in the priority queue until we're
! left with the root node
: (huffman-tree) ( nodes -- tree )
dup rest empty?
[ first ] [
{ { weight>> <=> } } sort-by
[ rest rest ] [ first ]
[ second ] tri
(huffman-combine) prefix
(huffman-tree)
] if ; recursive
! --------------------------------------
! ENCODING -----------------------------
! --------------------------------------
: (huffman-leaf?) ( node -- bool )
[ left>> huffman-node instance? ]
[ right>> huffman-node instance? ] bi and not ;
: (huffman-leaf) ( leaf bit -- )
swap encoding<< ;
DEFER: (huffman-encoding)
! Recursively walk the nodes left and right
: (huffman-node) ( bit nodes -- )
[ 0 suffix ] [ 1 suffix ] bi
[ [ left>> ] [ right>> ] bi ] 2dip
[ swap ] dip
[ (huffman-encoding) ] 2bi@ ;
: (huffman-encoding) ( bit nodes -- )
over (huffman-leaf?)
[ (huffman-leaf) ]
[ (huffman-node) ] if ;
PRIVATE>
! -------------------------------
! USER WORDS --------------------
! -------------------------------
: huffman-print ( nodes -- )
"Element" "Weight" "Code" "\n%10s\t%10s\t%6s\n" printf
{ { weight>> >=< } } sort-by
[ [ encoding>> ] [ element>> ] [ weight>> ] tri
"%8c\t%7d\t\t" printf pprint "\n" printf ] each ;
: huffman ( sequence -- nodes )
H{ } clone (huffman) values
[ (huffman-tree) { } (huffman-encoding) ] keep ;
! ---------------------------------
! USAGE ---------------------------
! ---------------------------------
! { 1 2 3 4 } huffman huffman-print
! "this is an example of a huffman tree" huffman huffman-print
! Element Weight Code
! 7 { 0 0 0 }
! a 4 { 1 1 1 }
! e 4 { 1 1 0 }
! f 3 { 0 0 1 0 }
! h 2 { 1 0 1 0 }
! i 2 { 0 1 0 1 }
! m 2 { 0 1 0 0 }
! n 2 { 0 1 1 1 }
! s 2 { 0 1 1 0 }
! t 2 { 0 0 1 1 }
! l 1 { 1 0 1 1 1 }
! o 1 { 1 0 1 1 0 }
! p 1 { 1 0 0 0 1 }
! r 1 { 1 0 0 0 0 }
! u 1 { 1 0 0 1 1 }
! x 1 { 1 0 0 1 0 }
</syntaxhighlight>
=={{header|Fantom}}==
<
class Node
{
Line 2,225 ⟶ 2,431:
}
}
</syntaxhighlight>
{{out}}
Line 2,254 ⟶ 2,460:
=={{header|Fortran}}==
<
! d-> 00000, t-> 00001, h-> 0001, s-> 0010,
! c-> 00110, x-> 00111, m-> 0100, o-> 0101,
Line 2,402 ⟶ 2,608:
print *
end program
</syntaxhighlight>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">type block
freq as uinteger
chars as string
end type
type code
char as string*1
code as string
end type
sub bubble( lst() as block, n_l as uinteger )
for j as integer = n_l-1 to 0 step -1
if j>0 andalso lst(j).freq > lst(j-1).freq then
swap lst(j), lst(j-1)
endif
next j
end sub
dim as string Sample = "this is an example for huffman encoding"
redim as block hufflist(0)
hufflist(0).freq = 1 : hufflist(0).chars = mid(Sample,1,1)
dim as boolean newchar
dim as string*1 currchar
dim as uinteger n_h = 1, n_c
'read characters in one-by-one and simultaneously bubblesort them
for i as uinteger = 2 to len(Sample)
currchar = mid(Sample,i,1)
newchar = true
for j as uinteger = 0 to n_h-1
if mid(Sample,i,1) = hufflist(j).chars then
hufflist(j).freq += 1
newchar = false
end if
if j>0 andalso hufflist(j).freq > hufflist(j-1).freq then
swap hufflist(j), hufflist(j-1)
endif
next j
if newchar then
redim preserve hufflist(0 to n_h)
hufflist(n_h).chars = currchar
hufflist(n_h).freq = 1
n_h+=1
end if
next i
'one final pass of bubblesort may be necessary
bubble hufflist(), n_h
'initialise huffman code
redim as code codelist(0 to n_h-1)
for i as uinteger = 0 to n_h-1
codelist(i).char = hufflist(i).chars
codelist(i).code = ""
next i
n_c = n_h
do
'characters in the least common block get "0" appended
for i as uinteger = 1 to len(hufflist(n_h-1).chars)
for j as uinteger = 0 to n_c-1
if codelist(j).char = mid(hufflist(n_h-1).chars,i,1) then
codelist(j).code = "0" + codelist(j).code
end if
next j
next i
'characters in the second-least common block get "1" appended
for i as uinteger = 1 to len(hufflist(n_h-2).chars)
for j as uinteger = 0 to n_c-1
if codelist(j).char = mid(hufflist(n_h-2).chars,i,1) then
codelist(j).code = "1" + codelist(j).code
end if
next j
next i
'combine the two least frequent blocks
hufflist(n_h-2).chars = hufflist(n_h-2).chars + hufflist(n_h-1).chars
hufflist(n_h-2).freq = hufflist(n_h-2).freq + hufflist(n_h-1).freq
redim preserve hufflist(0 to n_h-2)
n_h -= 1
'move the new combined block to its proper place in the list
bubble hufflist(), n_h
loop until n_h = 1
for i as uinteger = 0 to n_c - 1
print "'"+codelist(i).char+"'", codelist(i).code
next i
</syntaxhighlight>
{{out}}
<pre>' ' 111
'n' 001
'a' 1011
'e' 1010
'f' 1101
'i' 1100
's' 1000
'h' 0101
'm' 0100
'o' 0111
't' 10010
'x' 100111
'p' 100110
'l' 00001
'r' 00000
'u' 00011
'c' 00010
'd' 01101
'g' 01100</pre>
=={{header|Go}}==
{{trans|Java}}
<
import (
Line 2,502 ⟶ 2,816:
fmt.Println("SYMBOL\tWEIGHT\tHUFFMAN CODE")
printCodes(tree, []byte{})
}</
{{out}}
<pre>
Line 2,527 ⟶ 2,841:
</pre>
{{trans|Python}}
<
import (
Line 2,591 ⟶ 2,905:
fmt.Printf(" %c %d %s\n", c.sym, sym2freq[c.sym], c.code)
}
}</
=={{header|Groovy}}==
Line 2,597 ⟶ 2,911:
Implemented and tested with Groovy 2.3.
<
import groovy.transform.*
Line 2,648 ⟶ 2,962:
: decoded
}
</syntaxhighlight>
Usage:
<
def message = "this is an example for huffman encoding"
Line 2,661 ⟶ 2,975:
def decoded = decode(encoded, codeTable)
println decoded
</syntaxhighlight>
{{out}}
<pre>
Line 2,690 ⟶ 3,004:
=={{header|Haskell}}==
Credits go to [http://www.haskell.org/haskellwiki/99_questions/46_to_50#Problem_50 huffman] where you'll also find a non-tree solution. Uses sorted list as a priority queue.
<
import Control.Arrow ((&&&), second)
import Data.Ord (comparing)
data HTree a
Line 2,702 ⟶ 3,016:
test :: String -> IO ()
test =
mapM_ (\(a, b) -> putStrLn ('\'' : a : ("
serialize . huffmanTree . freq
Line 2,715 ⟶ 3,029:
huffmanTree =
snd .
head . until (null . tail) hstep . sortBy (comparing fst) . fmap (second Leaf
hstep
Line 2,726 ⟶ 3,040:
:: Ord a
=> [a] -> [(Int, a)]
freq =
main :: IO ()
main = test "this is an example for huffman encoding"</syntaxhighlight>
{{out}}
<syntaxhighlight lang="haskell">'p' : 00000
'r' : 00001
'g' : 00010
Line 2,747 ⟶ 3,063:
'a' : 1100
'e' : 1101
' ' : 111</
===Using <code>Set</code> as a priority queue===
(might be worth it for bigger alphabets):
<
htree :: (Ord t, Num t, Ord a) => S.Set (t, HTree a) -> HTree a
Line 2,762 ⟶ 3,078:
huffmanTree :: (Ord w, Num w, Ord a) => [(w, a)] -> HTree a
huffmanTree = htree . S.fromList . map (second Leaf)</
===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:
<
import Control.Arrow (second, (&&&))
import Data.Ord (comparing)
Line 2,783 ⟶ 3,099:
main = do
test "this is an example for huffman encoding"</
=={{header|Icon}} and {{header|Unicon}}==
<
record huffcode(c,n,b,i) # encoding table char, freq, bitstring, bits (int)
Line 2,845 ⟶ 3,161:
}
return T
end</
{{out}}
Line 2,874 ⟶ 3,190:
and implements the algorithm given in the problem description.
The program produces Huffman codes based on each line of input.
<
procedure main(A)
Line 2,903 ⟶ 3,219:
else codeMap[node[1]] := prefix
return codeMap
end</
A sample run:
Line 2,949 ⟶ 3,265:
'''Solution''' (drawn from [[J:Essays/Huffman_Coding|the J wiki]]):
<
if. 1=#x do. y
else. ((i{x),+/j{x) hc (i{y),<j{y [ i=. (i.#x) -. j=. 2{./:x end.
Line 2,962 ⟶ 3,278:
t=. 0 {:: x hc w NB. minimal weight binary tree
((< S: 0 t) i. w) { <@(1&=)@; S: 1 {:: t
)</
'''Example''':<
t 0 1 0 1 0
h 1 1 1 1 1
Line 2,983 ⟶ 3,299:
c 1 0 0 0 0
d 1 0 0 0 1
g 1 1 1 1 0</
=={{header|Java}}==
This implementation creates an actual tree structure, and then traverses the tree to recover the code.
<
abstract class HuffmanTree implements Comparable<HuffmanTree> {
Line 3,081 ⟶ 3,397:
printCodes(tree, new StringBuffer());
}
}</
{{out}}
Line 3,104 ⟶ 3,420:
f 3 1101
6 111</pre>
=={{header|JavaScript}}==
Line 3,116 ⟶ 3,429:
The Huffman encoder
<
this.str = str;
Line 3,178 ⟶ 3,491:
}
return decoded;
}</
And, using the Huffman encoder
<
print(s);
Line 3,193 ⟶ 3,506:
print(t);
print("is decoded string same as original? " + (s==t));</
{{out}}
Line 3,219 ⟶ 3,532:
this is an example for huffman encoding
is decoded string same as original? true</pre>
{{trans|C}}
<syntaxhighlight lang = "javascript">
class node{
constructor(freq, char, left, right){
this.left = left;
this.right = right;
this.freq = freq;
this.c = char;
}
};
nodes = [];
code = {};
function new_node(left, right){
return new node(left.freq + right.freq, -1, left, right);;
};
function qinsert(node){
nodes.push(node);
nodes.sort(compareFunction);
};
function qremove(){
return nodes.pop();
};
function compareFunction(a, b){
return b.freq - a.freq;
};
function build_code(node, codeString, length){
if (node.c != -1){
code[node.c] = codeString;
return;
};
/* Left Branch */
leftCodeString = codeString + "0";
build_code(node.left, leftCodeString, length + 1);
/* Right Branch */
rightCodeString = codeString + "1";
build_code(node.right, rightCodeString, length + 1);
};
function init(string){
var i;
var freq = [];
var codeString = "";
for (var i = 0; i < string.length; i++){
if (isNaN(freq[string.charCodeAt(i)])){
freq[string.charCodeAt(i)] = 1;
} else {
freq[string.charCodeAt(i)] ++;
};
};
for (var i = 0; i < freq.length; i++){
if (freq[i] > 0){
qinsert(new node(freq[i], i, null, null));
};
};
while (nodes.length > 1){
qinsert(new_node(qremove(), qremove()));
};
build_code(nodes[0], codeString, 0);
};
function encode(string){
output = "";
for (var i = 0; i < string.length; i ++){
output += code[string.charCodeAt(i)];
};
return output;
};
function decode(input){
output = "";
node = nodes[0];
for (var i = 0; i < input.length; i++){
if (input[i] == "0"){
node = node.left;
} else {
node = node.right;
};
if (node.c != -1){
output += String.fromCharCode(node.c);
node = nodes[0];
};
};
return output
};
string = "this is an example of huffman encoding";
console.log("initial string: " + string);
init(string);
for (var i = 0; i < Object.keys(code).length; i++){
if (isNaN(code[Object.keys(code)[i]])){
} else {
console.log("'" + String.fromCharCode(Object.keys(code)[i]) + "'" + ": " + code[Object.keys(code)[i]]);
};
};
huffman = encode(string);
console.log("encoded: " + huffman + "\n");
output = decode(huffman);
console.log("decoded: " + output);
</syntaxhighlight>
<pre style='width: full; overflow: scroll'>
initial string: this is an example of huffman encoding
' ': 111
'a': 1011
'c': 00101
'd': 00100
'e': 1010
'f': 1101
'g': 00111
'h': 0101
'i': 1100
'l': 00110
'm': 0100
'n': 100
'o': 0111
'p': 00001
's': 0110
't': 00000
'u': 00011
'x': 00010
encoded: 000000101110001101111100011011110111001111010000101011010000001001101010111011111011110101000111101110101001011100111101010000101011100100110010000111
decoded: this is an example of huffman encoding
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">
abstract type HuffmanTree end
ch::Char
freq::Int
end
freq::Int
left::HuffmanTree
Line 3,245 ⟶ 3,700:
d
end
function huffmantree(ftable::Dict)
trees::Vector{HuffmanTree} = [HuffmanLeaf(ch, fq) for (ch, fq) in ftable]
while length(trees) > 1
sort!(trees, lt = (x, y) -> x.freq < y.freq, rev = true)
least = pop!(trees)
nextleast = pop!(trees)
Line 3,257 ⟶ 3,712:
end
printencoding(lf::HuffmanLeaf, code
function printencoding(nd::HuffmanNode, code
printencoding(nd.left, code)
printencoding(nd.right, code)
end
Line 3,274 ⟶ 3,729:
printencoding(huffmantree(makefreqdict(msg)), "")
</
Char Freq Huffman code
p 1 00000
Line 3,294 ⟶ 3,749:
a 3 1100
i 3 1101
</pre>
Line 3,300 ⟶ 3,755:
{{trans|Java}}
This implementation creates an actual tree structure, and then traverses the tree to recover the code.
<
abstract class HuffmanTree(var freq: Int) : Comparable<HuffmanTree> {
Line 3,353 ⟶ 3,808:
println("SYMBOL\tWEIGHT\tHUFFMAN CODE")
printCodes(tree, StringBuffer())
}</
{{out}}
Line 3,378 ⟶ 3,833:
=={{header|Lua}}==
This implementation proceeds in three steps: determine word frequencies,
construct the Huffman tree, and finally fold the tree into the codes
while outputting them.
<
local freq = { }
Line 3,456 ⟶ 3,910:
return huffcode "this is an example for huffman encoding"
</syntaxhighlight>
<pre>
frequency word huffman code
Line 3,481 ⟶ 3,935:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Huffman {
comp=lambda (a, b) ->{
Line 3,566 ⟶ 4,020:
}
Huffman
</syntaxhighlight>
{{out}}
Line 3,598 ⟶ 4,052:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
huffman[l_List] := Module[{merge, structure, rules},
Line 3,610 ⟶ 4,064:
rules = (# -> Flatten[Position[structure, #] - 1]) & /@ DeleteDuplicates[l];
{Flatten[l /. rules], rules}];</
=={{header|Nim}}==
<
type
# Following range can be changed to produce Huffman codes on arbitrary alphabet (e.g. ternary codes)
CodeSymbol = range[0..1]
Node = ref object
f: int
parent: Node
c: char
else:
childs: array[CodeSymbol, Node]
# For min operator.
a.f < b.f
func `$`(hc: HuffCode): string =
result = ""
for symbol in hc:
result &= $symbol
## Constructs a sequence of nodes which can be adopted
## Optional parent parameter can be set to ensure node will not adopt itself
for node in tree:
if node.parent.isNil and node != parent: result.add(node)
func connect(parent: Node, child: Node) =
# Only call this proc when sure that parent has a free child slot
child.parent = parent
parent.f += child.f
for i in parent.childs.low..parent.childs.high:
if parent.childs[i] == nil:
parent.childs[i] = child
return
func generateCodes(codes: TableRef[char, HuffCode],
currentNode: Node, currentCode: HuffCode = @[]) =
if currentNode.isLeaf:
let key = currentNode.c
codes[key] = currentCode
return
for i in currentNode.childs.low..currentNode.childs.high:
if not currentNode.childs[i].isNil:
let newCode = currentCode & i
generateCodes(codes, currentNode.childs[i], newCode)
func buildTree(frequencies: CountTable[char]): seq[Node] =
result = newSeq[Node](frequencies.len)
for i in result.low..result.high:
let key = toSeq(frequencies.keys)[i]
result[i] = Node(f: frequencies[key], isLeaf: true, c: key)
while result.freeChildList.len > 1:
let currentNode = new Node
result.add(currentNode)
for c in currentNode.childs:
currentNode.connect(min(result.freeChildList(currentNode)))
if result.freeChildList.len <= 1: break
when isMainModule:
import algorithm, strformat
const
SampleString = "this is an example for huffman encoding"
SampleFrequencies = SampleString.toCountTable()
func `<`(code1, code2: HuffCode): bool =
# Used to sort the result.
if code1.len == code2.len:
result = false
for (c1, c2) in zip(code1, code2):
if c1 != c2: return c1 < c2
else:
result = code1.len < code2.len
let
tree = buildTree(SampleFrequencies)
root = tree.freeChildList[0]
for (key, value) in sortedByIt(toSeq(huffCodes.pairs), it[1]):
echo &"'{key}' → {value}"</syntaxhighlight>
{{out}}
<pre>'n' → 000
' ' → 101
's' → 0010
'h' → 0011
'm' → 0100
'f' → 1001
'i' → 1100
'a' → 1101
'e' → 1110
'd' → 01010
'x' → 01011
'g' → 01100
'r' → 01101
'c' → 01110
'u' → 01111
't' → 10000
'p' → 10001
'l' → 11110
'o' → 11111</pre>
=={{header|Oberon-2}}==
{{works with|oo2c}}
<
MODULE HuffmanEncoding;
IMPORT
Line 3,787 ⟶ 4,280:
END HuffmanEncoding.
</syntaxhighlight>
{{out}}
<pre>
Line 3,815 ⟶ 4,308:
This is not purely Objective-C. It uses Apple's Core Foundation library for its binary heap, which admittedly is very ugly. Thus, this only builds on Mac OS X, not GNUstep.
<
Line 3,964 ⟶ 4,457:
}
return 0;
}</
{{out}}
Line 3,995 ⟶ 4,488:
We use a Set (which is automatically sorted) as a priority queue.
{{works with|OCaml|4.02+}}
<
| Leaf of 'a
| Node of 'a huffman_tree * 'a huffman_tree
Line 4,044 ⟶ 4,537:
let tree = build_tree charFreqs in
print_string "Symbol\tHuffman code\n";
print_tree [] tree</
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
(define phrase "this is an example for huffman encoding")
; prepare initial probabilities table
(define table (ff->list
(fold (lambda (ff x)
(put ff x (+ (ff x 0) 1)))
{}
(string->runes phrase))))
; just sorter...
(define (resort l)
(sort (lambda (x y) (< (cdr x) (cdr y))) l))
; ...to sort table
(define table (resort table))
; build huffman tree
(define tree
(let loop ((table table))
(if (null? (cdr table))
(car table)
(loop (resort (cons
(cons
{ 1 (car table) 0 (cadr table)}
(+ (cdar table) (cdadr table)))
(cddr table)))))))
; huffman codes
(define codes
(map (lambda (i)
(call/cc (lambda (return)
(let loop ((prefix #null) (tree tree))
(if (ff? (car tree))
(begin
(loop (cons 0 prefix) ((car tree) 0))
(loop (cons 1 prefix) ((car tree) 1)))
(if (eq? (car tree) i)
(return (reverse prefix))))))))
(map car table)))
</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="scheme">
(print "weights: ---------------------------")
(for-each (lambda (ch)
(print (string (car ch)) ": " (cdr ch)))
(reverse table))
(print "codes: -----------------------------")
(map (lambda (char code)
(print (string char) ": " code))
(reverse (map car table))
(reverse codes))
</syntaxhighlight>
<pre>
weights: ---------------------------
: 6
n: 4
i: 3
f: 3
e: 3
a: 3
s: 2
o: 2
m: 2
h: 2
x: 1
u: 1
t: 1
r: 1
p: 1
l: 1
g: 1
d: 1
c: 1
codes: -----------------------------
: (0 0 0)
n: (1 1 0)
i: (0 1 0 0)
f: (0 1 0 1)
e: (0 0 1 0)
a: (0 0 1 1)
s: (0 1 1 1)
o: (1 0 1 0)
m: (1 0 1 1)
h: (1 0 0 0)
x: (0 1 1 0 1)
u: (0 1 1 0 0 0)
t: (0 1 1 0 0 1)
r: (1 1 1 1 0)
p: (1 1 1 1 1)
l: (1 1 1 0 0)
g: (1 1 1 0 1)
d: (1 0 0 1 0)
c: (1 0 0 1 1)
</pre>
=={{header|Perl}}==
<
use strict;
Line 4,103 ⟶ 4,693:
print "$enc\n";
print decode($enc, $rev_h), "\n";</
{{out}}
<pre>
Line 4,128 ⟶ 4,718:
this is an example for huffman encoding
</pre>
=={{header|Phix}}==
{{trans|Lua}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">store_nodes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">({</span><span style="color: #000000;">data</span><span style="color: #0000FF;">,</span><span style="color: #000000;">key</span><span style="color: #0000FF;">},</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">build_freqtable</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">freq</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">di</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">di</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">di</span><span style="color: #0000FF;">,</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">store_nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">nodes</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">build_hufftree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">node</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lkey</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_partial_key</span><span style="color: #0000FF;">({</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lfreq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lkey</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">deld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lkey</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rkey</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_partial_key</span><span style="color: #0000FF;">({</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">rfreq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rkey</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">deld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rkey</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">lfreq</span><span style="color: #0000FF;">+</span><span style="color: #000000;">rfreq</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">lkey</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rkey</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">node</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">build_huffcodes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">bits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">integer</span> <span style="color: #000000;">freq</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">node</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">build_huffcodes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">bits</span><span style="color: #0000FF;">&</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">build_huffcodes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">bits</span><span style="color: #0000FF;">&</span><span style="color: #008000;">'1'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">freq</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bits</span><span style="color: #0000FF;">},</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">print_huffcode</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000080;font-style:italic;">/*user_data*/</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">data</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"'%c' [%d] %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">print_huffcodes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">print_huffcode</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">invert_huffcode</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">rd</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rd</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">build_freqtable</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">huff</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">build_hufftree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">build_huffcodes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">huff</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">print_huffcodes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">encoded</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">encoded</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">encoded</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">rd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">invert_huffcode</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rd</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">decoded</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">done</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">done</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">encoded</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">key</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">done</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">key</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">encoded</span><span style="color: #0000FF;">[</span><span style="color: #000000;">done</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rd</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">decoded</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rd</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">decoded</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"this is an example for huffman encoding"</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 4,333 ⟶ 4,840:
'u' [1] 10001
'x' [1] 11110
"10000111111110010010...01101011111000001100 (157 digits)"
"this is an example for huffman encoding"
</pre>
Line 4,341 ⟶ 4,848:
{{trans|Python}} (not exactly)
<
function encode($symb2freq) {
$heap = new SplPriorityQueue;
Line 4,368 ⟶ 4,875:
foreach ($huff as $sym => $code)
echo "$sym\t$symb2freq[$sym]\t$code\n";
?></
{{out}}
Line 4,393 ⟶ 4,900:
e 3 1111
</pre>
=={{header|Picat}}==
{{trans|Prolog}}
<syntaxhighlight lang="picat">go =>
huffman("this is an example for huffman encoding").
huffman(LA) :-
LS=sort(LA),
packList(LS,PL),
PLS=sort(PL).remove_dups(),
build_tree(PLS, A),
coding(A, [], C),
SC=sort(C).remove_dups(),
println("Symbol\tWeight\tCode"),
foreach(SS in SC) print_code(SS) end.
build_tree([[V1|R1], [V2|R2]|T], AF) :-
V = V1 + V2,
A = [V, [V1|R1], [V2|R2]],
( T=[] -> AF=A ; NT=sort([A|T]), build_tree(NT, AF) ).
coding([_A,FG,FD], Code, CF) :-
( is_node(FG) -> coding(FG, [0 | Code], C1)
; leaf_coding(FG, [0 | Code], C1) ),
( is_node(FD) -> coding(FD, [1 | Code], C2)
; leaf_coding(FD, [1 | Code], C2) ),
append(C1, C2, CF).
leaf_coding([FG,FD], Code, CF) :-
CodeR = reverse(Code),
CF = [[FG, FD, CodeR]] .
is_node([_V, _FG, _FD]).
print_code([N, Car, Code]) :-
printf("%w:\t%w\t", Car, N),
foreach(V in Code) print(V) end,
nl.
packList([], []).
packList([X],[[1,X]]).
packList([X|Rest], XRunPacked) :-
XRunPacked = [XRun|Packed],
run(X, Rest, XRun, RRest),
packList(RRest, Packed).
run(V, [], VV, []) :- VV=[1,V].
run(V, [V|LRest], [N1,V], RRest) :-
run(V, LRest, [N, V], RRest),
N1 = N + 1.
run(V, [Other|RRest], [1,V], [Other|RRest]) :-
different_terms(V, Other).</syntaxhighlight>
{{out}}
<pre>Symbol Weight Code
c: 1 01010
d: 1 01011
g: 1 01100
l: 1 01101
p: 1 01110
r: 1 01111
t: 1 10000
u: 1 10001
x: 1 11110
h: 2 11111
m: 2 0010
o: 2 0011
s: 2 0100
a: 3 1001
e: 3 1100
f: 3 1101
i: 3 1110
n: 4 000
: 6 101</pre>
=={{header|PicoLisp}}==
Using a cons cells (freq . char) for leaves, and two cells (freq left . right)
for nodes.
<
(while (cadr Idx) (setq Idx @))
(car Idx) )
Line 4,414 ⟶ 4,995:
(prinl (cdr P) " " L)
(recurse (cadr P) (cons 0 L))
(recurse (cddr P) (cons 1 L)) ) ) )</
{{out}}
<pre>n 000
Line 4,437 ⟶ 5,018:
=={{header|PL/I}}==
<
hencode: Proc Options(main);
/*--------------------------------------------------------------------
Line 4,694 ⟶ 5,275:
End;
End;</
{{out}}
<pre>The list of nodes:
Line 4,764 ⟶ 5,345:
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<syntaxhighlight lang="powershell">
function Get-HuffmanEncodingTable ( $String )
{
Line 4,826 ⟶ 5,407:
}
$EncodedString
</syntaxhighlight>
{{out}}
<pre>
Line 4,857 ⟶ 5,438:
=={{header|Prolog}}==
Works with SWI-Prolog
<
L = 'this is an example for huffman encoding',
atom_chars(L, LA),
Line 4,903 ⟶ 5,484:
N1 is N + 1.
run(V, [Other|RRest], [1,V], [Other|RRest]):-
dif(V, Other).</
{{out}}
<pre> ?- huffman.
Line 4,930 ⟶ 5,511:
=={{header|PureBasic}}==
{{works with|PureBasic|4.50}}
<syntaxhighlight lang="purebasic">
OpenConsole()
Line 5,014 ⟶ 5,595:
CloseConsole()
</syntaxhighlight>
{{out}}
Line 5,042 ⟶ 5,623:
The output is sorted first on length of the code, then on the symbols.
<
from collections import defaultdict
Line 5,068 ⟶ 5,649:
print "Symbol\tWeight\tHuffman Code"
for p in huff:
print "%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1])</
{{out}}
Line 5,094 ⟶ 5,675:
An extension to the method outlined above is given [http://paddy3118.blogspot.com/2009/04/abuse-of-pythons-in-built-data.html here].
===Alternative===
This implementation creates an explicit tree structure, which is used during decoding. We also make use of a "pseudo end of file" symbol and padding bits to facilitate reading and writing encoded data to from/to a file.
<syntaxhighlight lang="python">"""Huffman encoding and decoding. Requires Python >= 3.7."""
from __future__ import annotations
from collections import Counter
from heapq import heapify
from heapq import heappush
from heapq import heappop
from itertools import chain
from itertools import islice
from typing import BinaryIO
from typing import Dict
from typing import Iterable
from typing import Optional
from typing import Tuple
LEFT_BIT = "0"
RIGHT_BIT = "1"
WORD_SIZE = 8 # Assumed to be a multiple of 8.
READ_SIZE = WORD_SIZE // 8
P_EOF = 1 << WORD_SIZE
class Node:
"""Huffman tree node."""
def __init__(
self,
weight: int,
symbol: Optional[int] = None,
left: Optional[Node] = None,
right: Optional[Node] = None,
):
self.weight = weight
self.symbol = symbol
self.left = left
self.right = right
def is_leaf(self) -> bool:
"""Return `True` if this node is a leaf node, or `False` otherwise."""
return self.left is None and self.right is None
def __lt__(self, other: Node) -> bool:
return self.weight < other.weight
def huffman_tree(weights: Dict[int, int]) -> Node:
"""Build a prefix tree from a map of symbol frequencies."""
heap = [Node(v, k) for k, v in weights.items()]
heapify(heap)
# Pseudo end-of-file with a weight of 1.
heappush(heap, Node(1, P_EOF))
while len(heap) > 1:
left, right = heappop(heap), heappop(heap)
node = Node(weight=left.weight + right.weight, left=left, right=right)
heappush(heap, node)
return heappop(heap)
def huffman_table(tree: Node) -> Dict[int, str]:
"""Build a table of prefix codes by visiting every leaf node in `tree`."""
codes: Dict[int, str] = {}
def walk(node: Optional[Node], code: str = ""):
if node is None:
return
if node.is_leaf():
assert node.symbol
codes[node.symbol] = code
return
walk(node.left, code + LEFT_BIT)
walk(node.right, code + RIGHT_BIT)
walk(tree)
return codes
def huffman_encode(data: bytes) -> Tuple[Iterable[bytes], Node]:
"""Encode the given byte string using Huffman coding.
Returns the encoded byte stream and the Huffman tree required to
decode those bytes.
"""
weights = Counter(data)
tree = huffman_tree(weights)
table = huffman_table(tree)
return _encode(data, table), tree
def huffman_decode(data: Iterable[bytes], tree: Node) -> bytes:
"""Decode the given byte stream using a Huffman tree."""
return bytes(_decode(_bits_from_bytes(data), tree))
def _encode(stream: Iterable[int], codes: Dict[int, str]) -> Iterable[bytes]:
bits = chain(chain.from_iterable(codes[s] for s in stream), codes[P_EOF])
# Pack bits (stream of 1s and 0s) one word at a time.
while True:
word = "".join(islice(bits, WORD_SIZE)) # Most significant bit first.
if not word:
break
# Pad last bits if they don't align to a whole word.
if len(word) < WORD_SIZE:
word = word.ljust(WORD_SIZE, "0")
# Byte order becomes relevant when READ_SIZE > 1.
yield int(word, 2).to_bytes(READ_SIZE, byteorder="big", signed=False)
def _decode(bits: Iterable[str], tree: Node) -> Iterable[int]:
node = tree
for bit in bits:
if bit == LEFT_BIT:
assert node.left
node = node.left
else:
assert node.right
node = node.right
if node.symbol == P_EOF:
break
if node.is_leaf():
assert node.symbol
yield node.symbol
node = tree # Back to the top of the tree.
def _word_to_bits(word: bytes) -> str:
"""Return the binary representation of a word given as a byte string,
including leading zeros up to WORD_SIZE.
For example, when WORD_SIZE is 8:
_word_to_bits(b'65') == '01000001'
"""
i = int.from_bytes(word, "big")
return bin(i)[2:].zfill(WORD_SIZE)
def _bits_from_file(file: BinaryIO) -> Iterable[str]:
"""Generate a stream of bits (strings of either "0" or "1") from file-like
object `file`, opened in binary mode."""
word = file.read(READ_SIZE)
while word:
yield from _word_to_bits(word)
word = file.read(READ_SIZE)
def _bits_from_bytes(stream: Iterable[bytes]) -> Iterable[str]:
"""Generate a stream of bits (strings of either "0" or "1") from an
iterable of single byte byte-strings."""
return chain.from_iterable(_word_to_bits(byte) for byte in stream)
def main():
"""Example usage."""
s = "this is an example for huffman encoding"
data = s.encode() # Need a byte string
encoded, tree = huffman_encode(data)
# Pretty print the Huffman table
print(f"Symbol Code\n------ ----")
for k, v in sorted(huffman_table(tree).items(), key=lambda x: len(x[1])):
print(f"{chr(k):<6} {v}")
# Print the bit pattern of the encoded data
print("".join(_bits_from_bytes(encoded)))
# Encode then decode
decoded = huffman_decode(*huffman_encode(data))
print(decoded.decode())
if __name__ == "__main__":
main()
</syntaxhighlight>
{{out}}
<pre>
Symbol Code
------ ----
n 000
110
m 0010
h 0101
i 1001
f 1010
e 1011
a 1110
r 00110
l 00111
c 01000
u 01001
x 01100
d 01101
t 01110
p 01111
Ā 10000
g 10001
o 11110
s 11111
011100101100111111110100111111110111000011010110110011100010011110011110111101010111100011011001010100110101010001011100001101011000010001111001101100100010001100000000
this is an example for huffman encoding
</pre>
=={{header|Quackery}}==
To use this code you will need to load the higher-order words defined at [[Higher-order functions#Quackery]] and the priority queue words defined at [[Priority queue#Quackery]].
The word <code>huffmantree</code> takes a string and generates a tree from it suitable for Huffman decoding. To decode a single character, start with the whole tree and either <code>0 peek</code> or <code>1 peek</code> according to the next bit in the compressed stream until you reach a number (ascii character code.)
The word <code>huffmanlist</code> will turn the Huffman tree into a nest of nests, each containing an ascii character code and a nest containing a Huffman code. The nests are sorted by ascii character code to facilitate binary splitting.
<syntaxhighlight lang="quackery"> [ 2dup peek 1+ unrot poke ] is itemincr ( [ n --> [ )
[ [ 0 128 of ] constant
swap witheach itemincr
' [ i^ join ] map
' [ 0 peek ] filter ] is countchars ( $ --> [ )
[ 0 peek dip [ 0 peek ] < ] is fewerchars ( [ [ --> b )
[ behead rot
behead rot + unrot
dip nested nested
join join ] is makenode ( [ [ --> [ )
[ [ dup pqsize 1 > while
frompq dip frompq
makenode topq again ]
frompq nip
0 pluck drop ] is maketree ( [ --> [ )
[ countchars
pqwith fewerchars
maketree ] is huffmantree ( $ --> [ )
[ stack ] is path.hfl ( --> s )
[ stack ] is list.hfl ( --> s )
forward is makelist ( [ --> )
[ dup size 1 = iff
[ 0 peek
path.hfl behead drop
nested join nested
list.hfl take
join
list.hfl put ] done
unpack
1 path.hfl put
makelist
0 path.hfl replace
makelist
path.hfl release ] resolves makelist ( [ --> )
[ sortwith
[ 0 peek swap 0 peek < ] ] is charsort ( [ --> [ )
[ [] list.hfl put
makelist
list.hfl take
charsort ] is huffmanlist ( [ --> [ )
[ sortwith
[ 1 peek size
swap 1 peek size < ] ] is codesort ( [ --> [ )
[ witheach
[ unpack swap
say ' "' emit
say '" ' echo cr ] ] is echohuff ( [ --> [ )
$ "this is an example for huffman encoding"
huffmantree
huffmanlist
say " Huffman codes sorted by character." cr
dup echohuff cr
say " Huffman codes sorted by code length." cr
codesort echohuff
</syntaxhighlight>
{{out}}
<pre> Huffman codes sorted by character.
" " [ 1 1 1 ]
"a" [ 1 0 0 1 ]
"c" [ 1 0 0 0 1 ]
"d" [ 0 0 1 1 0 ]
"e" [ 1 0 1 1 ]
"f" [ 1 1 0 1 ]
"g" [ 1 0 1 0 1 0 ]
"h" [ 0 0 0 1 ]
"i" [ 1 1 0 0 ]
"l" [ 1 0 0 0 0 ]
"m" [ 0 1 0 0 ]
"n" [ 0 1 1 ]
"o" [ 0 1 0 1 ]
"p" [ 1 0 1 0 1 1 ]
"r" [ 1 0 1 0 0 ]
"s" [ 0 0 0 0 ]
"t" [ 0 0 1 1 1 ]
"u" [ 0 0 1 0 0 ]
"x" [ 0 0 1 0 1 ]
Huffman codes sorted by code length.
" " [ 1 1 1 ]
"n" [ 0 1 1 ]
"a" [ 1 0 0 1 ]
"e" [ 1 0 1 1 ]
"f" [ 1 1 0 1 ]
"h" [ 0 0 0 1 ]
"i" [ 1 1 0 0 ]
"m" [ 0 1 0 0 ]
"o" [ 0 1 0 1 ]
"s" [ 0 0 0 0 ]
"c" [ 1 0 0 0 1 ]
"d" [ 0 0 1 1 0 ]
"l" [ 1 0 0 0 0 ]
"r" [ 1 0 1 0 0 ]
"t" [ 0 0 1 1 1 ]
"u" [ 0 0 1 0 0 ]
"x" [ 0 0 1 0 1 ]
"g" [ 1 0 1 0 1 0 ]
"p" [ 1 0 1 0 1 1 ]</pre>
=={{header|Racket}}==
<
#lang racket
Line 5,201 ⟶ 6,122:
(define decode (make-decoder tree))
;; Here's what the decoded message looks like:
(decode encoded)</
=={{header|Raku}}==
(formerly Perl 6)
===By building a tree===
This version uses nested <code>Array</code>s to build a tree [https://commons.wikimedia.org/wiki/File:HuffmanCodeAlg.png like shown in this diagram], and then recursively traverses the finished tree to accumulate the prefixes.
{{works with|rakudo|2015-12-17}}
<syntaxhighlight lang="raku" line>sub huffman (%frequencies) {
my @queue = %frequencies.map({ [.value, .key] }).sort;
while @queue > 1 {
given @queue.splice(0, 2) -> ([$freq1, $node1], [$freq2, $node2]) {
@queue = (|@queue, [$freq1 + $freq2, [$node1, $node2]]).sort;
}
}
hash gather walk @queue[0][1], '';
}
multi walk ($node, $prefix) { take $node => $prefix; }
multi walk ([$node1, $node2], $prefix) { walk $node1, $prefix ~ '0';
walk $node2, $prefix ~ '1'; }</syntaxhighlight>
===Without building a tree===
This version uses an <code>Array</code> of <code>Pair</code>s to implement a simple priority queue. Each value of the queue is a <code>Hash</code> mapping from letters to prefixes, and when the queue is reduced the hashes are merged on-the-fly, so that the last one remaining is the wanted Huffman table.
{{works with|rakudo|2015-12-17}}
<syntaxhighlight lang="raku" line>sub huffman (%frequencies) {
my @queue = %frequencies.map: { .value => (hash .key => '') };
while @queue > 1 {
@queue.=sort;
my $x = @queue.shift;
my $y = @queue.shift;
@queue.push: ($x.key + $y.key) => hash $x.value.deepmap('0' ~ *),
$y.value.deepmap('1' ~ *);
}
@queue[0].value;
}
# Testing
for huffman 'this is an example for huffman encoding'.comb.Bag {
say "'{.key}' : {.value}";
}
# To demonstrate that the table can do a round trip:
say '';
my $original = 'this is an example for huffman encoding';
my %encode-key = huffman $original.comb.Bag;
my %decode-key = %encode-key.invert;
my @codes = %decode-key.keys;
my $encoded = $original.subst: /./, { %encode-key{$_} }, :g;
my $decoded = $encoded .subst: /@codes/, { %decode-key{$_} }, :g;
.say for $original, $encoded, $decoded;</syntaxhighlight>
{{out}}
<pre>'x' : 11000
'p' : 01100
'h' : 0001
'g' : 00000
'a' : 1001
'e' : 1101
'd' : 110011
's' : 0111
'f' : 1110
'c' : 110010
'm' : 0010
' ' : 101
'n' : 010
'o' : 0011
'u' : 10001
't' : 10000
'i' : 1111
'r' : 01101
'l' : 00001
this is an example for huffman encoding
1000000011111011110111110111101100101010111011100010010010011000000111011011110001101101101000110001111011100010100101010111010101100100011110011111101000000
this is an example for huffman encoding</pre>
=={{header|Red}}==
<
;; message to encode:
Line 5,295 ⟶ 6,300:
]
]
</syntaxhighlight>
{{out}}
<pre> = 111
Line 5,323 ⟶ 6,328:
decoded: this is an example for huffman encoding
</pre>
=={{header|REXX}}==
<
* 27.12.2013 Walter Pachl
* 29.12.2013 -"- changed for test of s=xrange('00'x,'ff'x)
Line 5,581 ⟶ 6,587:
Say ' 'c '-->' code.c
End
Return</
{{out}}
<pre>We encode this string:
Line 5,652 ⟶ 6,658:
=={{header|Ruby}}==
Uses a {{libheader|RubyGems}} package [http://ruby.brian-amberg.de/priority-queue/ PriorityQueue]
<
def huffman_encoding(str)
Line 5,705 ⟶ 6,711:
enc = encode(str, encoding)
dec = decode(enc, encoding)
puts "success!" if str == dec</
<pre>[" ", "111"]
["a", "1011"]
Line 5,732 ⟶ 6,738:
Adapted C++ solution.
<
use std::collections::BTreeMap;
use std::collections::binary_heap::BinaryHeap;
Line 5,819 ⟶ 6,825:
}
}
</syntaxhighlight>
Output:
Line 5,846 ⟶ 6,852:
=={{header|Scala}}==
{{works with|scala|2.8}}
<
import scala.collection.mutable.{Map, PriorityQueue}
Line 5,894 ⟶ 6,900:
}
}
}</
{{out}}
Line 5,921 ⟶ 6,927:
==={{header|Scala (Alternate version)}}===
{{works with|scala|2.11.7}}
<
// this version uses immutable data only, recursive functions and pattern matching
object Huffman {
Line 5,964 ⟶ 6,970:
frequencies.foreach(x => println(x._1.value + "\t" + x._2 + s"/${text.length}" + s"\t${encodeChar(huffmanTree, x._1.value)}"))
}
}</
<pre>
Char Weight Code
Line 5,990 ⟶ 6,996:
=={{header|Scheme}}==
<
(if
(eof-object? (peek-char port))
Line 6,043 ⟶ 7,049:
(define freq-table (char-freq (open-input-string input) '()))
(define tree (huffman-tree (nodeify freq-table)))
(list-encodings tree (map car freq-table))</
{{out}}
Line 6,069 ⟶ 7,075:
=={{header|SETL}}==
<
plaintext := 'this is an example for huffman encoding';
Line 6,106 ⟶ 7,112:
forest less:= [f, n];
return [f, n];
end proc;</
=={{header|Sidef}}==
<
if (n.contains(:a)) {
h{n{:a}} = s
Line 6,162 ⟶ 7,168:
say enc
say decode(enc, tree)</
{{out}}
<pre>n: 000
Line 6,188 ⟶ 7,194:
=={{header|Standard ML}}==
{{works with|SML/NJ}}
<
Leaf of 'a
| Node of 'a huffman_tree * 'a huffman_tree
Line 6,244 ⟶ 7,250:
print "SYMBOL\tHUFFMAN CODE\n";
printCodes ([], tree)
end</
=={{header|Swift}}==
Rather than a priority queue of subtrees, we use the strategy of two sorted lists, one for leaves and one for nodes, and "merge" them as we iterate through them, taking advantage of the fact that any new nodes we create are bigger than any previously created nodes, so go at the end of the nodes list.
{{works with|Swift|2+}}
<
case Leaf(T)
indirect case Node(HuffmanTree<T>, HuffmanTree<T>)
Line 6,314 ⟶ 7,320:
let tree = buildTree(charFreqs)
print("Symbol\tHuffman code")
tree.printCodes("")</
{{out}}
<pre>
Line 6,341 ⟶ 7,347:
=={{header|Tcl}}==
{{tcllib|struct::prioqueue}}
<
package require struct::prioqueue
Line 6,393 ⟶ 7,399:
puts $str
puts [string map $encoding $str]</
{{out}}
<pre style='width:full; overflow:scroll'>n 4 000
Line 6,416 ⟶ 7,422:
this is an example for huffman encoding
0101011111100100101011001001010111000001011101010111100001101100011011101101111001000111010111111011111110111000111100000101110100010000010010001100100011110</pre>
=={{header|UNIX Shell}}==
{{works with|Bourne Again SHell}}
<syntaxhighlight lang="bash">
#!/bin/bash
set -eu
# make scratch directory
t="$(mktemp -d)"
cd "${t:?mktemp failed}"
trap 'rm -r -- "$t"' EXIT
# get character frequencies
declare -a freq=()
while read addr line; do
for c in $line; do
: $((freq[8#$c]++))
done
done < <(od -b -v)
# convert freqs into a bucket queue
declare -i i=0
for c in ${!freq[@]}; do
fn="${freq[c]}.$((i++))"
echo "$c:${freq[c]}" >"$fn"
done
top2() { ls | sort -t. -k1,1n -k2,2n | sed 2q; }
set -- $(top2)
while [[ $# -gt 1 ]]; do
declare -i l="${1%%.*}" r="${2%%.*}" # combine weights into
fn="$((l + r)).$((i++))" # ... new node weight
mkdir "$fn"
mv "$1" "$fn/0"
mv "$2" "$fn/1"
set -- $(top2)
done
echo -e "Symbol\tWeight\tHuffman Code"
cd "$fn"
find . -type f -exec grep . {} + |
tr -d ./ |
awk -F: '{printf "%c\t%d\t%s\n", $2, $3, $1}' |
sort -k 2,2nr -k 3,3n
</syntaxhighlight>
=={{header|Ursala}}==
following the algorithm given above
<
#import nat
#import flo
Line 6,432 ⟶ 7,484:
#cast %csAL
table = code_table 'this is an example for huffman encoding'</
a quick walk through the code starting from the bottom:
* <code>*K2 ^/~&h float+ length</code> compute character frequencies by partitioning the input list of characters by equality, and transforming each equivalence class to a pair containing its member and its cardinality represented as a floating point number
Line 6,465 ⟶ 7,517:
`e: '1101',
` : '111'></pre>
=={{header|Wren}}==
{{trans|Java}}
{{libheader|Wren-queue}}
Note that the results differ from Java because the PriorityQueue implementation is not the same.
<syntaxhighlight lang="wren">import "./queue" for PriorityQueue
class HuffmanTree {
construct new(freq) {
_freq = freq
}
freq { _freq }
compareTo(tree) { _freq - tree.freq }
}
class HuffmanLeaf is HuffmanTree {
construct new (freq, val) {
super(freq)
_val = val
}
val { _val }
}
class HuffmanNode is HuffmanTree {
construct new(l, r) {
super(l.freq + r.freq)
_left = l
_right = r
}
left { _left }
right { _right }
}
var buildTree = Fn.new { |charFreqs|
var trees = PriorityQueue.new()
var index = 0
for (freq in charFreqs) {
if (freq > 0) trees.push(HuffmanLeaf.new(freq, String.fromByte(index)), -freq)
index = index + 1
}
if (trees.count == 0) Fiber.abort("Something went wrong!")
while (trees.count > 1) {
var a = trees.pop()
var b = trees.pop()
var h = HuffmanNode.new(a[0], b[0])
trees.push(h, -h.freq)
}
return trees.pop()[0]
}
var printCodes // recursive
printCodes = Fn.new { |tree, prefix|
if (tree is HuffmanLeaf) {
System.print("%(tree.val)\t%(tree.freq)\t%(prefix)")
} else if (tree is HuffmanNode) {
// traverse left
prefix = prefix + "0"
printCodes.call(tree.left, prefix)
prefix = prefix[0...-1]
// traverse right
prefix = prefix + "1"
printCodes.call(tree.right, prefix)
prefix = prefix[0...-1]
}
}
var test = "this is an example for huffman encoding"
var freqs = List.filled(256, 0)
for (c in test) {
var ix = c.bytes[0]
freqs[ix] = freqs[ix] + 1
}
var tree = buildTree.call(freqs)
System.print("SYMBOL\tWEIGHT\tHUFFMAN CODE")
printCodes.call(tree, "")</syntaxhighlight>
{{out}}
<pre>
SYMBOL WEIGHT HUFFMAN CODE
n 4 000
m 2 0010
o 2 0011
s 2 0100
c 1 01010
d 1 01011
g 1 01100
l 1 01101
p 1 01110
r 1 01111
t 1 10000
u 1 10001
a 3 1001
6 101
e 3 1100
f 3 1101
i 3 1110
x 1 11110
h 2 11111
</pre>
=={{header|Zig}}==
{{trans|Rust}}
<syntaxhighlight lang="zig">
const std = @import("std");
const Node = struct {
frequency: usize,
kind: union(enum) {
internal: struct {
left: *Node,
right: *Node,
},
leaf: u8,
},
fn initLeaf(frequency: usize, ch: u8) Node {
return .{
.frequency = frequency,
.kind = .{ .leaf = ch },
};
}
fn initInternal(
allocator: std.mem.Allocator,
left_child: Node,
right_child: Node,
) !Node {
const left = try allocator.create(Node);
const right = try allocator.create(Node);
left.* = left_child;
right.* = right_child;
return .{
.frequency = left_child.frequency + right_child.frequency,
.kind = .{ .internal = .{ .left = left, .right = right } },
};
}
fn deinit(self: Node, allocator: std.mem.Allocator) void {
switch (self.kind) {
.internal => |inner| {
inner.left.deinit(allocator);
inner.right.deinit(allocator);
allocator.destroy(inner.left);
allocator.destroy(inner.right);
},
.leaf => {},
}
}
fn compare(context: void, a: Node, b: Node) std.math.Order {
_ = context;
return std.math.order(a.frequency, b.frequency);
}
};
pub fn main() !void {
const text = "this is an example for huffman encoding";
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer std.debug.assert(gpa.deinit() == .ok);
const allocator = gpa.allocator();
var frequencies = std.AutoHashMap(u8, usize).init(allocator);
defer frequencies.deinit();
for (text) |ch| {
const gop = try frequencies.getOrPut(ch);
if (gop.found_existing) {
gop.value_ptr.* += 1;
} else {
gop.value_ptr.* = 1;
}
}
var prioritized_frequencies =
std.PriorityQueue(Node, void, Node.compare).init(allocator, {});
defer prioritized_frequencies.deinit();
var freq_it = frequencies.iterator();
while (freq_it.next()) |counted_char| {
try prioritized_frequencies.add(Node.initLeaf(
counted_char.value_ptr.*,
counted_char.key_ptr.*,
));
}
while (prioritized_frequencies.len > 1) {
try prioritized_frequencies.add(try Node.initInternal(
allocator,
prioritized_frequencies.remove(),
prioritized_frequencies.remove(),
));
}
const root = prioritized_frequencies.items[0];
defer root.deinit(allocator);
var codes = std.AutoArrayHashMap(u8, []const u8).init(allocator);
defer codes.deinit();
var arena = std.heap.ArenaAllocator.init(allocator);
defer arena.deinit();
try generateCodes(arena.allocator(), &root, &.{}, &codes);
const stdout = std.io.getStdOut().writer();
var code_it = codes.iterator();
while (code_it.next()) |item| {
try stdout.print("{c}: {s}\n", .{
item.key_ptr.*,
item.value_ptr.*,
});
}
}
fn generateCodes(
arena: std.mem.Allocator,
node: *const Node,
prefix: []const u8,
out_codes: *std.AutoArrayHashMap(u8, []const u8),
) !void {
switch (node.kind) {
.internal => |inner| {
const left_prefix = try arena.alloc(u8, prefix.len + 1);
std.mem.copy(u8, left_prefix, prefix);
left_prefix[prefix.len] = '0';
try generateCodes(arena, inner.left, left_prefix, out_codes);
const right_prefix = try arena.alloc(u8, prefix.len + 1);
std.mem.copy(u8, right_prefix, prefix);
right_prefix[prefix.len] = '1';
try generateCodes(arena, inner.right, right_prefix, out_codes);
},
.leaf => |ch| {
try out_codes.put(ch, prefix);
},
}
}
</syntaxhighlight>
{{out}}
<pre>
n: 000
m: 0010
d: 00110
t: 00111
o: 0100
h: 0101
x: 01100
r: 01101
c: 01110
u: 01111
s: 1000
g: 10010
p: 100110
l: 100111
a: 1010
i: 1011
: 110
e: 1110
f: 1111
</pre>
=={{header|zkl}}==
This code was adapted from Perl, Python and most of the other examples.
<
ft:=Dictionary();
foreach c in (text){ ft[c]=ft.find(c,0)+1 } // leafs w/count
Line 6,490 ⟶ 7,807:
decodeTable:=encodeTable.pump(Dictionary(),"reverse"); // code:symbol
return(encodeTable,decodeTable);
}</
<
fcn decode(bits,table){ // this is a horrible decoder, for testing only
w:=bits.walker(); sink:=Sink(String);
Line 6,498 ⟶ 7,815:
}}catch(TheEnd){}
sink.close();
}</
<
encodeTable,decodeTable := buildHuffman(text);
encodeTable.pump(Console.println,fcn(kv){"%s : %s".fmt(kv.xplode())});
Line 6,508 ⟶ 7,825:
println(e);
0'|Bits decoded to: "%s"|.fmt(decode(e,decodeTable)).println();</
{{out}}
<pre>
|