A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm

Abstract : We show that there are asymptotically γn LMS-factors in a random word of length n, for some explicit γ that depends on the model of randomness under consideration. Our results hold for uniform distributions, memoryless sources and Markovian sources. From this analysis, we give new insight on the typical behavior of the IS-algorithm [9], which is one of the most efficient algorithms available for computing the suffix array.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01719172
Contributor : Admin Upem <>
Submitted on : Wednesday, February 28, 2018 - 7:41:00 AM
Last modification on : Thursday, July 5, 2018 - 2:46:00 PM
Long-term archiving on : Monday, May 28, 2018 - 10:58:37 AM

File

cpm15.pdf
Files produced by the author(s)

Identifiers

Citation

Cyril Nicaud. A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm. CPM 2015, Jun 2015, Ischia Island, Italy. pp.374-384, ⟨10.1007/978-3-319-19929-0_32⟩. ⟨hal-01719172⟩

Share

Metrics

Record views

59

Files downloads

88