研究テーマ
文字列アルゴリズム
接尾辞配列・接尾辞木などのデータ構造を用いて、巨大なテキストの中からパターンを高速に発見・解析するアルゴリズムを研究しています。
- Computing maximal palindromes in non-standard matching models — Inf. Comput., 2025
- Counting Distinct (Non-)crossing Substrings — String Processing and Information Retrieval - 32nd International Symposium, SPIRE 2025, London, UK, September 8-11, 2025, Proceedings
- Text Indexing for Simple Regular Expressions — 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025, Milan, Italy, June 17-19, 2025
文字列の組合せ論
文字列に潜む繰り返し構造や周期性を組合せ論的に解析し、その性質を捉える指標(repetitiveness measure)や理論的な限界を研究しています。
- The "Runs" Theorem — SIAM J. Comput., 2017
- Computing Longest (Common) Lyndon Subsequences — Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings
- Lyndon Arrays in Sublinear Time — 31st Annual European Symposium on Algorithms, ESA 2023, Amsterdam, The Netherlands, September 4-6, 2023
- The Smallest String Attractors of Fibonacci and Period-Doubling Words — 37th Annual Symposium on Combinatorial Pattern Matching, CPM 2026, Copenhagen, Denmark, June 15-17, 2026
データ圧縮
Burrows-Wheeler変換やLZ77といった圧縮手法を対象に、圧縮率の理論的な解析や、圧縮したまま検索・解析できるアルゴリズムを研究しています。
- On Repetitiveness Measures of Thue-Morse Words — String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings
- Computing NP-Hard Repetitiveness Measures via MAX-SAT — 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, September 5-9, 2022
- Height-Bounded Lempel-Ziv Encodings — 32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024
- On the Compressiveness of the Burrows-Wheeler Transform — 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025, Milan, Italy, June 17-19, 2025