31 lines
1.0 KiB
Plaintext
31 lines
1.0 KiB
Plaintext
import Collections
|
|
|
|
procedure main(A)
|
|
every line := !&input do {
|
|
every (t := table(0))[!line] +:= 1 # Frequency table
|
|
heap := Heap(sort(t), field, "<") # Initial priority queue
|
|
while heap.size() > 1 do { # Tree construction
|
|
every (p1|p2) := heap.get()
|
|
heap.add([&null, p1[2]+p2[2], p1, p2])
|
|
}
|
|
codes := treeWalk(heap.get(),"") # Get codes from tree
|
|
write("Huffman encoding:") # Display codes
|
|
every pair := !sort(codes) do
|
|
write("\t'",\pair[1],"'-> ",pair[2])
|
|
}
|
|
end
|
|
|
|
procedure field(node) # selector function for Heap
|
|
return node[2] # field to use for priority ordering
|
|
end
|
|
|
|
procedure treeWalk(node, prefix, codeMap)
|
|
/codeMap := table("")
|
|
if /node[1] then { # interior node
|
|
treeWalk(node[3], prefix||"0", codeMap)
|
|
treeWalk(node[4], prefix||"1", codeMap)
|
|
}
|
|
else codeMap[node[1]] := prefix
|
|
return codeMap
|
|
end
|