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 can construct and concisely represent optimal prefix (minimum-redundancy) coding whose codeword lengths are a multiple of given number of bits (1-bit, 2-bits, ...). The library supports Huffman trees of arbitrary degrees, even those that are not powers of 2.

The library uses modified Huffman algorithm, with ideas from 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

```rust 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::fromfrequencies(BitsPerFragment(1), hashmap!('a' => 100, 'b' => 50, 'c' => 10)); // We expected the following Huffman tree: // / \ // /\ a // bc // and the following code assignment: a -> 1, b -> 00, c -> 01 asserteq!(huffman.codesforvalues(), hashmap!( 'a' => Code{ content: 0b1, len: 1 }, 'b' => Code{ content: 0b00, len: 2 }, 'c' => Code{ content: 0b01, len: 2 } )); let mut decoderfora = huffman.decoder(); asserteq!(decoderfora.consume(1), DecodingResult::Value(&'a')); let mut decoderforb = huffman.decoder(); asserteq!(decoderforb.consume(0), DecodingResult::Incomplete); asserteq!(decoderforb.consume(0), DecodingResult::Value(&'b')); let mut decoderforc = huffman.decoder(); asserteq!(decoderforc.consume(0), DecodingResult::Incomplete); asserteq!(decoderforc.consume(1), DecodingResult::Value(&'c')); asserteq!(huffman.totalfragmentscount(), 5); asserteq!(huffman.values.asref(), ['a', 'b', 'c']); ```