圧縮文字列上の高速パターン列挙に関する基盤技術開発

本年度は, 本研究テーマの一つの集大成として, 圧縮された文字列データから規則性をもった部分文字列を高速に計算・列挙する手法を開発した. 繰り返し構造や回文構造といった文字列の規則性の発見は文字列処理の基礎であり, また, ゲノムデータの解析などに応用出来る. 圧縮文字列処理では展開文字列長に比例する計算資源を用いないことを目標としており, そのため圧縮文字列を全て展開せずに処理しなければいけないという難しさがあるが, 解の列挙においてはさらに出力の仕方も問題になる. 単純に出力すると出力サイズに比例する時間を避ける事ができず, 今回の出力である繰り返し構造や回文構造の数は展開文字列長に比例するためである. 本手法では, 圧縮された文字列を展開する事無く処理を行い, かつ, 出力の圧縮表現を計算することでこの問題を回避した. これにより, ゲノムデータなどの大規模文字列データも, それが良く圧縮されているならば省領域かつ高速に規則性を発見することが出来る. この結果は38th International Symposium on Mathematical Foundations of Computer Science (MFCS2013)に採択され発表を行った.また, 圧縮された文字列上の組み合わせ的性質を探る研究として圧縮文字列とLyndon文字列との関連性を探った. Lyndon文字列およびそれを基にしたLyndon分解は代数学と深く関連しており古くから知られているが, 近年はアルゴリズムへの応用も注目されている. 申請者らは24th Annual Symposium on Combinatorial Pattern Matching (CPM2013)と20th Symposium on String Processing and Information Retrieval (SPIRE 2013)において圧縮文字列からLyndon分解を効率的に求めるアルゴリズムを開発した. その過程において, Lyndon分解の項数が文法圧縮サイズの下界になっているという興味深い知見を得ている.

本年度は, 本研究テーマの一つの集大成として, 圧縮された文字列データから規則性をもった部分文字列を高速に計算・列挙する手法を開発した. 繰り返し構造や回文構造といった文字列の規則性の発見は文字列処理の基礎であり, また, ゲノムデータの解析などに応用出来る. 圧縮文字列処理では展開文字列長に比例する計算資源を用いないことを目標としており, そのため圧縮文字列を全て展開せずに処理しなければいけないという難しさがあるが, 解の列挙においてはさらに出力の仕方も問題になる. 単純に出力すると出力サイズに比例する時間を避ける事ができず, 今回の出力である繰り返し構造や回文構造の数は展開文字列長に比例するためである. 本手法では, 圧縮された文字列を展開する事無く処理を行い, かつ, 出力の圧縮表現を計算することでこの問題を回避した. これにより, ゲノムデータなどの大規模文字列データも, それが良く圧縮されているならば省領域かつ高速に規則性を発見することが出来る. この結果は38th International Symposium on Mathematical Foundations of Computer Science (MFCS2013)に採択され発表を行った.また, 圧縮された文字列上の組み合わせ的性質を探る研究として圧縮文字列とLyndon文字列との関連性を探った. Lyndon文字列およびそれを基にしたLyndon分解は代数学と深く関連しており古くから知られているが, 近年はアルゴリズムへの応用も注目されている. 申請者らは24th Annual Symposium on Combinatorial Pattern Matching (CPM2013)と20th Symposium on String Processing and Information Retrieval (SPIRE 2013)において圧縮文字列からLyndon分解を効率的に求めるアルゴリズムを開発した. その過程において, Lyndon分解の項数が文法圧縮サイズの下界になっているという興味深い知見を得ている.