<p>I am working on an efficient pattern-matching algorithm (using binary files as input) based on suffix arrays. I would like to ask you If you are familiar with any suffix array construction algorithm (SACA) except the one that was presented in the original paper. So far I have found quite a few: BPR2, DC3 RadixSA etc, however, as their source is not publicly available I do not want to implement them all and benchmark them afterward. Do you have any experience and which of them would you suggest if the operation time is critical? Additionally, I have found out that sometimes suboptimal algorithms (e.g. O(nlogn)) can work better in real-life scenarios than other counterparts which may have better asymptotic complexity( e.g. O(n)). Is this due to hidden constants that may dramatically increase the operation time of the latter algorithms? Does the poor locality that may come with these optimal algorithms also result to bad caching also affecting their performance? Thank you!</p>

CC BY-SA 4.0
2021-01-05T13:17:35.623Z
The construction of suffix arrays is so important in practice that there certainly exists experimental research on it. One reference I found is https://researchrepository.murdoch.edu.au/id/eprint/27921/1/linear_time_suffix.pdf and I think its quite easy to use Google Scholar to find more.
Laakeri
CC BY-SA 4.0
2021-01-08T18:46:01.133Z
Golang ships with suffix array implementation [1]. You can try and see if it works for you. It should be pretty good since has optimizations [2] inspired by this [3]. Afair [3] was the best last time I checked a long time ago. 

[1] https://golang.org/pkg/index/suffixarray/
[2] https://golang.org/src/index/suffixarray/sais.go
[3] https://sites.google.com/site/yuta256/sais
Pratik Deoghare
<string-search>
Suffix array construction algorithms (SACAs)
konstantinosAR
# Suffix array construction algorithms (SACAs)

(Asked by: username_0 on 2021-01-04)

I am working on an efficient pattern-matching algorithm (using binary files as input) based on suffix arrays. I would like to ask you If you are familiar with any suffix array construction algorithm (SACA) except the one that was presented in the original paper. So far I have found quite a few: BPR2, DC3 RadixSA etc, however, as their source is not publicly available I do not want to implement them all and benchmark them afterward. Do you have any experience and which of them would you suggest if the operation time is critical? Additionally, I have found out that sometimes suboptimal algorithms (e.g. O(nlogn)) can work better in real-life scenarios than other counterparts which may have better asymptotic complexity( e.g. O(n)). Is this due to hidden constants that may dramatically increase the operation time of the latter algorithms? Does the poor locality that may come with these optimal algorithms also result to bad caching also affecting their performance? Thank you!

**Tags:** string-search
> **Comments:**
> **username_1**: The construction of suffix arrays is so important in practice that there certainly exists experimental research on it. One reference I found is https://researchrepository.murdoch.edu.au/id/eprint/27921/1/linear_time_suffix.pdf and I think its quite easy to use Google Scholar to find more.  
> **username_2**: Golang ships with suffix array implementation [1]. You can try and see if it works for you. It should be pretty good since has optimizations [2] inspired by this [3]. Afair [3] was the best last time I checked a long time ago.   [1] https://golang.org/pkg/index/suffixarray/ [2] https://golang.org/src/index/suffixarray/sais.go [3] https://sites.google.com/site/yuta256/sais  

---

## 0 answers

