huffman

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

• func Print(root *Node)
• type Node
  • func Build(leaves []*Node) *Node
  • func BuildSorted(leaves []*Node) *Node
  • func (n *Node) Code() (r uint64, bits byte)
• type SortNodes
  • func (sn SortNodes) Len() int
  • func (sn SortNodes) Less(i, j int) bool
  • func (sn SortNodes) Swap(i, j int)
• type ValueType

Functions

func Print

func Print(root *Node)

Print traverses the Huffman tree and prints the values with their code in binary representation. For debugging purposes.

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

func Build(leaves []*Node) *Node

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

func BuildSorted(leaves []*Node) *Node

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.

func (*Node) Code

func (n *Node) Code() (r uint64, bits byte)

Code returns the Huffman code of the node. Left children get bit 0, Right children get bit 1. Implementation uses Node.Parent to walk "up" in the tree.

type SortNodes

type SortNodes []*Node

SortNodes implements sort.Interface, order defined by Node.Count.

func (SortNodes) Len

func (sn SortNodes) Len() int

func (SortNodes) Less

func (sn SortNodes) Less(i, j int) bool

func (SortNodes) Swap

func (sn SortNodes) Swap(i, j int)

type ValueType

type ValueType int32

ValueType is the type of the value stored in a Node.