Huffman compression — in Rust
Huffman encoding is an algorithm which maps values to bits, making it ideal for lossless compression. In this article, we will explore a Rust-based implementation of Huffman compression and decompression, which are part of the CLI tool huffc. Note that this is a first implementation; optimizations can be made (see Limitations at the end of the article).
The Huffman tree
The Huffman algorithm builds a right- or left-leaning binary tree where the nodes’ values represent the sum of the nodes of the children. The value of the nodes is the frequency of occurrence of that value. The edges build the prefix for the encoding. The tree is built from the bottom up, where the two least frequently occurring values are at the bottom. Below is an example of such a tree:
In the example, we have the following array: [1, 1, 3, 1, 2, 3, 1, 1, 4]. The bottom leaf nodes are for the values 2 and 4, since they are the least frequent. They connect to a parent node whose value is the sum of its children, therefore 2. That node builds a parent node with the next least frequent number, 3. The new parent then creates the root node, which is built with the most frequent value, 1.
This tree is created to build the encodings (also known as prefixes) for the values of the nodes. The encodings are generated by the value associated with the edges. Below is a list of the values with their encodings:
- 1: 1
- 3: 01
- 2: 001
- 4: 000
The Huffman tree is built this way so that the encodings are unambiguous. No encoding can be mistaken for another when reading from left to right. Therefore, the final encoding would look like:
110110010111000Huffman used as compression
So we have seen how Huffman encoding works, but why does this work as a form of compression? Well, let’s take the example array. Say this was a byte array. If we make our encoding bitwise, we can greatly reduce the space needed to store this array. The array is 9 bytes long. Using bitwise encoding, the same information can be represented as 2 bytes, since each 1 and 0 represents a single bit.
Rust Implementation
The implementation of the Huffman encoding will take the naive approach and do it on a byte-by-byte basis. The end of the article briefly explains the drawbacks of this approach and the steps needed to overcome them.
Step 1 — Frequency table
We need to know the occurrence of each value. Since we have some constraints, i.e., we are working on a byte level, we can make some optimizations. We know that the minimum value will be 0 and the maximum 255. Therefore, we can create a fixed array of length 256. The index of the array represents the byte value, and the elements the frequency of that value.
#[derive(Debug)]
pub struct FrequencyBuffer(pub [u64; 256]);
pub fn tally_frequency(bytes: &[u8]) -> FrequencyBuffer {
let mut fb = FrequencyBuffer([0; 256]);
bytes.iter().for_each(|byte| unsafe {
*fb.0.as_mut_ptr().add(*byte as usize) += 1;
});
fb
}Step 2 — Build the Huffman tree
To build the Huffman tree, we do not actually need to build a binary tree. We can use a Vector to optimize the structure. The first index is encoded as 1, the next is 01, the next is 001, and so on... until the last one, which is encoded 0, repeated n times, where n is the length of the vector. Therefore, the least frequent is at the back, and the most frequent is at the front. The actual frequency does not matter, only their relative frequency, which is represented by their position in the buffer. The elements of the buffer are the actual values.
pub fn build_huffman_array(mut freq_buffer: FrequencyBuffer) -> Vec<u8> {
let mut buffer = VecDeque::new();
while let Some((idx, _)) = find_and_pop_min(&mut freq_buffer.0) {
buffer.push_front(idx);
}
buffer.into()
}The method find_and_pop_min is defined below:
// Returns the index of the minimum value, Option because when all values are zero there is nothing
// to pop
type Idx = u8;
type Freq = u64;
pub fn find_and_pop_min(freq_buf: &mut [u64]) -> Option<(Idx, Freq)> {
let mut min_value_idx = None;
let mut min_value = None;
freq_buf.iter_mut().enumerate().for_each(|(idx, byte)| {
if *byte == 0 {
return;
}
match min_value {
None => {
min_value = Some(*byte);
min_value_idx = Some(idx as u8);
}
Some(v) if *byte < v => {
min_value = Some(*byte);
min_value_idx = Some(idx as u8);
}
_ => (),
}
});
if let Some(idx) = min_value_idx {
let byte = unsafe { freq_buf.get_unchecked_mut(idx as usize) };
*byte = 0;
}
match (min_value_idx, min_value) {
(Some(idx), Some(value)) => Some((idx, value)),
_ => None,
}
}Step 3 — Encode the Huffman tre
Since we now have a buffer representing the Huffman tree, we can now build the encodings into a HashMap. The HashMap will be useful to us when we come to serializing the data. First, we define an object that stores information of the Encoding:
#[derive(Debug, PartialEq, Eq)]
pub struct Encoded {
bits: BitVec<u8, Msb0>,
/// Number of bits in the sequence
num_bits_sequence: u8,
value: u8,
}We use a BitVec structure to store the raw encodings from the bitvec crate. It makes it a lot simpler to perform bitwise manipulation of contiguous memory. The Encoded structure also stores the number of bits in the sequence and value represented by the encoding. This is then mapped to the value.
pub fn encode_huffman_array(huffman_array: &[u8]) -> HashMap<u8, Encoded> {
huffman_array
.iter()
.enumerate()
.map(|(idx, value)| {
if idx == huffman_array.len() - 1 {
let bv: BitVec<u8, Msb0> = (0..idx as u8).map(|_| false).collect();
let num_bits_sequence = bv.len() as u8;
return (
*value,
Encoded {
bits: bv,
num_bits_sequence,
value: *value,
},
);
}
let bv: BitVec<u8, Msb0> = (0..idx as u8 + 1)
.map(|i| {
if i == idx as u8 {
return true;
}
false
})
.collect();
let num_bits_sequence = bv.len() as u8;
(
*value,
Encoded {
bits: bv,
num_bits_sequence,
value: *value,
},
)
})
.collect()
}Step 4 — Serialization
Now we have a structure representing the bits; it’s time to think about how to serialize the data. Below is a graphic of how it can be represented.
The first 64 bits are reserved for the total number of bits in the encoding. The next 64 bits are the length of the header. Encoded values make up 3 bytes and are in sequence of each other. The first byte is the value, the next byte is the number of bits, then the last byte is whether or not the encoding ends in a 1. After all the values are added, the encoded bits are appended at the end.
Get BWinter’s stories in your inbox
Join Medium for free to get updates from this writer.
Below is the serialization code:
fn u64_to_u8(value: u64) -> [u8; 8] {
[
(value >> 56) as u8,
(value >> 48) as u8,
(value >> 40) as u8,
(value >> 32) as u8,
(value >> 24) as u8,
(value >> 16) as u8,
(value >> 8) as u8,
value as u8,
]
}
pub fn serialize_huffman(
encoded_map: &HashMap<u8, Encoded>,
bit_buffer: Vec<u8>,
total_bits: u64,
) -> Vec<u8> {
let mut serialized_buffer = u64_to_u8(total_bits).to_vec();
let mut tmp_buffer = Vec::new();
for encoded in encoded_map.values() {
tmp_buffer.push(encoded.value);
tmp_buffer.push(encoded.num_bits_sequence);
tmp_buffer.push(*encoded.bits.last().unwrap() as u8);
}
let size_of_header_bytes = tmp_buffer.len() as u64;
let size_of_header_arr = u64_to_u8(size_of_header_bytes);
serialized_buffer.extend_from_slice(&size_of_header_arr);
serialized_buffer.extend(tmp_buffer);
serialized_buffer.extend(bit_buffer);
serialized_buffer
}Now we have a serialized buffer; we are essentially done with the encoding and compression part of the algorithm.
Decompression
We have to be able to reconstruct the original array. I will not go into much detail on how it is done since it is just using the headers of the serialization to get to the original buffer. Below is the deserialization code:
pub fn deserialize_huffman(huff_bytes: &[u8]) -> Vec<u8> {
let total_bits = u8_to_u64(&huff_bytes[0..8]);
let header_end_byte = 16;
let header_num_bytes = u8_to_u64(&huff_bytes[8..header_end_byte]);
let mut map_values = HashMap::new();
let mut idx = header_end_byte;
let mut max_bits = 0;
while idx - header_end_byte < header_num_bytes as usize {
let value = huff_bytes[idx];
let encoding_number_of_bits = huff_bytes[idx + 1];
let ends_in_1 = huff_bytes[idx + 2] != 0;
max_bits = max_bits.max(encoding_number_of_bits);
let value_bit_map = ValueBitMap { value, ends_in_1 };
map_values
.entry(encoding_number_of_bits)
.and_modify(|v: &mut Vec<ValueBitMap>| v.push(value_bit_map))
.or_insert(vec![value_bit_map]);
idx += 3
}
let mut decoded_buffer: Vec<u8> = Vec::new();
let bit_vec: BitVec<u8, Msb0> = BitVec::from_slice(&huff_bytes[idx..]);
let mut bit_vec_iter = bit_vec.iter();
let mut bits_to_target = 0;
let mut read_bits = 0;
while read_bits < total_bits {
let bit = bit_vec_iter.next().unwrap();
if *bit {
bits_to_target += 1;
// Here I need to do logic to find the number of bits
let value_bit_map = map_values.get(&bits_to_target).unwrap();
decoded_buffer.push(value_bit_map.iter().find(|v| v.ends_in_1).unwrap().value);
read_bits += bits_to_target as u64;
bits_to_target = 0;
} else {
bits_to_target += 1;
if bits_to_target >= max_bits {
// We hit the least occurring character, now we need to find it
let value_bit_map = map_values.get(&bits_to_target).unwrap();
decoded_buffer.push(value_bit_map.iter().find(|v| !v.ends_in_1).unwrap().value);
read_bits += bits_to_target as u64;
bits_to_target = 0
}
}
}
decoded_buffer
}Testing the compression
Speaking to a friend, he suggested a good candidate would be DNA sequences since they only contain 4 unique letters. The data is an extended version of what can be found at tests/resources/dna_seq_test.txt in the repo. I used huffc to perform the compression; the command was huffc -c -i dna_seq_test.txt.
3.9M dna_seq_test.txt
1.1M dna_seq_test.txt.huffThe file ending in huff is the compressed file. We can see that the DNA sequence file was compressed from 3.9 megabytes to 1.1 megabytes. That's a compression ratio of 3.55.
Limitations
So we’ve seen how Huffman compression works, and how useful it can be in an ideal scenario, at least a byte-by-byte implementation. However, the compression falls short and generally makes the files larger when you have a wide array of bytes that all have similar frequency of occurrence. This is a known problem and can be tackled in a variety of ways. Below is a list of possible techniques in order to tackle this limitation.
- Group bytes together, so instead of encoding on an 8-bit basis, try 16-bit, 32-bit, or 64-bit.
- Encode based off patterns, such as differences in the bytes instead.
Wrapping up
Thank you for your time reading this article! This project was a lot of fun; I learned a lot doing it, and I hope you learned something reading it.
Please check out my blog for other Rust and tech-related blogs :)
