研究室概要

本研究室では，テキスト，時系列，数列，ラベル付き木・グラフ，２次元列などの，いわゆるシーケンシャルなデータを「文字列」と総称し，文字列データを超高速かつ省領域に処理するアルゴリズムの理論研究を行っています。KMP法，接尾辞木，LZ圧縮法などの基礎的アルゴリズムが提案された1970年代から今日まで，文字列を対象としたアルゴリズムは，理論計算機科学の最重要分野の１つであり続けています。実世界においても，文字列アルゴリズムは，情報検索やデータ圧縮のコア技術として幅広く採用され，また近年盛んな競技プログラミングにおいても，文字列処理に関する課題が頻出するなど，注目を集めています。我々は，文字列の数理的性質を探求する「文字列組合せ論」と，最先端の「アルゴリズム・データ構造」技術を融合させることによって，大規模シーケンシャルデータの効率的処理を実現します。

• 研究紹介ポスター 　       

 Strings are concepts that generalize sequential data such as text, time series, labeled trees/graphs, and 2D arrays. Our research interests are in designing fast and space-efficient algorithms for processing strings, with particular emphasis on their theoretical perspectives. Since the discovery of classical algorithms including KMP, suffix trees, and LZ compression, string algorithmics has been one of the most important sub-fields in theoretical computer science. Also in the real world, string algorithms are commonly utilized as core building blocks of information retrieval systems and data compression programs. Further, string-related problems are commonly seen in competitive programming contests. Our approach for tackling massive sequential data is first to reveal mathematical properties of strings using the theory of "word combinatorics”, and then to develop advanced "algorithms and data structures” techniques.