search

IlyaGrebnov / libsais

libsais is a library for linear time suffix array, longest common prefix array and burrows wheeler transform construction based on induced sorting algorithm.
Apache License 2.0
180 stars 22 forks source link

Is SA-IS means using induce sort for suffix array? yuta mori has Open source code of SA-IS #2

Closed Daisy-gj closed 2 years ago

Daisy-gj commented 3 years ago

yuta mori's code:https://github.com/y-256/libdivsufsort/ , I've test his code, the biggest disadvantages is 5 times in-memory usage.

IlyaGrebnov commented 3 years ago

Yes, libsais is based on induced sorting SA-IS algorithm. Yuta Mori implementation for this algorithm could be found here .

Note, libdivsufsort you quoted above is not based on SA-IS algorithm. You could find description of algorithm here and it only need O(1) bytes of additional memory (256KB to be exact) which is optimal for this class of algorithms which do not use external memory.

Daisy-gj commented 3 years ago

Yes, libsais is based on induced sorting SA-IS algorithm. Yuta Mori implementation for this algorithm could be found here .

Note, libdivsufsort you quoted above is not based on SA-IS algorithm. You could find description of algorithm here and it only need O(1) bytes of additional memory (256KB to be exact) which is optimal for this class of algorithms which do not use external memory.

Thanks! I will read this paper.