compression

Documentation

Index

• func HuffDecode(root, current *Node, in []bool, out string) string
• func HuffEncode(codes map[rune][]bool, in string) []bool
• func HuffEncoding(node *Node, prefix []bool, codes map[rune][]bool)
• type Node
  • func HuffTree(listfreq []SymbolFreq) (*Node, error)
• type SymbolFreq

Functions

func HuffDecode

func HuffDecode(root, current *Node, in []bool, out string) string

HuffDecode recursively decodes the binary code in, by traversing the Huffman compression tree pointed by root. current stores the current node of the traversing algorithm. out stores the current decoded string.

func HuffEncode

func HuffEncode(codes map[rune][]bool, in string) []bool

HuffEncode encodes the string in by applying the mapping defined by codes.

func HuffEncoding

func HuffEncoding(node *Node, prefix []bool, codes map[rune][]bool)

HuffEncoding recursively traverses the Huffman tree pointed by node to obtain the map codes, that associates a rune with a slice of booleans. Each code is prefixed by prefix and left and right children are labelled with the booleans false and true, respectively.

Types

type Node

type Node struct {
	// contains filtered or unexported fields
}

A Node of an Huffman tree, which can either be a leaf or an internal node. Each node has a weight. A leaf node has an associated symbol, but no children (i.e., left == right == nil). A parent node has a left and right child and no symbol (i.e., symbol == -1).

func HuffTree

func HuffTree(listfreq []SymbolFreq) (*Node, error)

HuffTree returns the root Node of the Huffman tree by compressing listfreq. The compression produces the most optimal code lengths, provided listfreq is ordered, i.e.: listfreq[i] <= listfreq[j], whenever i < j.

type SymbolFreq

type SymbolFreq struct {
	Symbol rune
	Freq   int
}

A SymbolFreq is a pair of a symbol and its associated frequency.