Name
Abstract | ||
|---|---|---|
To store and search genomic databases efficiently, researchers have recently started building self-indexes based on LZ77. As the name suggests, a self-index for a string supports both random access and pattern matching queries. In this paper we show how, given a string S[1...n] whose LZ77 parse consists of z phrases, we can store a self-index for S in O(z log(n/z)) space such that later, first, given a position i and a length S, we can extract S[i.. i + l - 1] in O(l + log n) time; second, given a pattern P[1...m], we can list the occ occurrences of P in S in O(mlogm+ occ log log n) time. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-642-54423-1_63 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Binary logarithm,Discrete mathematics,Combinatorics,Parse tree,Computer science,Search engine indexing,Parsing,Pattern matching,Random access | Conference | 8392 |
ISSN | Citations | PageRank |
0302-9743 | 26 | 0.87 |
References | Authors | |
21 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Travis Gagie | 1 | 643 | 63.61 |
| Pawel Gawrychowski | 2 | 226 | 46.74 |
| Juha Kärkkäinen | 3 | 1354 | 95.20 |
| Yakov Nekrich | 4 | 450 | 38.94 |
| Simon J. Puglisi | 5 | 1132 | 75.14 |