Prague Stringology Conference 2014
Szymon Grabowski and Marcin Raniszewski
Two Simple Full-Text Indexes Based on the Suffix Array
| Abstract: |
| We propose two suffix array inspired full-text indexes. One, called SA-hash, augments the suffix array with a hash table to speed up pattern searches due to significantly narrowed search interval before the binary search phase. The other, called FBCSA, is a compact data structure, similar to Mäkinen's compact suffix array, but working on fixed sized blocks, which allows to arrange the data in multiples of 32 bits, beneficial for CPU access. Experimental results on the Pizza & Chili 200 MB datasets show that SA-hash is about 2.5-3 times faster in pattern searches (counts) than the standard suffix array, for the price of requiring 0.3n-2.0n bytes of extra space, where n is the text length, and setting a minimum pattern length. The latter limitation can be removed for the price of even more extra space. FBCSA is relatively fast in single cell accesses (a few times faster than related indexes at about the same or better compression), but not competitive if many consecutive cells are to be extracted. Still, for the task of extracting e.g. 10 successive cells its time-space relation remains attractive. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |