50 lines
1.2 KiB
Plaintext
50 lines
1.2 KiB
Plaintext
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).
|