Arrow Research search

Author name cluster

Tomohiro I

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

MFCS Conference 2016 Conference Paper

Fully Dynamic Data Structure for LCE Queries in Compressed Space

  • Takaaki Nishimoto
  • Tomohiro I
  • Shunsuke Inenaga
  • Hideo Bannai
  • Masayuki Takeda

A Longest Common Extension (LCE) query on a text T of length N asks for the length of the longest common prefix of suffixes starting at given two positions. We show that the signature encoding G of size w = O(min(z log N log^* M, N)) [Mehlhorn et al. , Algorithmica 17(2): 183-198, 1997] of T, which can be seen as a compressed representation of T, has a capability to support LCE queries in O(log N + log ell log^* M) time, where ell is the answer to the query, z is the size of the Lempel-Ziv77 (LZ77) factorization of T, and M >= 4N is an integer that can be handled in constant time under word RAM model. In compressed space, this is the fastest deterministic LCE data structure in many cases. Moreover, G can be enhanced to support efficient update operations: After processing G in O(w f_A) time, we can insert/delete any (sub)string of length y into/from an arbitrary position of T in O((y + log Nlog^* M) f_A) time, where f_A = O(min{ (loglog M loglog w)/(logloglog M), sqrt(log w/loglog w)}). This yields the first fully dynamic LCE data structure working in compressed space. We also present efficient construction algorithms from various types of inputs: We can construct G in O(N f_A) time from uncompressed string T; in O(n loglog (n log^* M) log N log^* M) time from grammar-compressed string T represented by a straight-line program of size n; and in O(z f_A log N log^* M) time from LZ77-compressed string T with z factors. 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.

Details

MFCS Conference 2013 Conference Paper

Detecting Regularities on Grammar-Compressed Strings

  • Tomohiro I
  • Wataru Matsubara
  • Kouji Shimohira
  • Shunsuke Inenaga
  • Hideo Bannai
  • Masayuki Takeda
  • Kazuyuki Narisawa
  • Ayumi Shinohara

Abstract We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in s in O ( n 3 h ) time and O ( n 2 ) space, where h is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O ( n 3 h + gnh log N ) time and O ( n 2 ) space, where g is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in O ( n 2 h ) time and O ( nh ( n + log 2 N )) time, respectively.

Details