Rosetta Code

Huffman coding: Difference between revisions

Page Discussion

Huffman coding (view source)

Revision as of 19:16, 14 January 2021

217 bytes added ,  3 years ago
Changed indentation. Many other minor changes. Changed the output to a sorted list of pairs.
m (Updated the output.)
(Changed indentation. Many other minor changes. Changed the output to a sorted list of pairs.)
Line 3,862:
=={{header|Nim}}==
 
<lang nim>import tables, seqUtilssequtils
 
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
f: int
parent: Node
case isLeaf: bool
of true:
c: char
else:
childs: array[CodeSymbol, Node]
 
# Following range can be changed to produce Huffman codes on arbitrary alphabet (e.g. ternary codes)
proc `<`(a: Node, b: Node): bool =
CodeSymbol = range[0..1]
# For min operator
a.f < b.f
 
proc `$`(hc: HuffCode): string = seq[CodeSymbol]
result = ""
for symbol in hc:
result &= $symbol
 
Node = ref object
proc freeChildList(tree: seq[Node], parent: Node = nil): seq[Node] =
f: int
# Constructs a sequence of nodes which can be adopted
parent: Node
# Optional parent parameter can be set to ensure node will not adopt itself
resultcase =isLeaf: @[]bool
forof node in treetrue:
c: char
if node.parent == nil and node != parent:
else:
result.add(node)
childs: array[CodeSymbol, Node]
 
procfunc connect`<`(parenta: Node, childb: Node): bool =
# For min operator.
# Only call this proc when sure that parent has a free child slot
a.f < b.f
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
 
func `$`(hc: HuffCode): string =
proc generateCodes(codes: TableRef[char, HuffCode], currentNode: Node, currentCode: HuffCode = @[]) =
result = ""
if currentNode.isLeaf:
for symbol in hc:
let key = currentNode.c
result &= $symbol
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)
 
procfunc buildTreefreeChildList(frequenciestree: CountTableseq[charNode], parent: Node = nil): seq[Node] =
## Constructs a sequence of nodes which can be adopted
result = newSeq[Node](frequencies.len)
## Optional parent parameter can be set to ensure node will not adopt itself
for i in result.low..result.high:
for node in tree:
let key = toSeq(frequencies.keys)[i]
if node.parent.isNil and node != parent: result.add(node)
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
 
func connect(parent: Node, child: Node) =
var sampleFrequencies = initCountTable[char]()
# Only call this proc when sure that parent has a free child slot
for c in sampleString:
child.parent = parent
sampleFrequencies.inc(c)
parent.f += child.f
let
for i in parent.childs.low..parent.childs.high:
tree = buildTree(sampleFrequencies)
if parent.childs[i] == nil:
parent.childs[i] = child
return
 
func 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 not currentNode.childs[i].isNil:
let newCode = currentCode & i
generateCodes(codes, currentNode.childs[i], newCode)
 
 
func 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
 
when isMainModule:
 
import algorithm, strformat
 
const
SampleString = "this is an example for huffman encoding"
SampleFrequencies = SampleString.toCountTable()
 
func `<`(code1, code2: HuffCode): bool =
# Used to sort the result.
if code1.len == code2.len:
result = false
for (c1, c2) in zip(code1, code2):
if c1 != c2: return c1 < c2
else:
result = code1.len < code2.len
 
let
tree = buildTree(SampleFrequencies)
root = tree.freeChildList[0]
 
var huffCodes = newTable[char, HuffCode]()
generateCodes( var huffCodes = newTable[char, rootHuffCode]()
echo generateCodes(huffCodes</lang>, root)
 
for (key, value) in sortedByIt(toSeq(huffCodes.pairs), it[1]):
echo &"'{key}' → {value}"</lang>
 
{{out}}
<pre>'n' → 000
<pre>{'d': 01010, 'f': 1001, 'o': 11111, 'i': 1100, 'x': 01011, 'g': 01100, 'r': 01101, 'c': 01110, 's': 0010, 'u': 01111, ' ': 101, 'a': 1101, 'h': 0011, 't': 10000, 'p': 10001, 'l': 11110, 'n': 000, 'm': 0100, 'e': 1110}
' ' → 101
</pre>
's' → 0010
'h' → 0011
'm' → 0100
'f' → 1001
'i' → 1100
'a' → 1101
'e' → 1110
'd' → 01010
'x' → 01011
'g' → 01100
'r' → 01101
'c' → 01110
'u' → 01111
't' → 10000
'p' → 10001
'l' → 11110
'o' → 11111</pre>
 
=={{header|Oberon-2}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/105141"