Faculty Profiles - I Tomohiro

Papers - I Tomohiro

Division display61 - 65 of about 65／ All the affair displays >>

Faster compact on-line Lempel-ziv factorization Reviewed

Yamamoto J., I T., Bannai H., Inenaga S., Takeda M.

Leibniz International Proceedings in Informatics, LIPIcs 25 675 - 686 2014.03

Language：English Publishing type：Research paper (international conference proceedings)

© Jun'ichi Yamamoto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga, and Masayuki Takeda. We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in O(N logN) time and uses only O(N log σ) bits of working space, where N is the length of the string and σ is the size of the alphabet. This is a notable improvement compared to the performance of previous on-line algorithms using the same order of working space but running in either O(N log3N) time (Okanohara & Sadakane 2009) or O(N log2N) time (Starikovskaya 2012). The key to our new algorithm is in the utilization of an elegant but less popular index structure called Directed Acyclic Word Graphs, or DAWGs (Blumer et al. 1985). We also present an opportunistic variant of our algorithm, which, given the run length encoding of size m of a string of length N, computes the Lempel-Ziv factorization of the string on-line, in O (m · min{n (log logm)(log logN)/log log logN , √ logm/log logm o})time and O(mlogN) bits of space.

DOI： 10.4230/LIPIcs.STACS.2014.675

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84907858098&origin=inward

Inferring strings from suffix trees and links on a binary alphabet Reviewed

I T., Inenaga S., Bannai H., Takeda M.

Discrete Applied Mathematics 163 ( PART 3 ) 316 - 325 2014.01

Authorship：Lead author Language：English Publishing type：Research paper (scientific journal)

A suffix tree, which provides us with a linear space full-text index of a given string, is a fundamental data structure for string processing and information retrieval. In this paper we consider the reverse engineering problem on suffix trees: given an unlabeled ordered rooted tree T accompanied with a node-to-node transition function f, infer a string whose suffix tree and its suffix links for inner nodes are isomorphic to T and f, respectively. Also, we consider the enumeration problem in which we enumerate all strings corresponding to an input tree and links. By introducing new characterizations of suffix trees, we show that the reverse engineering problem and the enumeration problem on suffix trees on a binary alphabet can be solved in optimal time. © 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2013.02.033

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84889665144&origin=inward

Computing palindromic factorizations and palindromic covers on-line Reviewed

I T., Sugimoto S., Inenaga S., Bannai H., Takeda M.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8486 150 - 161 2014.01

Language：English Publishing type：Research paper (international conference proceedings)

A palindromic factorization of a string w is a factorization of w consisting only of palindromic substrings of w. In this paper, we present an on-line O(n logn)-time O(n)-space algorithm to compute smallest palindromic factorizations of all prefixes of w, where n is the length of a given string w. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes of w, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, in O(n logn) time and O(n) space, in an on-line manner. We also present an on-line O(n)-time O(n)-space algorithm to compute a smallest palindromic cover of w. © 2014 Springer International Publishing Switzerland.

DOI： 10.1007/978-3-319-07566-2_16

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84958527699&origin=inward

Closed factorization Reviewed

Badkobeh G., Bannai H., Goto K., I T., Iliopoulos C., Inenaga S., Puglisi S., Sugimoto S.

Proceedings of the Prague Stringology Conference 2014, PSC 2014 162 - 168 2014.01

Language：English Publishing type：Research paper (international conference proceedings)

© Czech Technical University in Prague, Czech Republic. A closed string is a string with a proper substring that occurs in the string as a prefix and a suffix, but not elsewhere. Closed strings were introduced by Fici (Proc. WORDS, 2011) as objects of combinatorial interest in the study of Trapezoidal and Sturmian words. In this paper we consider algorithms for computing closed factors (substrings) in strings, and in particular for greedily factorizing a string into a sequence of longest closed factors. We describe an algorithm for this problem that uses linear time and space. We then consider the related problem of computing, for every position in the string, the longest closed factor starting at that position. We describe a simple algorithm for the problem that runs in O(n log n/ log log n) time.

Scopus

Other Link： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84928791807&origin=inward

Inferring strings from Lyndon factorization Reviewed

Nakashima Y., Okabe T., I T., Inenaga S., Bannai H., Takeda M.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8635 LNCS ( PART 2 ) 565 - 576 2014.01

　 PREV -NEXT　

<I Tomohiro>

Papers - I Tomohiro