#huffman #compression #decompression

huffman-compress

Huffman compression given a probability distribution over arbitrary symbols

9 releases (5 breaking)

0.6.0 Jun 2, 2019
0.5.0 May 10, 2018
0.4.0 Mar 5, 2018
0.3.2 Feb 12, 2018
0.1.1 Jan 29, 2018

#26 in Compression

Download history 17/week @ 2019-05-22 35/week @ 2019-05-29 11/week @ 2019-06-05 12/week @ 2019-06-12 31/week @ 2019-06-19 39/week @ 2019-06-26 45/week @ 2019-07-03 27/week @ 2019-07-10 18/week @ 2019-07-17 1/week @ 2019-07-24 8/week @ 2019-07-31 11/week @ 2019-08-07 88/week @ 2019-08-21 42/week @ 2019-08-28

59 downloads per month

MIT/Apache

21KB
380 lines

huffman-compress

Huffman compression given a probability distribution over arbitrary symbols.

Build Status crates.io docs.rs No Maintenance Intended

Examples

use std::iter::FromIterator;
use std::collections::HashMap;
use bit_vec::BitVec;
use huffman_compress::{CodeBuilder, Book, Tree};

let mut weights = HashMap::new();
weights.insert("CG", 293);
weights.insert("AG", 34);
weights.insert("AT", 4);
weights.insert("CT", 4);
weights.insert("TG", 1);

// Construct a Huffman code based on the weights (e.g. counts or relative
// frequencies).
let (book, tree) = CodeBuilder::from_iter(weights).finish();

// More frequent symbols will be encoded with fewer bits.
assert!(book.get("CG").map_or(0, |cg| cg.len()) <
        book.get("AG").map_or(0, |ag| ag.len()));

// Encode some symbols using the book.
let mut buffer = BitVec::new();
let example = vec!["AT", "CG", "AT", "TG", "AG", "CT", "CT", "AG", "CG"];
for symbol in &example {
    book.encode(&mut buffer, symbol);
}

// Decode the symbols using the tree.
let decoded: Vec<&str> = tree.decoder(&buffer).collect();
assert_eq!(decoded, example);

Documentation

Read the documentation

Changelog

  • 0.5.0
    • Update to bit-vec 0.5.
  • 0.4.0
    • Renamed Tree::decoder() to Tree::unbounded_decoder() to avoid surprises. A new Tree::decoder() takes the maximum number of symbols to decode.
    • No longer reexporting Saturating from num-traits.
  • 0.3.2
    • Preallocate arena space for Huffman tree.
  • 0.3.1
    • Update num-traits to 0.2 (semver compatible).
  • 0.3.0
    • Introduce CodeBuilder.
    • Changes tie breaking order.
  • 0.2.0
    • Allow initialization from iterators without creating a HashMap. Thanks @mernen.
    • Require K: Ord instead of K: Hash + Eq for symbols and switch Book internals from HashMap to BTreeMap.
    • Specify stability guarantees.
  • 0.1.1
    • Expose more methods on Book.
  • 0.1.0
    • Initial release.

License

huffman-compress is dual licensed under the Apache 2.0 and MIT license, at your option.

Dependencies

~200KB