Search

Your search keyword '"Bannai, Hideo"' showing total 531 results
Start Over Author "Bannai, Hideo"

Refine your results

531 results on '"Bannai, Hideo"'

101. Shortest Unique Palindromic Substring Queries in Optimal Time

Author

Nakashima, Yuto, Inoue, Hiroe, Mieno, Takuya, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Brankovic, Ljiljana, editor, Ryan, Joe, editor, and Smyth, William F., editor

Published
2018
Full Text
View/download PDF

102. Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays

Author

Kuhara, Yuki, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Gagie, Travis, editor, Moffat, Alistair, editor, Navarro, Gonzalo, editor, and Cuadros-Vargas, Ernesto, editor

Published
2018
Full Text
View/download PDF

103. Simpler and Faster Lempel Ziv Factorization

Author

Goto, Keisuke and Bannai, Hideo

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We present a new, simple, and efficient approach for computing the Lempel-Ziv (LZ77) factorization of a string in linear time, based on suffix arrays. Computational experiments on various data sets show that our approach constantly outperforms the currently fastest algorithm LZ OG (Ohlebusch and Gog 2011), and can be up to 2 to 3 times faster in the processing after obtaining the suffix array, while requiring the same or a little more space.

Published
2012

104. Efficient LZ78 factorization of grammar compressed text

Author

Bannai, Hideo, Inenaga, Shunsuke, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We present an efficient algorithm for computing the LZ78 factorization of a text, where the text is represented as a straight line program (SLP), which is a context free grammar in the Chomsky normal form that generates a single string. Given an SLP of size $n$ representing a text $S$ of length $N$, our algorithm computes the LZ78 factorization of $T$ in $O(n\sqrt{N}+m\log N)$ time and $O(n\sqrt{N}+m)$ space, where $m$ is the number of resulting LZ78 factors. We also show how to improve the algorithm so that the $n\sqrt{N}$ term in the time and space complexities becomes either $nL$, where $L$ is the length of the longest LZ78 factor, or $(N - \alpha)$ where $\alpha \geq 0$ is a quantity which depends on the amount of redundancy that the SLP captures with respect to substrings of $S$ of a certain length. Since $m = O(N/\log_\sigma N)$ where $\sigma$ is the alphabet size, the latter is asymptotically at least as fast as a linear time algorithm which runs on the uncompressed string when $\sigma$ is constant, and can be more efficient when the text is compressible, i.e. when $m$ and $n$ are small., Comment: SPIRE 2012

Published
2012
Full Text
View/download PDF

105. Time and Space Efficient Lempel-Ziv Factorization based on Run Length Encoding

Author

Yamamoto, Jun'ichi, Bannai, Hideo, Inenaga, Shunsuke, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We propose a new approach for calculating the Lempel-Ziv factorization of a string, based on run length encoding (RLE). We present a conceptually simple off-line algorithm based on a variant of suffix arrays, as well as an on-line algorithm based on a variant of directed acyclic word graphs (DAWGs). Both algorithms run in $O(N+n\log n)$ time and O(n) extra space, where N is the size of the string, $n\leq N$ is the number of RLE factors. The time dependency on N is only in the conversion of the string to RLE, which can be computed very efficiently in O(N) time and O(1) extra space (excluding the output). When the string is compressible via RLE, i.e., $n = o(N)$, our algorithms are, to the best of our knowledge, the first algorithms which require only o(N) extra space while running in $o(N\log N)$ time.

Published
2012

106. Speeding-up $q$-gram mining on grammar-based compressed texts

Author

Goto, Keisuke, Bannai, Hideo, Inenaga, Shunsuke, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We present an efficient algorithm for calculating $q$-gram frequencies on strings represented in compressed form, namely, as a straight line program (SLP). Given an SLP $\mathcal{T}$ of size $n$ that represents string $T$, the algorithm computes the occurrence frequencies of all $q$-grams in $T$, by reducing the problem to the weighted $q$-gram frequencies problem on a trie-like structure of size $m = |T|-\mathit{dup}(q,\mathcal{T})$, where $\mathit{dup}(q,\mathcal{T})$ is a quantity that represents the amount of redundancy that the SLP captures with respect to $q$-grams. The reduced problem can be solved in linear time. Since $m = O(qn)$, the running time of our algorithm is $O(\min\{|T|-\mathit{dup}(q,\mathcal{T}),qn\})$, improving our previous $O(qn)$ algorithm when $q = \Omega(|T|/n)$.

Published
2012
Full Text
View/download PDF

107. Computing q-gram Non-overlapping Frequencies on SLP Compressed Texts

Author

Goto, Keisuke, Bannai, Hideo, Inenaga, Shunsuke, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Length-$q$ substrings, or $q$-grams, can represent important characteristics of text data, and determining the frequencies of all $q$-grams contained in the data is an important problem with many applications in the field of data mining and machine learning. In this paper, we consider the problem of calculating the {\em non-overlapping frequencies} of all $q$-grams in a text given in compressed form, namely, as a straight line program (SLP). We show that the problem can be solved in $O(q^2n)$ time and $O(qn)$ space where $n$ is the size of the SLP. This generalizes and greatly improves previous work (Inenaga & Bannai, 2009) which solved the problem only for $q=2$ in $O(n^4\log n)$ time and $O(n^3)$ space.

Published
2011

108. Computing q-gram Frequencies on Collage Systems

Author

Goto, Keisuke, Bannai, Hideo, Inenaga, Shunsuke, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Collage systems are a general framework for representing outputs of various text compression algorithms. We consider the all $q$-gram frequency problem on compressed string represented as a collage system, and present an $O((q+h\log n)n)$-time $O(qn)$-space algorithm for calculating the frequencies for all $q$-grams that occur in the string. Here, $n$ and $h$ are respectively the size and height of the collage system.

Published
2011

109. Restructuring Compressed Texts without Explicit Decompression

Author

Goto, Keisuke, Maruyama, Shirou, Inenaga, Shunsuke, Bannai, Hideo, Sakamoto, Hiroshi, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We consider the problem of {\em restructuring} compressed texts without explicit decompression. We present algorithms which allow conversions from compressed representations of a string $T$ produced by any grammar-based compression algorithm, to representations produced by several specific compression algorithms including LZ77, LZ78, run length encoding, and some grammar based compression algorithms. These are the first algorithms that achieve running times polynomial in the size of the compressed input and output representations of $T$. Since most of the representations we consider can achieve exponential compression, our algorithms are theoretically faster in the worst case, than any algorithm which first decompresses the string for the conversion.

Published
2011

110. Fast $q$-gram Mining on SLP Compressed Strings

Author

Goto, Keisuke, Bannai, Hideo, Inenaga, Shunsuke, and Takeda, Masayuki

Subjects
Computer Science - Data Structures and Algorithms
Abstract

We present simple and efficient algorithms for calculating $q$-gram frequencies on strings represented in compressed form, namely, as a straight line program (SLP). Given an SLP of size $n$ that represents string $T$, we present an $O(qn)$ time and space algorithm that computes the occurrence frequencies of $q$-grams in $T$. Computational experiments show that our algorithm and its variation are practical for small $q$, actually running faster on various real string data, compared to algorithms that work on the uncompressed text. We also discuss applications in data mining and classification of string data, for which our algorithms can be useful.

Published
2011

112. New Lower Bounds for the Maximum Number of Runs in a String

Author

Kusano, Kazuhiko, Matsubara, Wataru, Ishino, Akira, Bannai, Hideo, and Shinohara, Ayumi

Subjects
Computer Science - Discrete Mathematics, G.2.1
Abstract

We show a new lower bound for the maximum number of runs in a string. We prove that for any e > 0, (a -- e)n is an asymptotic lower bound, where a = 56733/60064 = 0.944542. It is superior to the previous bound 0.927 given by Franek et al. Moreover, our construction of the strings and the proof is much simpler than theirs.

Published
2008

116. Faster STR-EC-LCS Computation

Author

Yamada, Kohei, primary, Nakashima, Yuto, additional, Inenaga, Shunsuke, additional, Bannai, Hideo, additional, and Takeda, Masayuki, additional

Published
2020
Full Text
View/download PDF

119. Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings

Author

Ueki, Yohei, Diptarama, Kurihara, Masatoshi, Matsuoka, Yoshiaki, Narisawa, Kazuyuki, Yoshinaka, Ryo, Bannai, Hideo, Inenaga, Shunsuke, Shinohara, Ayumi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Baier, Christel, editor, van den Brand, Mark, editor, Eder, Johann, editor, Hinchey, Mike, editor, and Margaria, Tiziana, editor

Published
2017
Full Text
View/download PDF

120. Sliding suffix trees simplified

Author

Leonard, Laurentius, Inenaga, Shunsuke, Bannai, Hideo, and Mieno, Takuya

Subjects
FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS)
Abstract

Sliding suffix trees (Fiala & Greene, 1989) for an input text $T$ over an alphabet of size $\sigma$ and a sliding window $W$ of $T$ can be maintained in $O(|T| \log \sigma)$ time and $O(|W|)$ space. The two previous approaches that achieve this can be categorized into the credit-based approach of Fiala and Greene (1989) and Larsson (1996, 1999), or the batch-based approach proposed by Senft (2005). Brodnik and Jekovec (2018) showed that the sliding suffix tree can be supplemented with leaf pointers in order to find all occurrences of an online query pattern in the current window, and that leaf pointers can be maintained by credit-based arguments as well. The main difficulty in the credit-based approach is in the maintenance of index-pairs that represent each edge. In this paper, we show that valid edge index-pairs can be derived in constant time from leaf pointers, thus reducing the maintenance of edge index-pairs to the maintenance of leaf pointers. We further propose a new simple method which maintains leaf pointers without using credit-based arguments. Our algorithm and proof of correctness are much simpler compared to the credit-based approach, whose analyses were initially flawed (Senft 2005)., Comment: 12 pages + 5 pages of appendix. 18 figures in total

Published
2023

124. Finding Gapped Palindromes Online

Author

Fujishige, Yuta, Nakamura, Michitaro, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Mäkinen, Veli, editor, Puglisi, Simon J., editor, and Salmela, Leena, editor

Published
2016
Full Text
View/download PDF

130. Closed factorization

Author

Badkobeh, Golnaz, Bannai, Hideo, Goto, Keisuke, I, Tomohiro, Iliopoulos, Costas S., Inenaga, Shunsuke, Puglisi, Simon J., and Sugimoto, Shiho

Published
2016
Full Text
View/download PDF

131. Inferring Strings from Full Abelian Periods

Author

Nishida, Makoto, I., Tomohiro, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Elbassioni, Khaled, editor, and Makino, Kazuhisa, editor

Published
2015
Full Text
View/download PDF

132. A Faster Algorithm for Computing Maximal -gapped Repeats in a String

Author

Tanimura, Yuka, Fujishige, Yuta, I, Tomohiro, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Iliopoulos, Costas, editor, Puglisi, Simon, editor, and Yilmaz, Emine, editor

Published
2015
Full Text
View/download PDF

133. Efficient Algorithms for Longest Closed Factor Array

Author

Bannai, Hideo, Inenaga, Shunsuke, Kociumaka, Tomasz, Lefebvre, Arnaud, Radoszewski, Jakub, Rytter, Wojciech, Sugimoto, Shiho, Waleń, Tomasz, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Iliopoulos, Costas, editor, Puglisi, Simon, editor, and Yilmaz, Emine, editor

Published
2015
Full Text
View/download PDF

134. Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree

Author

Matsuoka, Yoshiaki, I, Tomohiro, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Cicalese, Ferdinando, editor, Porat, Ely, editor, and Vaccaro, Ugo, editor

Published
2015
Full Text
View/download PDF

135. LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding

Author

Goto, Keisuke, Bannai, Hideo, Inenaga, Shunsuke, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Cicalese, Ferdinando, editor, Porat, Ely, editor, and Vaccaro, Ugo, editor

Published
2015
Full Text
View/download PDF

136. An Opportunistic Text Indexing Structure Based on Run Length Encoding

Author

Tamakoshi, Yuya, Goto, Keisuke, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Paschos, Vangelis Th., editor, and Widmayer, Peter, editor

Published
2015
Full Text
View/download PDF

139. Inferring Strings from Lyndon Factorization

Author

Nakashima, Yuto, Okabe, Takashi, I, Tomohiro, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Csuhaj-Varjú, Erzsébet, editor, Dietzfelbinger, Martin, editor, and Ésik, Zoltán, editor

Published
2014
Full Text
View/download PDF

140. Computing Palindromic Factorizations and Palindromic Covers On-line

Author

I, Tomohiro, Sugimoto, Shiho, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Kulikov, Alexander S., editor, Kuznetsov, Sergei O., editor, and Pevzner, Pavel, editor

Published
2014
Full Text
View/download PDF

141. Shortest Unique Substrings Queries in Optimal Time

Author

Tsuruta, Kazuya, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Geffert, Viliam, editor, Preneel, Bart, editor, Rovan, Branislav, editor, Štuller, Július, editor, and Tjoa, A Min, editor

Published
2014
Full Text
View/download PDF

147. Compressed Automata for Dictionary Matching

Author

I, Tomohiro, Nishimoto, Takaaki, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Konstantinidis, Stavros, editor

Published
2013
Full Text
View/download PDF

148. Converting SLP to LZ78 in almost Linear Time

Author

Bannai, Hideo, Gawrychowski, Paweł, Inenaga, Shunsuke, Takeda, Masayuki, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fischer, Johannes, editor, and Sanders, Peter, editor

Published
2013
Full Text
View/download PDF

149. Permuted Pattern Matching on Multi-track Strings

Author

Katsura, Takashi, Narisawa, Kazuyuki, Shinohara, Ayumi, Bannai, Hideo, Inenaga, Shunsuke, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, van Emde Boas, Peter, editor, Groen, Frans C. A., editor, Italiano, Giuseppe F., editor, Nawrocki, Jerzy, editor, and Sack, Harald, editor

Published
2013
Full Text
View/download PDF

150. Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text

Author

I, Tomohiro, Nakashima, Yuto, Inenaga, Shunsuke, Bannai, Hideo, Takeda, Masayuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kurland, Oren, editor, Lewenstein, Moshe, editor, and Porat, Ely, editor

Published
2013
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results