Module bwt 

BWT (Burrows-Wheeler Transform) forward and backward transformation. Requires bwt feature, enabled by default

This module contains a bruteforce implementation of BWT encoding in Rust as well as standard decoding. These are exposed as a standard Reader and Writer interfaces wrapping an underlying stream.

BWT output stream places together symbols with similar leading contexts. This reshaping of the entropy allows further stages to deal with repeated sequences of symbols for better compression.

Typical compression schemes are: BWT + RLE (+ EC) RLE + BWT + MTF + RLE + EC : bzip2 BWT + DC + EC : ybs

Where the stage families are: BWT: BWT (Burrows-Wheeler Transform), ST (Shindler transform) RLE: RLE (Run-Length Encoding) MTF: MTF (Move-To-Front), WFC (Weighted Frequency Coding) DC: DC (Distance Coding), IF (Inverse Frequencies) EC (Entropy Coder): Huffman, Arithmetic, RC (Range Coder)

Example

use std::io::{BufWriter, BufReader, Read, Write};
use compress::bwt;

// Encode some text
let text = "some text";
let mut e = bwt::Encoder::new(BufWriter::new(Vec::new()), 4 << 20);
e.write(text.as_bytes()).unwrap();
let (encoded, _) = e.finish();
let inner = encoded.into_inner().unwrap();

// Decode the encoded text
let mut d = bwt::Decoder::new(BufReader::new(&inner[..]), true);
let mut decoded = Vec::new();
d.read_to_end(&mut decoded).unwrap();

assert_eq!(&decoded[..], text.as_bytes());

Credit

This is an original (mostly trivial) implementation.

Modules

dc

DC (Distance Coding) forward and backward transformation. Designed to be used on BWT block output for compression.

mtf

MTF (Move To Front) encoder/decoder Produces a rank for each input character based on when it was seen last time. Useful for BWT output encoding, which produces a lot of zeroes and low ranks.

Structs

Decoder

This structure is used to decode a stream of BWT blocks. This wraps an internal reader which is read from when this decoder’s read method is called.

Encoder

This structure is used to compress a stream of bytes using the BWT. This is a wrapper around an internal writer which bytes will be written to.

InverseIterator

An iterator over inverse BWT Run time: O(N), memory: N words (table)

Radix

Radix sorting primitive

TransformIterator

An iterator over BWT output

Constants

ALPHABET_SIZE

Functions

compute_inversion_table

Compute an inversion jump table, needed for BWT decoding

compute_suffixes

Compute a suffix array from a given input string Resulting suffixes are guaranteed to be alphabetically sorted Run time: O(N^3), memory: N words (suf_array) + ALPHABET_SIZE words (Radix)

decode

Decode a BWT block, given it’s origin, and using ‘table’ temporarily

decode_simple

A simplified BWT decode function, which allocates a temporary suffix array

encode

Encode BWT of a given input, using the ‘suf_array’

encode_simple

Transform an input block into the output slice, all-inclusive version. Returns the index of the original string in the output matrix.

Type Aliases

Symbol

A base element for the transformation