Enum HuffmanTree

pub enum HuffmanTree {
    Leaf(u8, u8),
    Node(Box<HuffmanTree>, Box<HuffmanTree>),
}

HuffmanTree is a simple tree structure used convert encoded words to decoded words and vice versa.

Each leaf of the tree represents a single code word. Their probability is saved as single byte where 255 represents the highest probability, and 0 means the value does not appear.

You most likely don’t want to construct this tree yourself, so look for the 2 methods for constructing the tree for you.

Examples

extern crate huffman_coding;

let fake_data = vec![1, 1, 0, 0, 2];
let tree = huffman_coding::HuffmanTree::from_data(&fake_data[..]);
let probability = tree.get_byte_prob(1);
assert!(probability.is_some());
assert_eq!(probability.unwrap(), 255);

Variants

Leaf(u8, u8)

Node(Box<HuffmanTree>, Box<HuffmanTree>)

Implementations

impl HuffmanTree

pub fn from_table(data: &[u8]) -> Self

Method to read the probability of all 256 possible u8 values from a slice containing 256 elements.

This method can be used to construct a new tree from a list of probabilities. The first element in the slice will be interpreted as the probability of the 0 value appearing, the second as the probability of the 1 value, etc.

Examples

extern crate huffman_coding;

let mut table_data: [u8; 256] = [0; 256];
table_data[0] = 255;
table_data[1] = 128;
table_data[2] = 128;
let tree = huffman_coding::HuffmanTree::from_table(&table_data[..]);

let test_query = tree.get_byte_prob(1);
assert!(test_query.is_some());
assert_eq!(test_query.unwrap(), 128);

Panics

If data contains less than 256 elements

pub fn from_data(data: &[u8]) -> Self

Reads all of data and constructs a huffman tree according to the provided sample data

Examples

extern crate huffman_coding;
let pseudo_data = vec![0, 0, 1, 2, 2];
let tree = huffman_coding::HuffmanTree::from_data(&pseudo_data[..]);

let test_query = tree.get_byte_prob(0);
assert!(test_query.is_some());
assert_eq!(test_query.unwrap(), 255);

pub fn to_table(&self) -> [u8; 256]

Convert an existing huffman tree into an array where each element represents the probability of the index byte to appear according to the huffman tree

This can be used to transmit the encoding scheme via byte buffer

pub fn get_byte_prob(&self, byte: u8) -> Option<u8>

Return the probability of the given byte to appear according to the tree

If this returns None, then the byte should not appear according to the huffman tree If this returns Some, it will be between 255 meaning highest probability, and 1, meaning lowest probability

Trait Implementations

impl Debug for HuffmanTree

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

Formats the value using the given formatter.

impl Ord for HuffmanTree

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for HuffmanTree

fn eq(&self, other: &HuffmanTree) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for HuffmanTree

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Eq for HuffmanTree