三重野 琢也
| Ⅰ類（情報系） | 助教 |
| 情報・ネットワーク工学専攻 | 助教 |
研究者情報
経歴
学歴
研究活動情報
論文
- 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, 出版日 2023年09月20日, 査読付
研究論文（国際会議プロシーディングス） - Finding top-k longest palindromes in substrings
Kazuki Mitani; Takuya Mieno; Kazuhisa Seto; Takashi Horiyama
責任著者, Theoretical Computer Science, Elsevier BV, 掲載ページ 114183-114183, 出版日 2023年09月, 査読付
研究論文（学術雑誌） - Data Structures for Computing Unique Palindromes in Static and Non-Static Strings
Takuya Mieno; Mitsuru Funakoshi
筆頭著者, Algorithmica, Springer Science and Business Media LLC, 出版日 2023年08月30日, 査読付
研究論文（学術雑誌） - Computing Palindromes on a Trie in Linear Time
Takuya Mieno; Mitsuru Funakoshi; Shunsuke Inenaga
筆頭著者, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 248巻, 出版日 2022年12月, 査読付, 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.
研究論文（国際会議プロシーディングス） - 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, 出版日 2022年11月01日, 査読付
研究論文（国際会議プロシーディングス） - 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, 出版日 2022年06月, 査読付
研究論文（学術雑誌） - Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings
Takuya Mieno; Mitsuru Funakoshi
筆頭著者, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 13270 LNCS巻, 掲載ページ 425-438, 出版日 2022年05月29日, 査読付, 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.
研究論文（国際会議プロシーディングス） - Computing Minimal Unique Substrings for a Sliding Window
Takuya Mieno; Yuta Fujishige; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, Algorithmica, Springer Science and Business Media LLC, 84巻, 3号, 掲載ページ 670-693, 出版日 2022年03月, 査読付, 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.
研究論文（学術雑誌） - Palindromic trees for a sliding window and its applications
Takuya Mieno; Kiichi Watanabe; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, Information Processing Letters, Elsevier BV, 173巻, 掲載ページ 106174-106174, 出版日 2022年01月, 査読付
研究論文（学術雑誌） - 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年09月, 査読付, 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).
研究論文（国際会議プロシーディングス） - 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年09月, 査読付, 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.
研究論文（国際会議プロシーディングス） - 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年09月, 査読付, 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.
研究論文（国際会議プロシーディングス） - String Sanitization Under Edit Distance: Improved and Generalized.
Takuya Mieno; Solon P. Pissis; Leen Stougie; Michelle Sweering
筆頭著者, 32nd Annual Symposium on Combinatorial Pattern Matching(CPM), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 掲載ページ 19-18, 出版日 2021年06月, 査読付
研究論文（国際会議プロシーディングス） - Space-efficient algorithms for computing minimal/shortest unique substrings
Takuya Mieno; Dominik Köppl; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, Theoretical Computer Science, Elsevier BV, 845巻, 掲載ページ 230-242, 出版日 2020年12月, 査読付
研究論文（学術雑誌）, 英語 - 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
筆頭著者, SOFSEM 2020: Theory and Practice of Computer Science, Springer International Publishing, 掲載ページ 148-160, 出版日 2020年, 査読付
論文集(書籍)内論文 - 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, 出版日 2018年09月, 査読付
研究論文（学術雑誌）, 英語 - Tight Bounds on the Maximum Number of Shortest Unique Substrings.
Takuya Mieno; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, 28th Annual Symposium on Combinatorial Pattern Matching(CPM), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 掲載ページ 24-11, 出版日 2017年, 査読付
研究論文（国際会議プロシーディングス） - Shortest unique substring queries on run-length encoded strings
Takuya Mieno; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
筆頭著者, Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 58巻, 出版日 2016年08月01日, 査読付, 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.
研究論文（国際会議プロシーディングス）, 英語
共同研究・競争的資金等の研究課題
- 不在/稀少文字列の計算技法と一般化文字列への展開
三重野 琢也
日本学術振興会, 科学研究費助成事業, 電気通信大学, 若手研究, 24K20734
研究期間 2024年04月 - 2027年03月 - 文字列処理におけるNP困難問題の高速解法の追求
三重野 琢也
日本学術振興会, 科学研究費助成事業 学術変革領域研究(A), 電気通信大学, 学術変革領域研究(A), 23H04381
研究期間 2023年04月01日 - 2025年03月31日 - 動的文字列処理に対するアルゴリズム技法の開発と計算限界の解明
三重野 琢也
日本学術振興会, 科学研究費助成事業 研究活動スタート支援, 電気通信大学, 研究活動スタート支援, 22K21273
研究期間 2022年08月31日 - 2024年03月31日 - 最先端文字列アルゴリズム理論に基づく巨大データ解析技法
三重野 琢也
日本学術振興会, 科学研究費助成事業 特別研究員奨励費, 九州大学, 特別研究員奨励費, 前から読んでも後ろから読んでも同じ文字列を回文という。文字列から回文構造を発見する問題は特に生物情報科学の分野で重要視され、盛んに研究されている。 本研究期間においては、文字列中の回文構造を効率よく検出するためのデータ構造・アルゴリズムの開発を主として行った。他にも文字列圧縮アルゴリズムの性能に関する研究などを行い、以下の６つの成果を得た。 １つ目の成果は、入力文字列に対して特定の編集操作が許された設定において、ユニーク回文部分文字列を計算するアルゴリズムの提案である。ユニーク回文部分文字列とは、文字列中にちょうど一度だけ出現する回文である。本成果は国際会議 SPIRE 2021 に採択されており、さらにその結果を応用した研究成果は国際会議 IWOCA 2022 に投稿された。 ２つ目の成果は、双方向マクロスキームと呼ばれる文字列圧縮形式に対する圧縮性能限界の解明である。３つ目の成果は、LZEnd 圧縮と呼ばれる文字列圧縮手法の圧縮性能に関する新たな結果の証明である。文字列圧縮手法の性能を比較・解析する研究は文字列圧縮研究の分野で近年盛んに行われており、特に２つ目の成果は同分野で注目されていた未解決問題のひとつを解決したものである。２つ目と３つ目の成果は国際会議 SPIRE 2021 に採択されている。 ４つ目の成果は、RePair という文字列圧縮手法の圧縮性能に関する新たな結果の証明である。５つ目の成果は、デカルト木部分列照合問題と呼ばれる緩和された部分列照合問題に対するアルゴリズムの提案である。６つ目の成果は、圧縮表現された文字列上で、その文字列中に存在しない不在文字列を計算するアルゴリズムの提案である。上記３つの成果はいずれも国際会議 CPM 2022 に採択されている。, 20J11983
研究期間 2020年04月24日 - 2022年03月31日
