Suffix Array Construction
- PDF / 195,213 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 115 Downloads / 238 Views
beled trees compression techniques which achieve the entropy of the indexed data, are covered in more detail in the entries cited in Tree Compression and Indexing. Cross References Compressed Suffix Array Compressed Text Indexing Rank and Select Operations on Binary Strings Text Indexing Recommended Reading 1. Barbay, J., Golynski, A., Munro, J.I., Rao, S.S.: Adaptive searching in succinctly encoded binary relations and tree-structured documents. In: Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science (LNCS), vol. 4009, pp. 24–35. Springer, Berlin (2006) 2. Barbay, J., He, M., Munro, J.I., Rao, S.S.: Succinct indexes for strings, binary relations and multi-labeled trees. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 680–689. ACM, SIAM (2007) 3. Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. In: Proceedings of the 18th ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 690–695. ACM, SIAM (2007) 4. Golynski, A., Munro, J.I., Rao, S.S.: Rank/select operations on large alphabets: a tool for text indexing. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 368–373. ACM, SIAM (2006) 5. Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 549–554 (1989) 6. Jansson, J., Sadakane, K., Sung, W.-K.: Ultra-succinct representation of ordered trees. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 575–584. ACM, SIAM (2007) 7. Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science (LNCS), vol. 2719, pp. 345–356. Springer, Berlin (2003) 8. Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31, 762–776 (2001) 9. Munro, J.I., Rao, S.S.: Succinct representations of functions. In: Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science (LNCS), vol. 3142, pp. 1006–1015. Springer, Berlin (2004)
Suffix Array Construction 2006; Kärkkäinen, Sanders, Burkhardt JUHA KÄRKKÄINEN Department of Computer Science, University of Helsinki, Helsinki, Finland
S
Keywords and Synonyms Suffix sorting; Full-text index construction Problem Definition The suffix array [5,14] is the lexicographically sorted array of all the suffixes of a string. It is a popular text index structure with many applications. The subject of this entry are algorithms that construct the suffix array. More precisely, the input to a suffix array construction algorithm is a text string T = T[0; n) = t0 t1 t n1 , i. e., a sequence of n characters from an alphabet ˙ . For i 2 [0; n], let Si denote the suffix T[i; n) = t i t i+1 t n1 . The output is the suffix array SA[0; n] of T, a p
Data Loading...
