Counting suffix arrays and strings

Schürmann K-B, Stoye J (2008)
THEORETICAL COMPUTER SCIENCE 395(2-3): 220-234.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Autor
;
Abstract / Bemerkung
Suffix arrays are used in various applications and research areas like data compression or computational biology. In this work, our goal is to characterise the combinatorial properties of suffix arrays and their enumeration. For a fixed alphabet size and string length, we divide the set of all strings into equivalence classes of strings that share the same suffix array. For each such equivalence class, we count the number of strings contained in it. We also give exact formulas for computing the number of equivalence classes. Our methods yield a lower bound for the compressibility of suffix arrays and build the foundation for the efficient generation of appropriate test data sets for suffix array based algorithms. We also show that summing up the elements of all equivalence classes forms a particular instance for some summation identities of Eulerian numbers. (c) 2008 Elsevier B.V. All rights reserved.
Erscheinungsjahr
Zeitschriftentitel
THEORETICAL COMPUTER SCIENCE
Band
395
Zeitschriftennummer
2-3
Seite
220-234
ISSN
PUB-ID

Zitieren

Schürmann K-B, Stoye J. Counting suffix arrays and strings. THEORETICAL COMPUTER SCIENCE. 2008;395(2-3):220-234.
Schürmann, K. - B., & Stoye, J. (2008). Counting suffix arrays and strings. THEORETICAL COMPUTER SCIENCE, 395(2-3), 220-234. doi:10.1016/j.tcs.2008.01.011
Schürmann, K. - B., and Stoye, J. (2008). Counting suffix arrays and strings. THEORETICAL COMPUTER SCIENCE 395, 220-234.
Schürmann, K.-B., & Stoye, J., 2008. Counting suffix arrays and strings. THEORETICAL COMPUTER SCIENCE, 395(2-3), p 220-234.
K.-B. Schürmann and J. Stoye, “Counting suffix arrays and strings”, THEORETICAL COMPUTER SCIENCE, vol. 395, 2008, pp. 220-234.
Schürmann, K.-B., Stoye, J.: Counting suffix arrays and strings. THEORETICAL COMPUTER SCIENCE. 395, 220-234 (2008).
Schürmann, Klaus-Bernd, and Stoye, Jens. “Counting suffix arrays and strings”. THEORETICAL COMPUTER SCIENCE 395.2-3 (2008): 220-234.