Name
Abstract | ||
|---|---|---|
In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w=O(min(zlogNlog∗M,N)) is the size of the signature encoding of T, z is the size of the Lempel–Ziv77 (LZ77) factorization of T, N is the length of T, and M≥N is the maximum length of T. Our index supports searching for a pattern P in T in O(|P|fA+logwlog|P|log∗M(logN+log|P|log∗M)+occlogN) time and insertion/deletion of a substring of length y in O((y+logNlog∗M)logwlogNlog∗M) time, where occ is the number of occurrences of P in T and fA=O(min{loglogMloglogwlogloglogM,logwloglogw}). Also, we propose a new space-efficient LZ77 factorization algorithm for a given text T, which runs in O(NfA+zlogwlog3N(log∗N)2) time with O(w) working space. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.dam.2019.01.014 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Dynamic texts,LZ77 factorization,Dynamic index,Compressed data structures,Dynamic data structures | Log-log plot,Discrete mathematics,Binary logarithm,Substring,Combinatorics,Working space,Factorization,Dynamic text,Mathematics | Journal |
Volume | ISSN | Citations |
274 | 0166-218X | 5 |
PageRank | References | Authors |
0.42 | 15 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takaaki Nishimoto | 1 | 23 | 3.54 |
| Tomohiro I | 2 | 148 | 22.06 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 902 | 79.24 |