61 lines
2.2 KiB
Plaintext
61 lines
2.2 KiB
Plaintext
record huffnode(l,r,n,c) # internal and leaf nodes
|
|
record huffcode(c,n,b,i) # encoding table char, freq, bitstring, bits (int)
|
|
|
|
procedure main()
|
|
|
|
s := "this is an example for huffman encoding"
|
|
|
|
Count := huffcount(s) # frequency count
|
|
Tree := huffTree(Count) # heap and tree
|
|
|
|
Code := [] # extract encodings
|
|
CodeT := table()
|
|
every x := huffBits(Tree) do
|
|
put( Code, CodeT[c] := huffcode( c := x[-1], Count[c].n, b := x[1:-1], integer("2r"||b) ) )
|
|
|
|
|
|
Code := sortf( Code, 1 ) # show table in char order
|
|
write("Input String : ",image(s))
|
|
write(right("char",5), right("freq",5), " encoding" )
|
|
every write(right(image((x := !Code).c),5), right(x.n,5), " ", x.b )
|
|
|
|
end
|
|
|
|
procedure huffBits(N) # generates huffman bitcodes with trailing character
|
|
if \N.c then return N.c # . append leaf char code
|
|
suspend "0" || huffBits(N.l) # . left
|
|
suspend "1" || huffBits(N.r) # . right
|
|
end
|
|
|
|
|
|
procedure huffTree(T) # two queue huffman tree method
|
|
local Q1,Q2,x,n1,n2
|
|
|
|
Q1 := [] # queue of characters and weights
|
|
every x := !T do # ensure all are huffnodes
|
|
if type(x) == "huffnode" then put(Q1,x) else runerr(205,x)
|
|
Q1 := sortf(Q1,3) # sort by weight ( 3 means by .n )
|
|
|
|
if *Q1 > 1 then Q2 := []
|
|
while *Q1+*\Q2 > 1 do { # While there is more than one node ...
|
|
|
|
n1 := if Q1[1] & ( ( Q1[1].n <= Q2[1].n ) | not Q2[1] ) then get(Q1) else get(Q2) # lowest weight from Q1 or Q2
|
|
n2 := if Q1[1] & ( ( Q1[1].n <= Q2[1].n ) | not Q2[1] ) then get(Q1) else get(Q2) # lowest weight from Q1 or Q2
|
|
|
|
put( Q2, huffnode( n1, n2, n1.n + n2.n ) ) # new weighted node to end of Q2
|
|
}
|
|
|
|
return (\Q2 | Q1)[1] # return the root node
|
|
end
|
|
|
|
procedure huffcount(s) # return characters and frequencies in a table of huffnodes by char
|
|
local c,T
|
|
|
|
T := table()
|
|
every c := !s do {
|
|
/T[c] := huffnode(,,0,c)
|
|
T[c].n +:= 1
|
|
}
|
|
return T
|
|
end
|