2016/05/31 by Nishimoto, Takaaki, I, Tomohiro, Inenaga, Shunsuke +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1605.09558
In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w = O(min(z log N log^*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 ≥ 3N is an integer that can be handled in constant time under word RAM model. Our index supports searching for a pattern P in T in O(|P| fA + log w log |P| log^* M (log N + log |P| log^* M) + occ log N) time and insertion/deletion of a substring of length y in O((y+ log Nlog^* M)log w log N log^* M) time, where fA = O(min \ (loglog M loglog w)/(logloglog M), √((log w)/(loglog w)) \). Also, we propose a new space-efficient LZ77 factorization algorithm for a given text of length N, which runs in O(N fA + z log w log3 N (log^* N)2) time with O(w) working space.