String algorithm visualizations

This is a small app to visualize some string algorithms.

Usage

As an interactive webapp, see this blog post

This is done by compiling the rust code to webassembly with a small javascript wrapper for event handling.

As a Rust application

1. Install Rust: https://rustup.rs/
2. Clone the repository and install the SDL2 and SDL2_TTF dependencies if needed.
3. Run the code with the default bin feature as:

   cargo run -- <suffix-array|bwt|bi-bwt> [string] [--query <query>] [--save dir]
           

   arguments in [] are optional.

   • The --save option can be used to save each frame as a .bmp.

Keyboard controls

Both the webapp and binary support the following keyboard commands:

• → / SPACE: next frame
• ← / BACKSPACE: previous frame
• p / RETURN: play/pause
• ↑ / + / f: faster
• ↓ / - / s: slower

Algorithms

Ko-Aluru linear time suffix array construction (suffix-array)

First, it visualizes the extension step of the Ko-Aluru linear-time suffix array construction algorithm: Assuming the small suffixes are already sorted and put and the end of their first-character buckets, this shows how the remaining large suffixes are put into their places.

See this blogpost for more context.

Burrows–Wheeler transform & FM Index (bwt)

The second visualization is of the BWT and FM index.

• First the rotations are listed and sorted.
• Then the last-to-first correspondence is shown.
• Then character counts and the occurrences array are computed.
• Lastly, it’s shown how to compute the range starting with a given query.

Bidirectional Burrows-Wheeler transform (bi-bwt)

Lastly, you can visualize the bidirectional burrows wheeler transform.

This starts in the middle of a query and then first extends to the left, and then extends to the right.

Animations

To turn a set of bmp images into a gif, use:

ffmpeg -y -framerate 1 -i %d.bmp -filter_complex "split[s0][s1];[s0]palettegen=max_colors=64[p];[s1][p]paletteuse=dither=bayer",fps=1 suffix-array.gif