TY - GEN

T1 - Dynamic index and LZ factorization in compressed space

AU - Nishimoto, Takaaki

AU - Tomohiro, I.

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Publisher Copyright:
© Czech Technical University in Prague.

PY - 2016

Y1 - 2016

N2 - In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w = O(min(z logN 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 ≥ 4N 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(logN + log |P| log-M) + occ logN) time and insertion/deletion of a substring of length y in O((y + logN log-M) log w logN log-M) time, where fA = O(min{log logM log log w log log logM , √ log w log log w}). Also, we propose a new spaceefficient LZ77 factorization algorithm for a given text of length N, which runs in O(NfA + z log w log3 N(log- N)2) time with O(w) working space.

AB - In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w = O(min(z logN 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 ≥ 4N 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(logN + log |P| log-M) + occ logN) time and insertion/deletion of a substring of length y in O((y + logN log-M) log w logN log-M) time, where fA = O(min{log logM log log w log log logM , √ log w log log w}). Also, we propose a new spaceefficient LZ77 factorization algorithm for a given text of length N, which runs in O(NfA + z log w log3 N(log- N)2) time with O(w) working space.

UR - http://www.scopus.com/inward/record.url?scp=85027267678&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027267678&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85027267678

T3 - Proceedings of the Prague Stringology Conference, PSC 2016

SP - 158

EP - 171

BT - Proceedings of the Prague Stringology Conference, PSC 2016

A2 - Holub, Jan

A2 - Zdarek, Jan

PB - Prague Stringology Club

T2 - 20th Prague Stringology Conference, PSC 2016

Y2 - 29 August 2016 through 31 August 2016

ER -