huffman

README

huffman

Provides basic huffman decoder implemenation.

Installation

$ go get github.com/32bitkid/huffman

Examples

// 0xa5 => 0b 1 01 00 1 01 => True, False, Maybe, True, False

br := br.NewBitReader(bytes.NewReader([]byte{0xa5}))

decoder := huffman.NewBinaryTreeHuffmanDecoder(huffman.HuffmanTable{
    "1":  "True",
    "01": "False",
    "00": "Maybe",
})

for {
    val, err := decoder.Decode(br)
    if err != nil {
        break
    }
    fmt.Println("%s", val)
}

Documentation

Overview

Package huffman implements a naïve Huffman decoder.

Example

package main

import (
	"bytes"
	"fmt"
	br "github.com/32bitkid/bitreader"
	"github.com/32bitkid/huffman"
)

func main() {
	// representation huffman tree generated from the
	// text "this is an example of a huffman tree"

	table := huffman.HuffmanTable{
		"111":   ' ',
		"010":   'a',
		"000":   'e',
		"1101":  'f',
		"1010":  'h',
		"1000":  'i',
		"0111":  'm',
		"0010":  'n',
		"1011":  's',
		"0110":  't',
		"11001": 'l',
		"00110": 'o',
		"10011": 'p',
		"11000": 'r',
		"00111": 'u',
		"10010": 'x',
	}

	decoder := huffman.NewBinaryTreeHuffmanDecoder(table)

	// the text "hello huffman" encoded using the table
	//
	// Text:       h    e   l     l     o     _   h    u     f    f    m    a   n
	// encoded: 0b 1010 000 11001 11001 00110 111 1010 00111 1101 1101 0111 010 0010
	// aligned: 0b 1010 0001 1001 1100 1001 1011 1101 0001 1111 0111 0101 1101 0001 0000
	// hex:     0x    a    1    9    c    9    b    d    1    f    7    5    d    1    0

	data := []byte{0xa1, 0x9c, 0x9b, 0xd1, 0xf7, 0x5d, 0x10}
	r := br.NewReader(bytes.NewReader(data))

	for i := 0; i < 13; i++ {
		val, _ := decoder.Decode(r)
		fmt.Printf("%c", val)
	}

}

Output:

hello huffman

Index

• Variables
• func NewBinaryTreeHuffmanDecoder(t HuffmanTable) *binaryTreeHuffmanDecoder
• type HuffmanDecoder
  • func NewHuffmanDecoder(t HuffmanTable) HuffmanDecoder
• type HuffmanTable

Examples

• Package
• HuffmanDecoder (Simple)

Variables

var ErrMissingHuffmanValue = errors.New("huffman: value not found")

ErrMissingHuffmanValue indiciates the decoded value could not be found in the huffman tree.

Functions

func NewBinaryTreeHuffmanDecoder

func NewBinaryTreeHuffmanDecoder(t HuffmanTable) *binaryTreeHuffmanDecoder

NewBinaryTreeHuffmanDecoder creates a Huffamn decoder that will walk the huffman tree one bit at a time until a match is found.

Types

type HuffmanDecoder

type HuffmanDecoder interface {
	Decode(bitreader.BitReader) (interface{}, error)
}

HuffmanDecoder is the interface that wraps the basic Decode method.

Upon a match, the proper number of bits will be advanced in the bitstream, and the corresponding value will be returned.

Example (Simple)

package main

import (
	"bytes"
	"fmt"
	br "github.com/32bitkid/bitreader"
	"github.com/32bitkid/huffman"
)

func main() {
	table := huffman.HuffmanTable{
		"1":  true,
		"01": false,
		"00": "maybe",
	}
	ternaryDecoder := huffman.NewBinaryTreeHuffmanDecoder(table)

	r := br.NewReader(bytes.NewReader([]byte{0xa0}))

	val, _ := ternaryDecoder.Decode(r)
	fmt.Println(val)
	val, _ = ternaryDecoder.Decode(r)
	fmt.Println(val)
	val, _ = ternaryDecoder.Decode(r)
	fmt.Println(val)

}

Output:

true
false
maybe

func NewHuffmanDecoder

func NewHuffmanDecoder(t HuffmanTable) HuffmanDecoder

NewHuffmanDecoder creates a new huffman decoder with the default implementation.

type HuffmanTable

type HuffmanTable map[string]interface{}

HuffmanTable is the configuration state given to a decoder.