Struct huff_coding::tree::HuffTree

pub struct HuffTree<L: HuffLetter> { /* fields omitted */ }

Struct representing a Huffman Tree with an alphabet of type implementing HuffLetter

A HuffTree can be initialized in two ways:

• from a struct implementing the Weights<L> trait (from_weights), where L must implement the HuffLetter trait
• from a binary representation (try_from_bin): BitVec<Msb0, u8>, where in order to even get it, L must implement the HuffLetterAsBytes trait

Codes stored by the tree can be retrieved using the codes method

How it works

---

When initialized with the HuffTree::from_weights method it follows the steps of the Huffman Coding algorithm (duh):

1. Creates standalone branches for every letter found in the given weights and pushes them onto a branch heap
2. Finds two branches with the lowest weights
3. Makes them children to a branch with a None letter and the children's summed up weight
4. Removes the two found branches from the heap and adds the newly created branch into it
5. Repeats steps 2 to 4 until there's only one branch left
6. Sets the only branch left as root
7. Recurses into the tree to set every branch's code

• Every branch gets its parent's code with its own position in the parent branch (left - 0, right - 1)

Initializing from bits goes as follows:

1. Go through the HuffTree encoded in binary (big endian) bit by bit
2. Every 1 means a joint branch
3. Every 0 means a letter branch followed by size_of::<L> * 8 bits representing the stored letter

Examples

---

Initialization from ByteWeights

use huff_coding::{
    bitvec::prelude::*,
    prelude::{HuffTree, ByteWeights},
};
use std::collections::HashMap;
 
let tree = HuffTree::from_weights(
    ByteWeights::from_bytes(b"abbccc")
);
let codes = tree.read_codes();
 
assert_eq!(
    codes.get(&b'c').unwrap(), 
    &bitvec![Msb0, u8; 0]
);
assert_eq!(
    codes.get(&b'b').unwrap(),
    &bitvec![Msb0, u8; 1, 1]
);
assert_eq!(
    codes.get(&b'a').unwrap(),
    &bitvec![Msb0, u8; 1, 0]
);

Initialization from HashMap<L, usize>:

use huff_coding::{
    bitvec::prelude::*,
    prelude::{HuffTree, Weights},
};
use std::collections::HashMap;
 
let mut weights = HashMap::new();
weights.insert(String::from("pudzian"), 1);
weights.insert(String::from("krol"), 2);
weights.insert(String::from("szef"), 3);
 
let tree = HuffTree::from_weights(weights);
let codes = tree.read_codes();
 
assert_eq!(
    codes.get("szef").unwrap(), 
    &bitvec![Msb0, u8; 0]
);
assert_eq!(
    codes.get("krol").unwrap(),
    &bitvec![Msb0, u8; 1, 1]
);
assert_eq!(
    codes.get("pudzian").unwrap(),
    &bitvec![Msb0, u8; 1, 0]
);

Representing and reading the tree from bits:

use huff_coding::prelude::{HuffTree, ByteWeights};
 
let tree = HuffTree::from_weights(
    ByteWeights::from_bytes(b"abbccc")
);
 
let tree_bin = tree.as_bin();
// the tree's root's left child is a letter branch, which are encoded by a 0 
assert_eq!(*tree_bin.get(1).unwrap(), false);
 
let new_tree = HuffTree::try_from_bin(tree_bin).unwrap();
// the newly created tree is identical, except in weights
assert_eq!(
    tree.read_codes(),
    new_tree.read_codes()
);
assert_ne!(
    tree
        .root()
        .leaf()
        .weight(), 
    new_tree
        .root()
        .leaf()
        .weight()
);
// every weight in a HuffTree read from binary is set to 0 
assert_eq!(
    new_tree
        .root()
        .leaf()
        .weight(),
     0
);

Panics

---

When trying to create a HuffTree<L> from a type implementing Weights<L> with len == 0:

use huff_coding::prelude::{HuffTree, Weights};
use std::collections::HashMap;
 
let weights = HashMap::<char, usize>::new();
 
// panics here at 'provided empty weights'
let tree = HuffTree::from_weights(weights);

Errors

---

When trying to create a HuffTree<L> from binary where the original's letter type is different than the one specified to be read:

use huff_coding::prelude::{HuffTree, ByteWeights};
 
let tree = HuffTree::from_weights(
    ByteWeights::from_bytes(b"abbccc")
);
let tree_bin = tree.as_bin();
let new_tree = HuffTree::<u128>::try_from_bin(tree_bin)
    .expect("this will return a FromBinError");

or when providing a too small/big BitVec to create a HuffTree:

use huff_coding::{
    bitvec::prelude::*,
    prelude::{HuffTree, ByteWeights},
};
 
let tree = HuffTree::<u128>::try_from_bin(bitvec![Msb0, u8; 0, 1])
    .expect("this will return a FromBinError (provided BitVec is to small)");

Implementations

impl<L: HuffLetter> HuffTree<L>

pub fn from_weights<W: Weights<L>>(weights: W) -> Self

Initialize the HuffTree with a struct implementing the Weights<L> trait, where L implements HuffLetter

In order to get the tree represented in binary(Bitvec<Msb0, u8>) you must ensure that L also implements HuffLetterAsBytes

Examples

---

Initialization from ByteWeights

use huff_coding::{
    bitvec::prelude::*,
    prelude::{HuffTree, ByteWeights},
};
use std::collections::HashMap;
 
let tree = HuffTree::from_weights(
    ByteWeights::from_bytes(b"deefff")
);
let codes = tree.read_codes();
 
assert_eq!(
    codes.get(&b'f').unwrap(),
    &bitvec![Msb0, u8; 0]
);
assert_eq!(
    codes.get(&b'e').unwrap(),
    &bitvec![Msb0, u8; 1, 1]
);
assert_eq!(
    codes.get(&b'd').unwrap(),
    &bitvec![Msb0, u8; 1, 0]
);

Initialization from HashMap<L, usize>:

use huff_coding::{
    bitvec::prelude::*,
    prelude::{HuffTree, Weights},
};
use std::collections::HashMap;
 
let mut weights = HashMap::new();
weights.insert('ą', 1);
weights.insert('þ', 2);
weights.insert('😎', 3);
 
let tree = HuffTree::from_weights(weights);
let codes = tree.read_codes();
 
assert_eq!(
    codes.get(&'😎').unwrap(),
    &bitvec![Msb0, u8; 0]
);
assert_eq!(
    codes.get(&'þ').unwrap(),
    &bitvec![Msb0, u8; 1, 1]
);
assert_eq!(
    codes.get(&'ą').unwrap(),
    &bitvec![Msb0, u8; 1, 0]
);

Panics

---

When trying to create a HuffTree<L> from a type implementing Weights<L> with len == 0:

use huff_coding::prelude::{HuffTree, Weights};
use std::collections::HashMap;
 
let weights = HashMap::<char, usize>::new();
 
// panics here at 'provided empty weights'
let tree = HuffTree::from_weights(weights);

pub fn root(&self) -> &HuffBranch<L>

Return a reference to the tree's root branch

pub fn root_mut(&mut self) -> &mut HuffBranch<L>

Return a mutable reference to the tree's root branch

pub fn read_codes(&self) -> HashMap<L, BitVec<Msb0, u8>>

Go down the tree reading every letter's code and returning a HashMap<L, BitVec<Msb0, u8>>

Example

---

use huff_coding::{
    bitvec::prelude::*,
    prelude::{HuffTree, ByteWeights},
};
use std::collections::HashMap;
 
let tree = HuffTree::from_weights(
    ByteWeights::from_bytes(b"ghhiii")
);
let codes = tree.read_codes();
 
let mut cmp_codes = HashMap::new();
cmp_codes.insert(b'i', bitvec![Msb0, u8; 0]);
cmp_codes.insert(b'h', bitvec![Msb0, u8; 1, 1]);
cmp_codes.insert(b'g', bitvec![Msb0, u8; 1, 0]);
 
assert_eq!(codes, cmp_codes);

pub fn read_codes_with_hasher<S: BuildHasher>(
    &self,
    hash_builder: S
) -> HashMap<L, BitVec<Msb0, u8>, S>

Go down the tree reading every letter's code and returning a [HashMap<L, BitVec<Msb0, u8>, S>][HashMap] where S is the provided hash builder (implementing BuildHasher)

Example

---

use huff_coding::{
    bitvec::prelude::*,
    prelude::{HuffTree, ByteWeights},
};
use std::collections::{
    HashMap,
    hash_map::RandomState,
};
 
let tree = HuffTree::from_weights(
    ByteWeights::from_bytes(b"ghhiii")
);
let codes = tree.read_codes_with_hasher(RandomState::default());
 
let mut cmp_codes = HashMap::new();
cmp_codes.insert(b'i', bitvec![Msb0, u8; 0]);
cmp_codes.insert(b'h', bitvec![Msb0, u8; 1, 1]);
cmp_codes.insert(b'g', bitvec![Msb0, u8; 1, 0]);
 
assert_eq!(codes, cmp_codes);

impl<L: HuffLetterAsBytes> HuffTree<L>

pub fn try_from_bin(bin: BitVec<Msb0, u8>) -> Result<Self, FromBinError<L>>

Try to read the provided BitVec<Msb0, u8> and construct a HuffTree<L> from it. Every weight in the newly created tree is set to 0 as they're not stored in the binary representation

In order to call this method, L must implement HuffLetterAsBytes

Decoding scheme

---

1. Go bit by bit
2. Create a HuffBranch with no letter (a joint branch) when a 1 is found
3. When a 0 is found, read next size_of::<L>() * 8 bits and create a value of type L from them, inserting it then into a HuffBranch

Example

---

use huff_coding::prelude::{HuffTree, ByteWeights};
 
let tree = HuffTree::from_weights(
    ByteWeights::from_bytes(b"mnnooo")
);
 
let tree_bin = tree.as_bin();
 
let new_tree = HuffTree::try_from_bin(tree_bin).unwrap();
// the newly created tree is identical, except in weights
assert_eq!(
    tree.read_codes(),
    new_tree.read_codes()
);
assert_ne!(
    tree
        .root()
        .leaf()
        .weight(), 
    new_tree
        .root()
        .leaf()
        .weight()
);
// every weight in a HuffTree read from binary is set to 0 
assert_eq!(
    new_tree
        .root()
        .leaf()
        .weight(),
     0
);

Errors

---

When trying to create a HuffTree<L>from binary where the original's letter type is different than the one specified to be read:

use huff_coding::prelude::{HuffTree, ByteWeights};
 
let tree = HuffTree::from_weights(
    ByteWeights::from_bytes(b"abbccc")
);
let tree_bin = tree.as_bin();
let new_tree = HuffTree::<u128>::try_from_bin(tree_bin)
    .expect("this will return a FromBinError");

or when providing a too small/big BitVec to create a HuffTree:

use huff_coding::{
    bitvec::prelude::*,
    prelude::{HuffTree, ByteWeights},
};
 
let tree = HuffTree::<u128>::try_from_bin(bitvec![Msb0, u8; 0, 1])
    .expect("this will return a FromBinError (provided BitVec is to small)");

pub fn as_bin(&self) -> BitVec<Msb0, u8>

Return a binary representation of the HuffTree<L> (BitVec<Msb0, u8>)

In order to call this method, L must implement HuffLetterAsBytes

Encoding scheme

---

1. Recurse down the tree
2. Every joint branch is encoded as a 1
3. Every letter branch is encoded as a 0 and is followed by the letter itself encoded in binary

Example

---

use huff_coding::prelude::{HuffTree, ByteWeights};
 
let tree = HuffTree::from_weights(
    ByteWeights::from_bytes(b"abbccc")
);
 
let tree_bin = tree.as_bin();
assert_eq!(tree_bin.to_string(), "[10011000, 11100110, 00010011, 00010]");

Trait Implementations

impl<L: Clone + HuffLetter> Clone for HuffTree<L>

pub fn clone(&self) -> HuffTree<L>

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<L: Debug + HuffLetter> Debug for HuffTree<L>

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.