Crate small_bwt 

BWT construction in small space

Implementation of the BWT construction algorithm in small space, described in Algorithm 11.8 of the book: Compact Data Structures - A Practical Approach, Gonzalo Navarro, 2016.

Given a typical text, it runs in O(n log n loglog n) time and O(n) additional bits of space, where n is the length of the input string and the alphabet size is much smaller than n. See the book for more details.

Basic usage

BwtBuilder provides a simple interface to build the BWT. It inputs a byte slice and outputs the BWT to a write stream.

use small_bwt::BwtBuilder;

// The text must end with a smallest terminal character.
let text = "abracadabra$";

// Build the BWT.
let mut bwt = vec![];
BwtBuilder::new(text.as_bytes())?.build(&mut bwt)?;
let bwt_str = String::from_utf8_lossy(&bwt);
assert_eq!(bwt_str, "ard$rcaaaabb");

Structs

BwtBuilder

BWT builder in small space.

Functions

decode_bwt

Decodes the original text from a given BWT.

verify_terminator

Verifies that the smallest character appears only at the end of the text.