#saca #suffix #search #index


Partitioned suffix arrays, for use with sacabase

1 stable release

2.0.0 Nov 23, 2019

#6 in #suffix

Download history 954/week @ 2022-12-01 702/week @ 2022-12-08 456/week @ 2022-12-15 285/week @ 2022-12-22 366/week @ 2022-12-29 732/week @ 2023-01-05 985/week @ 2023-01-12 930/week @ 2023-01-19 1227/week @ 2023-01-26 1033/week @ 2023-02-02 844/week @ 2023-02-09 650/week @ 2023-02-16 632/week @ 2023-02-23 538/week @ 2023-03-02 420/week @ 2023-03-09 553/week @ 2023-03-16

2,327 downloads per month
Used in 3 crates (2 directly)

MIT license

287 lines


Computing the suffix array (the lexicographic order of all suffixes of a text) is expensive, especially as the text gets large.

Sometimes, for very large inputs, a compromise is possible. Instead of computing the suffix array of the whole text, we can compute the suffix array of the first half, and the suffix array of the second half.

Memory usage remains roughly the same (depending on the SACA used), lookup time gets worse by a constant factor (the number of partitions), and, across partitions boundaries, worse (shorter) matches are sometimes found.

For some applications, like diffing very large files, this compromise makes sense. Read the docs and the tests to see if sacapart is right for you.

Note: sacapart is meant to be used in conjuction with a SACA that supports sacabase, like divsufsort.


~30K SLoC