高度反復データに対する圧縮性指標の研究と圧縮情報処理への応用

近年，計算機性能やセンシング技術の向上，通信ネットワークの発達などを背景に，計算機上のデータが爆発的に増加している．これらのデータを有効に保存・活用するためには圧縮技術の利用が不可欠だが，一般に可逆圧縮の限界として知られるシャノンの情報量は，繰り返しを多く含むデータの圧縮可能性を適切に捉えられていない．例えば，同一種のDNA配列は個体間で数パーセントの差異しかないため，共通する部分配列を参照しあうことで大幅な圧縮が可能になるが，各塩基の頻度情報のみを利用するエントロピー符号ではほとんど圧縮することができない．近年，このような繰り返しを多く含む高度反復データを対象とした圧縮手法が盛んに研究されている．本研究では，高度反復データが有する圧縮可能性を適切に捉える圧縮性指標に関する研究および圧縮情報処理技術への応用に関する研究を行う．2022年度は，連長圧縮された文字列上で文字列複雑度に基づいた圧縮性指標を効率的に計算する手法について研究を行い，成果をまとめた論文はInternational Symposium on String Processing and Information Retrieval (SPIRE) 2022に採択され発表を行った．現在まで様々な圧縮性指標が提案されているが，文字列複雑度に基づいた圧縮性指標は，効率的に計算できる点，文字列の局所的な変化に対して頑健である点など多くの良い性質を持つ．さらに，文字列複雑度に基づいた圧縮性指標が分かると，そのサイズに基づいた索引構造が効率的に計算できることが知られている．今回の研究成果により，この索引構造がより効率的に構築できるようになることが期待できる．

近年，計算機性能やセンシング技術の向上，通信ネットワークの発達などを背景に，計算機上のデータが爆発的に増加している．これらのデータを有効に保存・活用するためには圧縮技術の利用が不可欠だが，一般に可逆圧縮の限界として知られるシャノンの情報量は，繰り返しを多く含むデータの圧縮可能性を適切に捉えられていない．例えば，同一種のDNA配列は個体間で数パーセントの差異しかないため，共通する部分配列を参照しあうことで大幅な圧縮が可能になるが，各塩基の頻度情報のみを利用するエントロピー符号ではほとんど圧縮することができない．近年，このような繰り返しを多く含む高度反復データを対象とした圧縮手法が盛んに研究されている．本研究では，高度反復データが有する圧縮可能性を適切に捉える圧縮性指標に関する研究および圧縮情報処理技術への応用に関する研究を行う．2022年度は，連長圧縮された文字列上で文字列複雑度に基づいた圧縮性指標を効率的に計算する手法について研究を行い，成果をまとめた論文はInternational Symposium on String Processing and Information Retrieval (SPIRE) 2022に採択され発表を行った．現在まで様々な圧縮性指標が提案されているが，文字列複雑度に基づいた圧縮性指標は，効率的に計算できる点，文字列の局所的な変化に対して頑健である点など多くの良い性質を持つ．さらに，文字列複雑度に基づいた圧縮性指標が分かると，そのサイズに基づいた索引構造が効率的に計算できることが知られている．今回の研究成果により，この索引構造がより効率的に構築できるようになることが期待できる．