README
¶
huffman
Canonical Huffman codes in Go.
Documentation
¶
Overview ¶
Package huffman implements canonical Huffman codes. These are useful for DEFLATE and other compression algorithms.
References:
<https://www.rfc-editor.org/rfc/rfc1951.html>, Section 3.2.2 <https://en.wikipedia.org/wiki/Canonical_Huffman_code>
Index ¶
- Constants
- type Code
- type Decoder
- func (d Decoder) DebugString() string
- func (d Decoder) Decode(hc Code) (symbol Symbol, minSize byte, maxSize byte)
- func (d Decoder) Dump(w io.Writer) (int64, error)
- func (d Decoder) Encoder() *Encoder
- func (d Decoder) GoString() string
- func (d *Decoder) Init(sizes []byte) error
- func (d *Decoder) InitFromEncoder(e Encoder) error
- func (d Decoder) MarshalJSON() ([]byte, error)
- func (d Decoder) MaxSize() byte
- func (d Decoder) MaxSymbol() Symbol
- func (d Decoder) MinSize() byte
- func (d Decoder) NumSymbols() uint
- func (d Decoder) SizeBySymbol() []byte
- func (d Decoder) String() string
- func (d *Decoder) UnmarshalJSON(raw []byte) error
- type Encoder
- func (e Encoder) DebugString() string
- func (e Encoder) Decoder() *Decoder
- func (e Encoder) Dump(w io.Writer) (int64, error)
- func (e Encoder) Encode(symbol Symbol) Code
- func (e Encoder) GoString() string
- func (e *Encoder) Init(numSymbols int, frequencies []uint32)
- func (e *Encoder) InitFromDecoder(d Decoder) error
- func (e *Encoder) InitFromSizes(sizes []byte) error
- func (e Encoder) MarshalJSON() ([]byte, error)
- func (e Encoder) MaxSize() byte
- func (e Encoder) MaxSymbol() Symbol
- func (e Encoder) MinSize() byte
- func (e Encoder) NumSymbols() uint
- func (e Encoder) SizeBySymbol() []byte
- func (e Encoder) String() string
- func (e *Encoder) UnmarshalJSON(raw []byte) error
- type Symbol
Constants ¶
const InvalidSymbol = Symbol(-1)
InvalidSymbol is returned by some functions to clearly indicate that no symbol is being returned.
const MaxSymbol = Symbol(math.MaxInt32)
MaxSymbol is the maximum valid symbol.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Code ¶
type Code struct {
// Size holds the number of valid bits.
Size byte
// Bits holds the actual values of the bits. The least significant bit
// of Bits is the first bit.
Bits uint32
}
Code represents a sequence of bits.
func MakeReversedCode ¶
MakeReversedCode constructs a Code from a sequence of bits that's in the wrong order, i.e. the least significant bit is the *last* bit in the sequence, instead of the first.
type Decoder ¶
type Decoder struct {
// contains filtered or unexported fields
}
Decoder implements a decoder for canonical Huffman codes.
func NewDecoder ¶ added in v1.1.0
NewDecoder is a convenience function that allocates a new Decoder and calls Init on it. If Init returns an error, NewDecoder panics.
func (Decoder) DebugString ¶ added in v1.1.0
DebugString returns a programmer-readable debugging string of the Decoder's current state.
func (Decoder) Decode ¶
Decode attempts to decode a Huffman code into a Symbol.
If the Decode is completely successful, symbol >= 0 and minSize == maxSize.
If the Decode fails due to insufficient bits, symbol == InvalidSymbol and at least (minSize - hc.Size) additional bits are required to decode this symbol. No more than (maxSize - hc.Size) additional bits will be required.
If the Decode fails due to unreasonable input, symbol == InvalidSymbol and minSize == maxSize == 0.
func (Decoder) GoString ¶ added in v1.1.0
GoString returns a Go expression that would reconstruct this Decoder.
func (*Decoder) Init ¶
Init initializes this Decoder. The argument consists of zero or more bit lengths, one for each symbol in the code, which is used to construct the canonical Huffman code per the algorithm in RFC 1951 Section 3.2.2. Symbols with an assigned bit length of 0 are omitted from the code entirely.
Not all inputs are valid for constructing a canonical Huffman code. In particular, this method will reject "degenerate" codes which use overly long big lengths for some inputs. Degenerate codes consisting of 0 valid symbols or 1 valid symbol are permitted, however, as there is no way to construct a non-degenerate Huffman code for such cases.
func (*Decoder) InitFromEncoder ¶ added in v1.1.0
InitFromEncoder initializes this Decoder to be the mirror of the given Encoder.
func (Decoder) MarshalJSON ¶ added in v1.1.0
MarshalJSON renders this Decoder as JSON data.
func (Decoder) MaxSymbol ¶
MaxSymbol is the last Symbol in the code's alphabet.
(The first Symbol in the code's alphabet is always 0.)
func (Decoder) NumSymbols ¶ added in v1.1.0
NumSymbols returns the total number of symbols in the code's alphabet.
func (Decoder) SizeBySymbol ¶
SizeBySymbol returns a copy of the original bit length array used to initialize this Decoder.
func (*Decoder) UnmarshalJSON ¶ added in v1.1.0
UnmarshalJSON initializes this Decoder from JSON data.
type Encoder ¶
type Encoder struct {
// contains filtered or unexported fields
}
Encoder implements an encoder for canonical Huffman codes.
func NewEncoder ¶ added in v1.1.0
NewEncoder is a convenience function that allocates a new Encoder and calls Init on it.
func NewEncoderFromSizes ¶ added in v1.1.0
NewEncoderFromSizes is a convenience function that allocates a new Encoder and calls InitFromSizes on it. If InitFromSizes returns an error, NewEncoderFromSizes panics.
func (Encoder) DebugString ¶ added in v1.1.0
DebugString returns a programmer-readable debugging string of the Encoder's current state.
func (Encoder) GoString ¶ added in v1.1.0
GoString returns a Go expression that would reconstruct this Encoder.
func (*Encoder) Init ¶
Init initializes this Encoder. The first argument tells Init how many Symbols are in this code's alphabet, and the second argument lists the frequency (i.e. number of occurrences) for each Symbol in the code, one for each Symbol except that any Symbol not represented in the list is assumed to have a frequency of 0.
func (*Encoder) InitFromDecoder ¶ added in v1.1.0
InitFromDecoder initializes this Encoder to be the mirror of the given Decoder.
func (*Encoder) InitFromSizes ¶ added in v1.1.0
InitFromSizes initializes this Encoder from a list of bit lengths, one for each symbol in the code. See Decoder.Init for more details.
func (Encoder) MarshalJSON ¶ added in v1.1.0
MarshalJSON renders this Encoder as JSON data.
func (Encoder) MaxSymbol ¶
MaxSymbol is the last Symbol in the code's alphabet.
(The first Symbol in the code's alphabet is always 0.)
func (Encoder) NumSymbols ¶ added in v1.1.0
NumSymbols returns the total number of symbols in the code's alphabet.
func (Encoder) SizeBySymbol ¶
SizeBySymbol returns an array containing the bit length for each Symbol in the alphabet. This array can be transmitted to another party and used by Decoder to reconstruct this Huffman code on the receiving end.
func (*Encoder) UnmarshalJSON ¶ added in v1.1.0
UnmarshalJSON initializes this Encoder from JSON data.
Source Files