Huffman Encoding/Decoding

Related tags

Compression huffman-tree huffman-compression-algorithm
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
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

image-rs 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

Cliff L. Biffle 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.

Shengqiu Li 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.

Charlie Moog 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

Niklas Sauter 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

Stelar Labs 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

Du Toit 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

StreamingFast 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

Jad Ghalayini 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

Chris Rogus 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

null 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

Databento, Inc. 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

Philip Deljanov 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

xiaozhuai, Weihang Ding 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

duoxehyon 11 Apr 23, 2023
A tool for quickly collecting function selectors and decoding signatures from on-chain EVM bytecode.
A tool for quickly collecting function selectors and decoding signatures from on-chain EVM bytecode.

Overview | Disclaimer | Tests | Installation | Usage | Examples | Aknowledgements | License Overview Sigmund provides a CLI that allows users to colle

wavefnx 46 Jul 22, 2024
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

null 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

Arjan Topolovec 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

Henri Sivonen 284 Dec 13, 2022
Owner
Chaoqi LIU
26' UIUC Math and Computer Science
Chaoqi LIU
GitHub
Basic (and naïve) LZW and Huffman compression algorithms in Rust.

Naive implementation of the LZW and Huffman compression algorithms. To run, install the Rust toolchain. Cargo may be used to compile the source. Examp

Luiz Felipe Gonçalves 9 May 22, 2023
Encoding and decoding support for BSON in Rust

bson-rs Encoding and decoding support for BSON in Rust Index Overview of BSON Format Usage BSON Values BSON Documents Modeling BSON with strongly type

mongodb 304 Dec 30, 2022
A TOML encoding/decoding library for Rust

toml-rs A TOML decoder and encoder for Rust. This library is currently compliant with the v0.5.0 version of TOML. This library will also likely contin

Alex Crichton 1k Dec 30, 2022
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

image-rs 3.5k Jan 9, 2023
Google Encoded Polyline encoding & decoding in Rust.

polyline Google Encoded Polyline encoding & decoding in Rust. A Note on Coordinate Order This crate uses Coordinate and LineString types from the geo-

GeoRust 14 Dec 11, 2022
TIFF decoding and encoding library in pure Rust

image-tiff TIFF decoding and encoding library in pure Rust Supported Features Baseline spec (other than formats and tags listed below as not supported

image-rs 66 Dec 30, 2022
Serde support for encoding/decoding rusty_v8 values

Serde support for encoding/decoding rusty_v8 values

Deno Land 34 Nov 28, 2022
PNG decoding and encoding library in pure Rust

PNG Decoder/Encoder PNG decoder/encoder in pure Rust. It contains all features required to handle the entirety of the PngSuite by Willem van Schack. p

image-rs 247 Dec 25, 2022
CBOR (binary JSON) for Rust with automatic type based decoding and encoding.

THIS PROJECT IS UNMAINTAINED. USE serde_cbor INSTEAD. This crate provides an implementation of RFC 7049, which specifies Concise Binary Object Represe

Andrew Gallant 121 Dec 27, 2022
A wav encoding and decoding library in Rust

Hound A wav encoding and decoding library in Rust. Hound can read and write the WAVE audio format, an ubiquitous format for raw, uncompressed audio. T

Ruud van Asseldonk 345 Dec 27, 2022