Crate minimum_redundancy 

minimum_redundancy is the Rust library by Piotr Beling to encode and decode data with binary or non-binary minimum-redundancy (Huffman) coding.

The library is fast and consumes low memory both to construct (which is done without explicitly building a tree) and store the coding dictionary (it only stores frequency-sorted symbols and the numbers of non-leaf nodes at successive levels of the canonical Huffman tree). In addition, the implementation is generic. It can construct not only binary codes (obtained via binary Huffman trees), but of any arity (trees of any degree).

The high efficiency of minimum_redundancy is confirmed by benchmarks included in (please cite this paper if you are using minimum_redundancy for research purposes):

• Piotr Beling, BSuccinct: Rust libraries and programs focused on succinct data structures, SoftwareX, Volume 26, 2024, 101681, ISSN 2352-7110, https://doi.org/10.1016/j.softx.2024.101681.

The library uses improved Huffman algorithm, with ideas from the following papers:

• A. Brodnik, S. Carlsson, Sub-linear decoding of Huffman Codes Almost In-Place, 1998
• A. Moffat, J. Katajainen, In-Place Calculation of Minimum-Redundancy Codes. In: Akl S.G., Dehne F., Sack JR., Santoro N. (eds) Algorithms and Data Structures. WADS 1995. Lecture Notes in Computer Science, vol 955. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60220-8_79

Example

use minimum_redundancy::{Coding, Code, DecodingResult, BitsPerFragment};
use maplit::hashmap;

// Construct coding with 1 bit per fragment for values 'a', 'b', 'c',
// whose frequencies of occurrence are 100, 50, 10 times, respectively.
let huffman = Coding::from_frequencies(BitsPerFragment(1), hashmap!('a' => 100u32, 'b' => 50, 'c' => 10));
// We expected the following Huffman tree:
//  /  \
// /\  a
// bc
// and the following code assignment: a -> 1, b -> 00, c -> 01
assert_eq!(huffman.codes_for_values(), hashmap!(
                'a' => Code{ content: 0b1, len: 1 },
                'b' => Code{ content: 0b00, len: 2 },
                'c' => Code{ content: 0b01, len: 2 }
               ));
// reverse codes encode the first levels of the tree on the least significant bits (e.g., c -> 10):
assert_eq!(huffman.reversed_codes_for_values(), hashmap!(
                'a' => Code{ content: 0b1, len: 1 },
                'b' => Code{ content: 0b00, len: 2 },
                'c' => Code{ content: 0b10, len: 2 }
               ));
let mut decoder_for_a = huffman.decoder();
assert_eq!(decoder_for_a.consume(1), DecodingResult::Value(&'a'));
let mut decoder_for_b = huffman.decoder();
assert_eq!(decoder_for_b.consume(0), DecodingResult::Incomplete);
assert_eq!(decoder_for_b.consume(0), DecodingResult::Value(&'b'));
let mut decoder_for_c = huffman.decoder();
assert_eq!(decoder_for_c.consume(0), DecodingResult::Incomplete);
assert_eq!(decoder_for_c.consume(1), DecodingResult::Value(&'c'));
assert_eq!(huffman.total_fragments_count(), 5); // 1+2+2
assert_eq!(huffman.values.as_ref(), ['a', 'b', 'c']); // sorted by frequencies

Structs

BitsPerFragment

Represents the Huffman tree degree that is a power of two, given as the number of bits needed to store a single codeword fragment (so the degree equals 2 to the power of self.0).

Code

Represents a codeword.

CodeIterator

Iterator over the fragments of (unreversed) code.

CodesIterator

Iterator over value-codeword pairs.

Coding

Succinct representation of minimum-redundancy coding (Huffman tree of some degree in the canonical form).

Decoder

Decoder that decodes a value for given code, consuming one codeword fragment (and going one level down the huffman tree) at a time.

Degree

Represents the degree of the Huffman tree (an arbitrary number, not necessarily a power of two).

LevelIterator

Iterator over the levels of the huffman tree.

ReversedCodeIterator

Iterator over the fragments of reversed code.

ReversedCodesIterator

Iterator over value / reversed codeword pairs.

Enums

DecodingResult

Result of decoding a value, returned by Decoder::consume, Decoder::decode and Decoder::decode_next.

ValueSize

Describes the number of bytes needed to store a value of the type ValueType. The number can be constant or can depend on the particular value.

Traits

Frequencies

Types that implement this trait can count numbers of occurrences of values.

TreeDegree

Represents the degree of the Huffman tree, which is equal to the number of different values of a single codeword fragment.

Functions

entropy_to_bpf

Heuristically calculates the number of bits per fragment for which the average codeword length is about constant.