Sampled longest common prefix array

Visa fullständig post



Permalänk

http://hdl.handle.net/10138/23555

Citation

Sirén , J 2010 , Sampled longest common prefix array . in A Amir & L Parida (eds) , Combinatorial Pattern Matching : 21st Annual Symposium, CPM 2010 . Lecture Notes in Computer Science , no. 6129 , Springer , pp. 227-237 , 21st Annual Symposium on Combinatorial Pattern Matching , New York , United States , 21/06/2010 . DOI: 10.1007/978-3-642-13509-5_21

Titel: Sampled longest common prefix array
Författare: Sirén, Jouni
Medarbetare: University of Helsinki, Department of Computer Science
Amir, A.
Parida, L.

Utgivare: Springer
Datum: 2010
Språk: eng
Sidantal: 11
Tillhör serie: Combinatorial Pattern Matching 21st Annual Symposium, CPM 2010
Tillhör serie: Lecture Notes in Computer Science
ISBN: 978-3-642-13508-8
DOI: https://doi.org/10.1007/978-3-642-13509-5_21
Permanenta länken (URI): http://hdl.handle.net/10138/23555
Abstrakt: When augmented with the longest common prefix (LCP) array and some other structures, the suffix array can solve many string processing problems in optimal time and space. A compressed representation of the LCP array is also one of the main building blocks in many compressed suffix tree proposals. In this paper, we describe a new compressed LCP representation: the sampled LCP array. We show that when used with a compressed suffix array (CSA), the sampled LCP array often offers better time/space trade-offs than the existing alternatives. We also show how to construct the compressed representations of the LCP array directly from a CSA
Subject: 113 Computer and information sciences
Licens:


Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
paper.pdf 311.0Kb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post