Takuya Mieno
| Cluster I (Informatics and Computer Engineering) | Assistant Professor |
| Department of Computer and Network Engineering | Assistant Professor |
Researcher Information
Career
Educational Background
Research Activity Information
Paper
- Linear-Time Computation of Generalized Minimal Absent Words for Multiple Strings
Kouta Okabe; Takuya Mieno; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai
String Processing and Information Retrieval, Springer Nature Switzerland, 331-344, 20 Sep. 2023, Peer-reviwed
International conference proceedings - Finding top-k longest palindromes in substrings
Kazuki Mitani; Takuya Mieno; Kazuhisa Seto; Takashi Horiyama
Corresponding, Theoretical Computer Science, Elsevier BV, 114183-114183, Sep. 2023, Peer-reviwed
Scientific journal - Data Structures for Computing Unique Palindromes in Static and Non-Static Strings
Takuya Mieno; Mitsuru Funakoshi
Lead, Algorithmica, Springer Science and Business Media LLC, 30 Aug. 2023, Peer-reviwed
Scientific journal - Computing Palindromes on a Trie in Linear Time
Takuya Mieno; Mitsuru Funakoshi; Shunsuke Inenaga
Lead, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 248, Dec. 2022, Peer-reviwed, A trie T is a rooted tree such that each edge is labeled by a single character from the alphabet, and the labels of out-going edges from the same node are mutually distinct. Given a trie T with n edges, we show how to compute all distinct palindromes and all maximal palindromes on T in O(n) time, in the case of integer alphabets of size polynomial in n. This improves the state-of-the-art O(n log h)-time algorithms by Funakoshi et al. [PSC 2019], where h is the height of T . Using our new algorithms, the eertree with suffix links for a given trie T can readily be obtained in O(n) time. Further, our trie-based O(n)-space data structure allows us to report all distinct palindromes and maximal palindromes in a query string represented in the trie T , in output optimal time. This is an improvement over an existing (naïve) solution that precomputes and stores all distinct palindromes and maximal palindromes for each and every string in the trie T separately, using a total O(n2) preprocessing time and space, and reports them in output optimal time upon query.
International conference proceedings - Online Algorithms for Finding Distinct Substrings with Length and Multiple Prefix and Suffix Conditions
Laurentius Leonard; Shunsuke Inenaga; Hideo Bannai; Takuya Mieno
String Processing and Information Retrieval, Springer International Publishing, 24-37, 01 Nov. 2022, Peer-reviwed
International conference proceedings - Combinatorics of minimal absent words for a sliding window
Tooru Akagi; Yuki Kuhara; Takuya Mieno; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Theoretical Computer Science, Elsevier BV, 927, 109-119, Jun. 2022, Peer-reviwed
Scientific journal - Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings
Takuya Mieno; Mitsuru Funakoshi
Lead, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 13270 LNCS, 425-438, 29 May 2022, Peer-reviwed, A palindromic substring T[i.j] of a string T is said to be a shortest unique palindromic substring (SUPS) in T for an interval [p, q] if T[i.j] is a shortest one such that T[i.j] occurs only once in T, and [i, j] contains [p, q]. The SUPS problem is, given a string T of length n, to construct a data structure that can compute all the SUPSs for any given query interval. It is known that any SUPS query can be answered in O(α) time after O(n)-time preprocessing, where α is the number of SUPSs to output [Inoue et al., 2018]. In this paper, we first show that α is at most 4, and the upper bound is tight. Also, we present an algorithm to solve the SUPS problem for a sliding window that can answer any query in O(log log W) time and update data structures in amortized O(log σ) time, where W is the size of the window, and σ is the alphabet size. Furthermore, we consider the SUPS problem in the after-edit model and present an efficient algorithm. Namely, we present an algorithm that uses O(n) time for preprocessing and answers any k SUPS queries in O(log nlog log n+ klog log n) time after single character substitution. As a by-product, we propose a fully-dynamic data structure for range minimum queries (RmQs) with a constraint where the width of each query range is limited to polylogarithmic. The constrained RmQ data structure can answer such a query in constant time and support a single-element edit operation in amortized constant time.
International conference proceedings - Computing Minimal Unique Substrings for a Sliding Window
Takuya Mieno; Yuta Fujishige; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Lead, Algorithmica, Springer Science and Business Media LLC, 84, 3, 670-693, Mar. 2022, Peer-reviwed, Abstract
A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. In this paper, we study the problem of computing MUSs for a sliding window over a given string T. We first show how the set of MUSs can change when the window slides over T. We then present an $$O(n\log \sigma ')$$-time and O(d)-space algorithm to compute MUSs for a sliding window of size d over the input string T of length n, where $$\sigma '\le d$$ is the maximum number of distinct characters in every window.
Scientific journal - Palindromic trees for a sliding window and its applications
Takuya Mieno; Kiichi Watanabe; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Lead, Information Processing Letters, Elsevier BV, 173, 106174-106174, Jan. 2022, Peer-reviwed
Scientific journal - A Separation of γ and b via Thue–Morse Words
Hideo Bannai; Mitsuru Funakoshi; Tomohiro I; Dominik Köppl; Takuya Mieno; Takaaki Nishimoto
String Processing and Information Retrieval, Springer International Publishing, 12944 LNCS, 167-178, 2021, Peer-reviwed, We prove that for n≥ 2, the size b(tn) of the smallest bidirectional scheme for the nth Thue–Morse word tn is n+ 2. Since Kutsukake et al. [SPIRE 2020] show that the size γ(tn) of the smallest string attractor for tn is 4 for n≥ 4, this shows for the first time that there is a separation between the size of the smallest string attractor γ and the size of the smallest bidirectional scheme b, i.e., there exist string families such that γ= o(b).
In book - On the Approximation Ratio of LZ-End to LZ77
Takumi Ideue; Takuya Mieno; Mitsuru Funakoshi; Yuto Nakashima; Shunsuke Inenaga; Masayuki Takeda
String Processing and Information Retrieval, Springer International Publishing, 12944 LNCS, 114-126, 2021, Peer-reviwed, A family of Lempel-Ziv factorizations is a well-studied string structure. The LZ-End factorization is a member of the family that achieved faster extraction of any substrings (Kreft & Navarro, TCS 2013). One of the interests for LZ-End factorizations is the possible difference between the size of LZ-End and LZ77 factorizations. They also showed families of strings where the approximation ratio of the number of LZ-End phrases to the number of LZ77 phrases asymptotically approaches 2. However, the alphabet size of these strings is unbounded. In this paper, we analyze the LZ-End factorization of the period-doubling sequence. We also show that the approximation ratio for the period-doubling sequence asymptotically approaches 2 for the binary alphabet.
In book - Minimal Unique Palindromic Substrings After Single-Character Substitution
Mitsuru Funakoshi; Takuya Mieno
String Processing and Information Retrieval, Springer International Publishing, 12944 LNCS, 33-46, 2021, Peer-reviwed, A palindrome is a string that reads the same forward and backward. A palindromic substring w of a string T is called a minimal unique palindromic substring (MUPS) of T if w occurs only once in T and any proper palindromic substring of w occurs at least twice in T. MUPSs are utilized for answering the shortest unique palindromic substring problem, which is motivated by molecular biology [Inoue et al., 2018]. Given a string T of length n, all MUPSs of T can be computed in O(n) time. In this paper, we study the problem of updating the set of MUPSs when a character in the input string T is substituted by another character. We first analyze the number d of changes of MUPSs when a character is substituted, and show that d is in O(log n). Further, we present an algorithm that uses O(n) time and space for preprocessing, and updates the set of MUPSs in O(log σ+ (log log n) 2+ d) time where σ is the alphabet size. We also propose a variant of the algorithm, which runs in optimal O(1 + d) time when the alphabet size is constant.
In book - String Sanitization Under Edit Distance: Improved and Generalized.
Takuya Mieno; Solon P. Pissis; Leen Stougie; Michelle Sweering
Lead, 32nd Annual Symposium on Combinatorial Pattern Matching(CPM), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 19-18, 2021, Peer-reviwed
International conference proceedings - Space-efficient algorithms for computing minimal/shortest unique substrings
Takuya Mieno; Dominik Köppl; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Lead, Theoretical Computer Science, Elsevier BV, 845, 230-242, Dec. 2020, Peer-reviwed
Scientific journal - Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
Takuya Mieno; Yuki Kuhara; Tooru Akagi; Yuta Fujishige; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Lead, SOFSEM 2020: Theory and Practice of Computer Science, Springer International Publishing, 148-160, 2020, Peer-reviwed
In book - Algorithms and combinatorial properties on shortest unique palindromic substrings
Hiroe Inoue; Yuto Nakashima; Takuya Mieno; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Journal of Discrete Algorithms, Elsevier BV, 52-53, 122-132, Sep. 2018, Peer-reviwed
Scientific journal - Tight Bounds on the Maximum Number of Shortest Unique Substrings.
Takuya Mieno; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Lead, 28th Annual Symposium on Combinatorial Pattern Matching(CPM), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 24-11, 2017, Peer-reviwed
International conference proceedings - Shortest unique substring queries on run-length encoded strings
Takuya Mieno; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
Lead, Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 58, 01 Aug. 2016, Peer-reviwed, We consider the problem of answering shortest unique substring (SUS) queries on run-length encoded strings. For a string S, a unique substring u = S[i..j] is said to be a shortest unique substring (SUS) of S containing an interval [s, t] (i ≤ s ≤ t ≤ j) if for any i0 ≤ s ≤t ≤j0 with j - i >
j0 - i0, S[i0..j0] occurs at least twice in S. Given a run-length encoding of size m of a string of length N, we show that we can construct a data structure of size O(m + πs(N,m)) in O(mlogm + πc(N,m)) time such that queries can be answered in O(πq(N,m) + k) time, where k is the size of the output (the number of SUSs), and πs(N,m), πc(N,m), πq(N,m) are, respectively, the size, construction time, and query time for a predecessor/successor query data structure of m elements for the universe of [1,N]. Using the data structure by Beam and Fich (JCSS 2002), this results in a data structure of O(m) space that is constructed in O(mlogm) time, and answers queries in O( √ log m/log logm + k) time.
International conference proceedings, English
Lectures, oral presentations, etc.
Research Themes
- 不在/稀少文字列の計算技法と一般化文字列への展開
三重野 琢也
日本学術振興会, 科学研究費助成事業, 電気通信大学, 若手研究, 24K20734
Apr. 2024 - Mar. 2027 - 文字列処理におけるNP困難問題の高速解法の追求
三重野 琢也
日本学術振興会, 科学研究費助成事業 学術変革領域研究(A), 電気通信大学, 学術変革領域研究(A), 23H04381
01 Apr. 2023 - 31 Mar. 2025 - 動的文字列処理に対するアルゴリズム技法の開発と計算限界の解明
三重野 琢也
日本学術振興会, 科学研究費助成事業 研究活動スタート支援, 電気通信大学, 研究活動スタート支援, 22K21273
31 Aug. 2022 - 31 Mar. 2024 - 最先端文字列アルゴリズム理論に基づく巨大データ解析技法
三重野 琢也
日本学術振興会, 科学研究費助成事業 特別研究員奨励費, 九州大学, 特別研究員奨励費, 前から読んでも後ろから読んでも同じ文字列を回文という。文字列から回文構造を発見する問題は特に生物情報科学の分野で重要視され、盛んに研究されている。 本研究期間においては、文字列中の回文構造を効率よく検出するためのデータ構造・アルゴリズムの開発を主として行った。他にも文字列圧縮アルゴリズムの性能に関する研究などを行い、以下の６つの成果を得た。 １つ目の成果は、入力文字列に対して特定の編集操作が許された設定において、ユニーク回文部分文字列を計算するアルゴリズムの提案である。ユニーク回文部分文字列とは、文字列中にちょうど一度だけ出現する回文である。本成果は国際会議 SPIRE 2021 に採択されており、さらにその結果を応用した研究成果は国際会議 IWOCA 2022 に投稿された。 ２つ目の成果は、双方向マクロスキームと呼ばれる文字列圧縮形式に対する圧縮性能限界の解明である。３つ目の成果は、LZEnd 圧縮と呼ばれる文字列圧縮手法の圧縮性能に関する新たな結果の証明である。文字列圧縮手法の性能を比較・解析する研究は文字列圧縮研究の分野で近年盛んに行われており、特に２つ目の成果は同分野で注目されていた未解決問題のひとつを解決したものである。２つ目と３つ目の成果は国際会議 SPIRE 2021 に採択されている。 ４つ目の成果は、RePair という文字列圧縮手法の圧縮性能に関する新たな結果の証明である。５つ目の成果は、デカルト木部分列照合問題と呼ばれる緩和された部分列照合問題に対するアルゴリズムの提案である。６つ目の成果は、圧縮表現された文字列上で、その文字列中に存在しない不在文字列を計算するアルゴリズムの提案である。上記３つの成果はいずれも国際会議 CPM 2022 に採択されている。, 20J11983
24 Apr. 2020 - 31 Mar. 2022