Suffix Array Vs. Compressed Suffix Array Vs. Bwt Search
0
7
Entering edit mode
10.4 years ago
Rob 6.7k

Hi all,

I was wondering if there is a good reference on what the (practically) fastest data structure for exact sequence search is. Specifically, I'm curious about the speed of finding all occurrences (exactly) of a string in a large corpus using backward search in a BWT versus search in a (presumably uncompressed) suffix array. I understand that they can both be performed asymptotically in O(m), where m is the length of the pattern string, with both structures. However, I'm curious if there are significant practical differences in the search speed. Any references or benchmarks would be greatly appreciated.

Thanks,

Rob

search alignment • 2.9k views
ADD COMMENT

Login before adding your answer.

Traffic: 2219 users visited in the last hour
Help About
FAQ
Access RSS
API
Stats

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6