Huffman Encoding/Decoding

Last update: Dec 24, 2022

Overview

Huffman Encoding/Decoding

This project is inspired by lab_huffman of CS225(2022fall) @ UIUC

Team:
-- Chaoqi LIU ([email protected])
-- Jiahui LIN ([email protected])

Background Information

In 1951, while enrolled in an Information Theory class at MIT, David A. Huffman and his classmates were given a choice by professor Robert M. Fano: they could either take the final exam or find the most efficient binary code. Huffman chose the less traveled path, and the rest, as they say, is history.

The Huffman encoding algorithm is a fundamental data compression algorithm. Data compression is a powerful tool that allows a given set of information to be represented in less space, allowing for more efficient data transfer. JPG (lossy) and PNG image formats use various types of compression (lossless). It is also used to compress multiple files in ZIP files. Communication Networks, which deal with transferring large amounts of data, and Computer Security, which deals with data encoding for a layer of privacy, both use the concept of data encoding.

Huffman coding

Huffman Tree Visualization

Huffman tree built from the text "The Huffman encoding algorithm is a fundamental data compression algorithm" was shown below

                                                                                                ______________________________ 74 _____________________________                                                                                                  
                                                                 ______________________________/                                                               \______________________________                                                                   
                                                ______________ 31 _____________                                                                                                ______________ 43 _____________                                                   
                                 ______________/                               \______________                                                                  ______________/                               \______________                                    
                        ______ 14 _____                                                ______ 17 _____                                                 ______ 20 _____                                                ______ 23 _____                            
                 ______/               \______                                  ______/               \______                                   ______/               \______                                  ______/               \______                     
            __ 6 __                          a:8                           __ 8 __                          _:9                            __ 10 _                        __ 10 _                         __ 11 _                        __ 12 _                 
         __/       \__                                                  __/       \__                                                   __/       \__                  __/       \__                   __/       \__                  __/       \__              
      l:3            d:3                                             h:4            e:4                                               5             t:5             m:5            o:5              i:5             6              n:6             6             
                                                                                                                                    /   \                                                                         /   \                          /   \           
                                                                                                                                 c:2    f:3                                                                    g:3     3                      r:3    s:3         
                                                                                                                                                                                                                      / \                                        
                                                                                                                                                                                                                    p:1u:2

You might also like...

Encoding and decoding images in Rust

Image Maintainers: @HeroicKatora, @fintelia How to contribute An Image Processing Library This crate provides basic image processing functions and met

3.5k Jan 2, 2023

corncobs: Corny COBS encoding/decoding in Rust

corncobs: Corny COBS encoding/decoding in Rust This crate provides Consistent Overhead Byte Stuffing (COBS) support for Rust programs, with a particul

9 Jun 20, 2022

A library for decoding and encoding DirectDraw Surface files

A library for decoding and encoding DirectDraw Surface files. Currently handles decoding some uncompressed DX9 formats, as well as DXT1-5. Supports encoding in the A8R8G8B8 format. Support for cubemaps and volumes, as well as DX10 is planned.

1 Feb 18, 2022

A small command-line utility for encoding and decoding bech32 strings

A small command-line utility for encoding and decoding bech32 strings.

5 Dec 26, 2022

Derive macro for encoding/decoding instructions and operands as bytecode

bytecoding Derive macro for encoding and decoding instructions and operands as bytecode. Documentation License Licensed under either of Apache License

15 Mar 20, 2022

Astro Format is a library for efficiently encoding and decoding a set of bytes into a single buffer format.

Astro Format is a library for efficiently transcoding arrays into a single buffer and native rust types into strings

1 Aug 13, 2022

A rust bencode encoding/decoding implementation backed by serde.

Bende A rust bencode encoding/decoding implementation backed by serde. About This is one of a few bencode implementations available for rust. Though t

3 Dec 4, 2022

Substreams development kit for Ethereum chains, contains Firehose Block model and helpers as well as utilities for Ethereum ABI encoding/decoding.

Substreams Ethereum Substreams development kit for Ethereum chains, contains Rust Firehose Block model and helpers as well as utilities for Ethereum A

15 Oct 25, 2022

Zero-copy, no-std proquint encoding and decoding

proqnt A pronounceable quintuplet, or proquint, is a pronounceable 5-letter string encoding a unique 16-bit integer. Proquints may be used to encode b

11 May 9, 2023

Base 32 + 64 encoding and decoding identifiers + bytes in rust, quickly

fast32 Base32 and base64 encoding in Rust. Primarily for integer (u64, u128) and UUID identifiers (behind feature uuid), as well as arbitrary byte arr

9 Dec 18, 2023

A tool to deserialize data from an input encoding, transform it and serialize it back into an output encoding.

dts A simple tool to deserialize data from an input encoding, transform it and serialize it back into an output encoding. Requires rust = 1.56.0. Ins

11 Dec 14, 2022

Databento Binary Encoding (DBZ) - Fast message encoding and storage format for market data

dbz A library (dbz-lib) and CLI tool (dbz-cli) for working with Databento Binary Encoding (DBZ) files. Python bindings for dbz-lib are provided in the

15 Nov 4, 2022

Symphonia is a pure Rust audio decoding and media demuxing library supporting AAC, FLAC, MP3, MP4, OGG, Vorbis, and WAV.

Pure Rust multimedia format demuxing, tag reading, and audio decoding library

1k Jan 2, 2023

Rust library to get image size and format without loading/decoding

imageinfo-rs Rust library to get image size and format without loading/decoding. The imageinfo don't get image format by file ext name, but infer by f

47 Dec 30, 2022

Pure Rust implementation of Arbitrum sequencer feed reader with built-in transaction decoding and MEV features

Sequencer-Client (WIP 🚧 ) Pure Rust implementation of Arbitrum sequencer feed reader with built-in transaction decoding and MEV features Design Goal

11 Apr 23, 2023

I/O and binary data encoding for Rust

nue A collection of tools for working with binary data and POD structs in Rust. pod is an approach at building a safe interface for transmuting POD st

38 Nov 9, 2022

Implementation of Bencode encoding written in rust

Rust Bencode Implementation of Bencode encoding written in rust. Project Status Not in active developement due to lack of time and other priorities. I

32 Aug 6, 2022

A Gecko-oriented implementation of the Encoding Standard in Rust

encoding_rs encoding_rs an implementation of the (non-JavaScript parts of) the Encoding Standard written in Rust and used in Gecko (starting with Fire

284 Dec 13, 2022

Character encoding support for Rust

Encoding 0.3.0-dev Character encoding support for Rust. (also known as rust-encoding) It is based on WHATWG Encoding Standard, and also provides an ad