Lyndon文字列による反復性指標解析

文字列データの圧縮や，圧縮された文字列データを圧縮サイズに依存した計算量で何らかの処理を行う技術は，重要な文字列処理技術の一つであり，これまでに非常に多く研究がなされている．特に，繰り返し構造を多く含む文字列に対して有用な辞書式圧縮や関連する様々な圧縮法が，どの程度文字列中の繰り返し構造を捉えているかを明らかにするため，様々な圧縮法に基づいた反復性指標に関する理論的な解析が注目を集めている．本研究課題は，文字列の圧縮と直接的に関係のない Lyndon 文字列や関連する文字列構造との関係を導入および明らかにすることで，文字列の反復性をどのように捉えることができるかという問いに挑戦する課題である．また，これらの知見を利用することで様々な問題に対する文字列アルゴリズムの開発を推し進める．2年目にあたる2022年度では，査読付き国際ジャーナルに4報，査読付き国際会議に2報の研究成果を発表済みである．うち3報が文字列組合せ論に関する成果であり，うち4報が文字列アルゴリズムおよびデータ構造に関する成果をまとめたものである．本研究課題に最も深く関係する成果として，反復分解のアルゴリズムおよび組合せ的性質に関する成果が挙げられる．ここでの反復とは，テキスト中の部分文字列のうち，ある文字列の2回以上の有理数回の繰り返しで表される文字列のことを指す．本成果では，テキストの最大および最小サイズの反復分解を高速に計算するアルゴリズムに加え，そのような反復分解に関する組合せ的性質についてフィボナッチ文字列を用いて議論を行っている．特に後者の成果については，文字列の反復性について追求する本研究課題において有用な知見を与えていると考えられる．

文字列データの圧縮や，圧縮された文字列データを圧縮サイズに依存した計算量で何らかの処理を行う技術は，重要な文字列処理技術の一つであり，これまでに非常に多く研究がなされている．特に，繰り返し構造を多く含む文字列に対して有用な辞書式圧縮や関連する様々な圧縮法が，どの程度文字列中の繰り返し構造を捉えているかを明らかにするため，様々な圧縮法に基づいた反復性指標に関する理論的な解析が注目を集めている．本研究課題は，文字列の圧縮と直接的に関係のない Lyndon 文字列や関連する文字列構造との関係を導入および明らかにすることで，文字列の反復性をどのように捉えることができるかという問いに挑戦する課題である．また，これらの知見を利用することで様々な問題に対する文字列アルゴリズムの開発を推し進める．2年目にあたる2022年度では，査読付き国際ジャーナルに4報，査読付き国際会議に2報の研究成果を発表済みである．うち3報が文字列組合せ論に関する成果であり，うち4報が文字列アルゴリズムおよびデータ構造に関する成果をまとめたものである．本研究課題に最も深く関係する成果として，反復分解のアルゴリズムおよび組合せ的性質に関する成果が挙げられる．ここでの反復とは，テキスト中の部分文字列のうち，ある文字列の2回以上の有理数回の繰り返しで表される文字列のことを指す．本成果では，テキストの最大および最小サイズの反復分解を高速に計算するアルゴリズムに加え，そのような反復分解に関する組合せ的性質についてフィボナッチ文字列を用いて議論を行っている．特に後者の成果については，文字列の反復性について追求する本研究課題において有用な知見を与えていると考えられる．