README
¶
huffman
Huffman coding implementation in Go (Huffman tree, Symbol table, Huffman Reader + Writer).
Huffman Tree
Use the Build() function to build a Huffman tree. Use the Print() function to print Huffman codes
of all leaves of a tree (for verification).
Example:
leaves := []*Node{
{Value: ' ', Count: 20},
{Value: 'a', Count: 40},
{Value: 'm', Count: 10},
{Value: 'l', Count: 7},
{Value: 'f', Count: 8},
{Value: 't', Count: 15},
}
root := Build(leaves)
Print(root)
Output:
'a': 0
'm': 100
'l': 1010
'f': 1011
't': 110
' ': 111
Huffman Reader and Writer
The hufio package implements a Huffman Reader and Writer. You may use these to transmit Huffman code of your data.
This Reader and Writer internally manages a Symbol Table (the frequency of encountered symbols, updated dynamically).
The Writer computes and sends the Huffman code of the data, the Reader receives the Huffman code and "reconstructs"
the original data based on that.
The implementation uses a sliding window which is used to manage the symbol table. The sliding window is optional, that is, if no window is used, the symbol table is calculated based on all previously encountered symbols.
Writer + Reader example:
buf := &bytes.Buffer{}
w := NewWriter(buf)
if _, err := w.Write([]byte("Testing Huffman Writer + Reader.")); err != nil {
log.Panicln("Failed to write:", err)
}
if err := w.Close(); err != nil {
log.Panicln("Failed to close:", err)
}
r := NewReader(bytes.NewReader(buf.Bytes()))
if data, err := ioutil.ReadAll(r); err != nil {
log.Panicln("Failed to read:", err)
} else {
log.Println("Read:", string(data))
}
Documentation
¶
Overview ¶
Package huffman implements a Huffman entropy coding.
https://en.wikipedia.org/wiki/Huffman_coding
Use the Build() function to build a Huffman tree. Use the Print() function to print Huffman codes of all leaves of a tree (for verification).
Example:
leaves := []*Node{
{Value: ' ', Count: 20},
{Value: 'a', Count: 40},
{Value: 'm', Count: 10},
{Value: 'l', Count: 7},
{Value: 'f', Count: 8},
{Value: 't', Count: 15},
}
root := Build(leaves)
Print(root)
Output:
'a': 0 'm': 100 'l': 1010 'f': 1011 't': 110 ' ': 111
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Node ¶
type Node struct {
Parent *Node // Optional parent node, for fast code read-out
Left *Node // Optional left node
Right *Node // Optional right node
Count int // Relative frequency
Value ValueType // Optional value, set if this is a leaf
}
Node in the Huffman tree.
func Build ¶
Build builds a Huffman tree from the specified leaves. The content of the passed slice is modified, if this is unwanted, pass a copy. Guaranteed that the same input slice will result in the same Huffman tree.
func BuildSorted ¶
BuildSorted builds a Huffman tree from the specified leaves which must be sorted by Node.Count. The content of the passed slice is modified, if this is unwanted, pass a copy. Guaranteed that the same input slice will result in the same Huffman tree.
Source Files
Directories