csa_wt construction without suffix array samples #131
Description
The compressed suffix array construction algorithm apparently uses divsufsort to produce the suffix array of the input text, from which the BWT in then generated. In case suffix array samples are not needed, this step can take quite a lot of time and disk space. The amount of wall clock time required increases further due to the fact that (if I remember correctly) a buffered integer vector is used to read the input in chunks.
Options to skip the suffix array construction include (from the top of my head):
- Adding a function that constructs the CSA without the suffix array samples (controlled e.g. by
t_sa_sample_strat) - Using a Wavelet tree directly instead of the CSA. Some of the existing functionality (such as the C array) would have to be re-implemented. Similarly a new construction function may be needed
- Extending the approach outlined in suffix array/ bwt construction algorithms other than libdivsufsort #27.
Any comments on the matter? I’m not yet sure if I have time to implement any of these but if it turns out so, I’d like to avoid coming up with a completely new API if something already exists.