Lib.rs

› Algorithms
#suffix #search #search-index #array-index #saca #index #text-search

divsufsort

Rust port of Yuta Mori's divsufsort

by Amos Wenger

4 stable releases

2.0.0 Nov 23, 2019
1.0.2 Nov 17, 2019
1.0.0 Nov 16, 2019

#1974 in Algorithms

Download history 378/week @ 2024-07-22 402/week @ 2024-07-29 340/week @ 2024-08-05 354/week @ 2024-08-12 428/week @ 2024-08-19 550/week @ 2024-08-26 598/week @ 2024-09-02 813/week @ 2024-09-09 665/week @ 2024-09-16 805/week @ 2024-09-23 628/week @ 2024-09-30 791/week @ 2024-10-07 712/week @ 2024-10-14 865/week @ 2024-10-21 800/week @ 2024-10-28 872/week @ 2024-11-04

3,258 downloads per month
Used in 6 crates (5 directly)

MIT license

425KB
3.5K SLoC

divsufsort

This crate contains a Rust handmade port of Yuta Mori's libdivsufsort, as found on:

Changes

The main changes from the C codebase are as follows.

Instead of passing pointers to T (the original text) and SA (the suffix array), slices and indices are passed instead. This sometimes involves adding more parameters to functions (like tr_heapsort).

Some macros (for stacks, used in sssort and trsort) have been replaced with proper Rust types. The SAPtr type is used to represent an index into SA. A/B/B* access has also been translated from C macros to Rust (inlined) functions.

Cross-checking is only built when the crosscheck feature is enabled. It is not intended for general use, only for debugging the divsufsort crate.

Authors

The original C code was written by Yuta Mori.

The port was done by hand, by Amos Wenger.

License

divsufsort is released under the MIT license, same as the original.

See the LICENSE file for details.

Dependencies