98 lines
1.7 KiB
Plaintext
98 lines
1.7 KiB
Plaintext
class Node
|
|
{
|
|
Float probability := 0.0f
|
|
}
|
|
|
|
class Leaf : Node
|
|
{
|
|
Int character
|
|
|
|
new make (Int character, Float probability)
|
|
{
|
|
this.character = character
|
|
this.probability = probability
|
|
}
|
|
}
|
|
|
|
class Branch : Node
|
|
{
|
|
Node left
|
|
Node right
|
|
|
|
new make (Node left, Node right)
|
|
{
|
|
this.left = left
|
|
this.right = right
|
|
probability = this.left.probability + this.right.probability
|
|
}
|
|
}
|
|
|
|
class Huffman
|
|
{
|
|
Node[] queue := [,]
|
|
Str:Str table := [:]
|
|
|
|
new make (Int[] items)
|
|
{
|
|
uniqueItems := items.dup.unique
|
|
uniqueItems.each |Int item|
|
|
{
|
|
num := items.findAll { it == item }.size
|
|
queue.add (Leaf(item, num.toFloat / items.size))
|
|
}
|
|
createTree
|
|
createTable
|
|
}
|
|
|
|
Void createTree ()
|
|
{
|
|
while (queue.size > 1)
|
|
{
|
|
queue.sort |a,b| {a.probability <=> b.probability}
|
|
node1 := queue.removeAt (0)
|
|
node2 := queue.removeAt (0)
|
|
queue.add (Branch (node1, node2))
|
|
}
|
|
}
|
|
|
|
Void traverse (Node node, Str encoding)
|
|
{
|
|
if (node is Leaf)
|
|
{
|
|
table[(node as Leaf).character.toChar] = encoding
|
|
}
|
|
else // (node is Branch)
|
|
{
|
|
traverse ((node as Branch).left, encoding + "0")
|
|
traverse ((node as Branch).right, encoding + "1")
|
|
}
|
|
}
|
|
|
|
Void createTable ()
|
|
{
|
|
if (queue.size != 1) return // error!
|
|
traverse (queue.first, "")
|
|
}
|
|
|
|
override Str toStr ()
|
|
{
|
|
result := "Huffman Encoding Table:\n"
|
|
table.keys.sort.each |Str key|
|
|
{
|
|
result += "$key -> ${table[key]}\n"
|
|
}
|
|
return result
|
|
}
|
|
}
|
|
|
|
class Main
|
|
{
|
|
public static Void main ()
|
|
{
|
|
example := "this is an example for huffman encoding"
|
|
huffman := Huffman (example.chars)
|
|
echo ("From \"$example\"")
|
|
echo (huffman)
|
|
}
|
|
}
|