2 unstable releases

0.7.12 Feb 27, 2025
0.7.6 Jan 29, 2025
0.5.1 Nov 26, 2024

#249 in Algorithms

Download history 216/week @ 2024-12-01 155/week @ 2024-12-08 29/week @ 2024-12-15 1/week @ 2024-12-29 328/week @ 2025-01-05 252/week @ 2025-01-12 18/week @ 2025-01-19 718/week @ 2025-01-26 159/week @ 2025-02-02 11/week @ 2025-02-09 139/week @ 2025-02-16 725/week @ 2025-02-23 294/week @ 2025-03-02 76/week @ 2025-03-09 4/week @ 2025-03-16

1,106 downloads per month
Used in 2 crates

BSD-3-Clause

190KB
3K SLoC

Parallel Construction of Suffix Arrays in Rust

See https://docs.rs/libsufr/latest/libsufr/ for API documentation.

This is a Rust library crate for creating suffix arrays.

The basic ideas are as follow:

  • Read the input file as u8 (unsigned 8-bit integer values).
  • Select the suffixes, which are normally 0 to the length of the text but there is the option to skip suffixes that don't start with A/C/G/T if the input is DNA. Note: Following the C++ implementation, we use 32-bit integers if the input text length is less than 2^32 and 64-bit integers, otherwise.
  • Create partitions by randomly choosing suffixes and copying the suffixes to the highest possible partition bounded by any pivot.
  • Sort the partitions in parallel.
  • Merge the partitions. Because the values fall into nonoverlapping ranges, these subarrays can be appended in order to produce the final SA.
  • Produce a binary-encoded output file with the suffix/LCP arrays and other metadata.

Some advantages to this algorithm:

  • The various partitioned subarrays can be processed independently by separate threads, and no thread will ever have to merge the entire input.
  • Suffix comparisons are made faster by caching LCPs.
  • Using u8 for the input text and 32-bits (when possible) for SA/LCP results in lower memory usage.

See the repository for documentation: https://github.com/TravisWheelerLab/sufr

See Also

Use cargo install sufr for a CLI.

Authors

Dependencies

~9–19MB
~273K SLoC