huffman

Documentation

Overview

Package huffman is used to build variable length codes for compression. Frequency data is used to construct a Huffman Tree. A Lookup can be created from that Tree. The Lookup can be used to encode arbitrary symbols as bits and then the Tree can be used to restore those bits back to the original symbols.

For instance, frequency data on letters in English text can be used to build an Huffman tree

Index

• func Encode[T any](data list.List[T], l Lookup[T]) *rye.Bits
• type Frequency
• type HuffIter
• type Lookup
  • func NewLookup[T comparable](t Tree[T]) Lookup[T]
  • func NewTranslateLookup[K comparable, T any](t Tree[T], translator func(T) K) Lookup[T]
• type Tree
  • func MapNew[T comparable](data map[T]int) Tree[T]
  • func New[T any](data []Frequency[T]) Tree[T]

Examples

• Encode (RoundTrip)

Functions

func Encode

func Encode[T any](data list.List[T], l Lookup[T]) *rye.Bits

Encode data to bits using the lookup. Calling Tree.ReadAll on these bits will recover the original data.

Example (RoundTrip)

var letterFrequencyMap = map[rune]int{
	'E': 21912, 'T': 16587, 'A': 14810, 'O': 14003, 'I': 13318, 'N': 12666,
	'S': 11450, 'R': 10977, 'H': 10795, 'D': 7874, 'L': 7253, 'U': 5246,
	'C': 4943, 'M': 4761, 'F': 4200, 'Y': 3853, 'W': 3819, 'G': 3693,
	'P': 3316, 'B': 2715, 'V': 2019, 'K': 1257, 'X': 315, 'Q': 205,
	'J': 188, 'Z': 128,
}
tree := MapNew(letterFrequencyMap)
l := NewLookup(tree)

bits := Encode[rune](list.Slice([]rune("THISISATEST")), l)
// Encoded length is 5, much less than the 11 characters
fmt.Println("Length:", len(bits.Data))

str := string(slice.IterSlice[rune](tree.Iter(bits), nil))
fmt.Println(str)

Output:

Length: 5
THISISATEST

Types

type Frequency

type Frequency[T any] struct {
	Val   T
	Count int
}

Frequency is used for constructing a Huffman Coding.

type HuffIter

type HuffIter[T any] interface {
	liter.Iter[T]
	liter.Starter[T]
	Factory() (copy liter.Iter[T], t T, done bool)
	slice.Slicer[T]
}

HuffIter fulfills liter.Iter as well as liter.Starter and has a Factory method to make a copy and fulfill liter.Factory.

type Lookup

type Lookup[T any] interface {
	Get(v T) *rye.Bits
	All() []T
}

Lookup is used during encoding to finds the bit representation for a value in the tree. If T is comparable use NewLookup to create a Lookup. If T is not comparable, then use NewTranslateLookup and provide a function to translate from T to a comparable type.

func NewLookup

func NewLookup[T comparable](t Tree[T]) Lookup[T]

NewLookup creates a lookup on a Tree with a comparable type. If T on the Tree is not comparable, use NewTranslateLookup.

func NewTranslateLookup

func NewTranslateLookup[K comparable, T any](t Tree[T], translator func(T) K) Lookup[T]

NewTranslateLookup creates a lookup when T is not comparable. A translator function must be provided.

type Tree

type Tree[T any] interface {
	Read(b *rye.Bits) T
	Iter(b *rye.Bits) HuffIter[T]
	// All visits every value in the Tree can calls the given func on each value
	All(fn func(T))
	Len() int
	// contains filtered or unexported methods
}

Tree represents a Huffman Coding.

func MapNew

func MapNew[T comparable](data map[T]int) Tree[T]

New Huffman Coding Tree contructed from a frequency map.

func New

func New[T any](data []Frequency[T]) Tree[T]

New Huffman Coding Tree contructed from Frequency data.