Huffman coding: Difference between revisions
→{{header|Picat}}
m (→{{header|Lua}}: the Lua version probably can't be a translation of itself...) |
|||
Line 4,759:
e 3 1111
</pre>
=={{header|Picat}}==
Adapted from the Prolog solution.
<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).</lang>
Output:
<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}}==
| |||