In: Computing and Informatics, vol. 38, no. 3
T.m. Kowalski - S. Grabowski - K. Fredriksson
Detaily:
Rok, strany: 2020, 555 - 574
Jazyk: eng
Kľúčové slová:
Suffix array, data structures, text indexes, hashing
O článku:
The suffix array is a classic full-text index, combining effectiveness with simplicity. We discuss three approaches aiming to improve its efficiency even more: changes to the navigation, data layout and adding extra data. In short, we show that i) the way how we search for the right interval boundary impacts significantly the overall search speed, ii) a B-tree data layout easily wins over the standard one, iii) the well-known idea of a lookup table for the prefixes of the suffixes can be refined with using compression, iv) caching prefixes of the suffixes in a helper array can pose another practical space-time tradeoff.
Ako citovať:
ISO 690:
Kowalski, T., Grabowski, S., Fredriksson, K. 2020. Suffix Arrays with a Twist. In Computing and Informatics, vol. 38, no.3, pp. 555-574. 1335-9150. DOI: https://doi.org/10.31577/cai_2019_3_555
APA:
Kowalski, T., Grabowski, S., Fredriksson, K. (2020). Suffix Arrays with a Twist. Computing and Informatics, 38(3), 555-574. 1335-9150. DOI: https://doi.org/10.31577/cai_2019_3_555
O vydaní:
Vydavateľ: Ústav informatiky SAV
Publikované: 9. 3. 2020