Development of Lossless Compression Model and Algorithm for Hierarchically Repetitive Data

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

本研究は，階層的な反復構造を持つデータのための可逆圧縮モデルとアルゴリズムの研究開発を目的としたものである．令和2年度は，研究課題として掲げた項目のうち，主として「対象データの特徴を捉えた効率よいアルゴリズムの研究開発」および「開発した可逆圧縮モデルとアルゴリズムの実装及び計算機実験」に取り組んだ．特に，「極大な頻出パターン」と「連」という2種類の特徴的な反復構造に着目し，これらをデータ中から効率よく抽出可能な圧縮アルゴリズムの研究開発に注力した．「極大な頻出パターン」とは，データ中に繰り返し出現する部分のうち極大なものを指す．極大な頻出パターンは，その内部により小さな頻出パターンを内包するが，そうした小さなパターンに断片化することなく，極大な括りで一つのパターンと捉え抽出することで，圧縮性能を大きく向上させることができる．しかしながら，従来の圧縮手法では，こうした極大な頻出パターンを効率よく抽出することができなかった．「連」とは，同じパターンが連続して出現する，データ中の部分を指す．この連についても，従来手法では，断片化せずに効率よく捉え抽出することができず，そのことで潜在的な圧縮性能を引き出せずにいた．こうした課題を踏まえ，申請者は「極大な頻出パターン」と「連」を効率よく抽出可能な可逆圧縮アルゴリズムを開発した．その過程で，従来手法で可逆圧縮モデルとして用いられてきた文脈自由文法を拡張したモデルを取り入れ，圧縮モデル研究の面からも成果を得た．さらに，開発したアルゴリズムの実装及び計算機実験を行い，提案アルゴリズムの有効性を実験的に確認した．