ストリーム処理のための文字列組合せ論

点击翻译按钮获取中文摘要

文字列の組合せ的性質の究明を目標に，文字列の特徴的な分解構造に着目し研究を行った．本研究では，文字列の反復分解，LZ77分解，そしてLyndon分解の3つの分解について以下に説明する二つの主な成果を得ている．一つ目は反復分解についての成果である．文字列の反復分解とは，文字列を反復とよばれる繰り返し構造の列への分解のことをいう．繰り返し構造は，文字列の特徴を捉える指標として最も基本的な構造の一つである．近年，様々な繰り返し構造による分解を考え，それらを計算する効率的なアルゴリズムの研究などの成果が公表されている．一つの文字列における反復分解は一般に複数存在する．本研究成果では，与えられた文字列の反復分解のサイズ（分解の項の数）が最大および最小となる反復分解を効率的に計算するアルゴリズムを提案した．本研究成果は，国際会議PSC 2016 に採択され発表済みである．さらに，反復分解とフィボナッチ文字列とよばれる特徴的な文字列との関係について新たな知見を得ており，公表に向けて準備中である．二つ目の成果では，LZ77分解とLyndon分解のサイズの関係を示した．LZ77分解は，理論，実用の両面から見ても良い圧縮率として知られるLZ77圧縮のもとになっている分解であり，そのような観点から，盛んに研究が行われている．一方で，Lyndon分解は文字列の辞書式順序に基づいた分解であり，近年その応用に関する研究が注目を集めている．LZ77分解は圧縮表現であるのに対し，Lyndon分解は圧縮表現ではないが，どちらの分解も最小文法のサイズの下界になっていることが知られており，文法圧縮分野において重要な指標である．本研究成果は，二つの分解に初めて直接的な関係を与えた結果である．また本研究成果は，国際会議STACS 2017 に採択され発表済みである．