Comparison w/ `suffix` crate

[hucsmn]

Comparison w/ `suffix` crate

[hucsmn]

The motivation of this crate is to quickly sort suffix array of binary data in memory and use as less memory as possible. However, burntsushi's suffix is for indexing utf-8 encoded text. Since utf-8 is a variable width encoding, performances of these two crates were not that comparable.

I was woking on implementing a better bsdiff months before, which quite need a mordern suffix array construction algorithm. Util I started this work, there was no such rust crate that could meet my requisitions (for now, there is divsufsort ported by Amos Wenger, which is more recommended).
Therefore, I implemented a partially paralleled SACA, which uses O(1) additional memory and runs in O(n) time (qsufsort in Colin Percival's original bsdiff 4.3 is O(n) additional memory & O(n*log(n)) worst time).

AFAIK, speed of this crate is usually 1.3x-1.7x faster than burntsushi's suffix, but 2x-3x slower than Yuta Mori's dissufsort in C and Amos Wenger's hand-ported divsufsort in rust. The testing code and result was listed here. For people who launches new projects relating to binary data indexing, the new rust-bindings for divsufsort by Amos Wenger is preferred.

I am planned to try another implementation of SACA, or just simply replace the current implementation with Amos Wenger's work in later versions. I would like to add some explainations to README.

TL;DR: suffix_array runs faster than burntsushi's suffix. But it is not suitable to compare them in this way, because suffix handles utf-8 input while suffix_array does not. For people who need indexing utf-8 encoded texts, it is recommend to use burntsushi's suffix.

[Shnatsel]

Thanks! It would be great to put the TL;DR in the README.