Anonymous user
Huffman coding: Difference between revisions
Solve task in Nim
m (→{{header|Sidef}}: modified code to work with Sidef 2.10) |
(Solve task in Nim) |
||
Line 3,214:
{Flatten[l /. rules], rules}];</lang>
=={{header|Nim}}==
<lang nim>import tables, seqUtils
const sampleString = "this is an example for huffman encoding"
type
# Following range can be changed to produce Huffman codes on arbitrary alphabet (e.g. ternary codes)
CodeSymbol = range[0..1]
HuffCode = seq[CodeSymbol]
Node = ref object of RootObj
f: int
parent: Node
case isLeaf: bool
of true:
c: char
else:
childs: array[CodeSymbol, Node]
proc `<`(a: Node, b: Node): bool =
a.f < b.f
proc `$`(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
proc freeChildList(tree: seq[Node], parent: Node = nil): seq[Node] =
result = @[]
for node in tree:
if node.parent == nil and node != parent:
result.add(node)
# Only call this proc when sure that parent has a free child slot
proc connect(parent: Node, child: Node) =
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
proc 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 currentNode.childs[i] != nil:
let newCode = currentCode & i
generateCodes(codes, currentNode.childs[i], newCode)
proc 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
var sampleFrequencies = initCountTable[char]()
for c in sampleString:
sampleFrequencies.inc(c)
let
tree = buildTree(sampleFrequencies)
root = tree.freeChildList[0]
var huffCodes = newTable[char, HuffCode]()
generateCodes(huffCodes, root)
echo huffCodes</lang>
{{out}}
<pre>{ : 101, a: 1001, c: 01010, d: 01011, e: 1100, f: 1101, g: 01100, h: 11111, i: 1110, l: 01101, m: 0010, n: 000, o: 0011, p: 01110, r: 01111, s: 0100, t: 10000, u: 10001, x: 11110}</pre>
=={{header|Objective-C}}==
| |||