2015/04/27 by Takaaki Nishimoto, I Tomohiro, Nishimoto, Takaaki +7 · 1 citation
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1504.06954
openalex publication_date 2015/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we present the following results: (1) We propose a new dynamic compressed index of O(w) space, that supports searching for a pattern P in the current text in O(|P| f(M,w) + 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 N is the length of the current text, M is the maximum length of the dynamic text, z is the size of the Lempel-Ziv77 (LZ77) factorization of the current text, f(a,b) = O(min \ (loglog a loglog b)/(logloglog a), √((log b)/(loglog b)) \) and w = O(z log N log^*M). (2) We propose a new space-efficient LZ77 factorization algorithm for a given text of length N, which runs in O(N f(N,w') + z log w' log3 N (log^* N)2) time with O(w') working space, where w' =O(z log N log^* N). (3) We propose a data structure of O(w) space which supports longest common extension (LCE) queries on the text in O(log N + log ℓ log^* N) time, where ℓ is the output LCE length. On top of the above contributions, we show several applications of our data structures which improve previous best known results on grammar-compressed string processing.