Data Compression: theoretical and practical approaches to the smallest grammar problem

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

本研究は，可逆的データ圧縮の代表例である文法圧縮に対して，理論と応用の両面から取り組んでいる．今年度は関連する文字列処理に関して様々な進展があった．文字の置換を許容して構造の一致を見つけ出すパラメータ化パターン照合問題に関して2つのアプローチを行った．まず，検索を高速化するために，有向非巡回文字列グラフ(DAWG)を拡張した索引構造を新たに提案し，それをテキストから効率よく構築するアルゴリズムを開発した．このアルゴリズムはテキストの末尾に文字を付加した場合にも索引の更新が容易なオンライン型となっている．またこの索引構造を活用することで，検索の対象となるパターンの前後に新たな文字列を付加した場合にその変更に追随しながら効率よくパラメータ化照合ができることを示した．第2のアプローチとして，可逆的データ圧縮で重要な働きをするBurrow-Wheeler変換(BW変換)について，パラメータ化に拡張したBW変換を効率よく行えるアルゴリズムを開発した．このアルゴリズムもオンライン型である．さらに，パラメータ化照合や順序保存照合を含む，より一般化した枠組みにおいて，高速に検索を行うことのできる汎用の並列照合アルゴリズムを開発することに成功した．一方，通常の文字列照合に用いられる索引構造であるポジションヒープに関して，索引構造から元の文字列を復元する「逆問題」の解析に取り組んだ．索引構造に文字ラベルや頂点番号がすべて付与されている場合だけではなく，それらが隠蔽された種々の設定においても，効率よく復元が行えることを示した．