Development of Lossless Compression Model and Algorithm for Hierarchically Repetitive Data

分层重复数据无损压缩模型和算法的开发

基本信息

批准号：
20J14475
负责人：
古谷勇
金额：
$ 1.09万
依托单位：
Hokkaido University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-24 至 2022-03-31
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20J14475/
关键词：
可逆圧縮アルゴリズム

项目摘要

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

本研究的目的是研究和开发具有分层重复结构的数据的无损压缩模型和算法。 2020年，我们的研究课题主要是“捕捉目标数据特征的高效算法的研究与开发”和“所开发的可逆压缩模型和算法的实现和计算机实验”。我们特别关注两种类型的特征重复结构：“极其频繁的模式”和“运行”，并专注于研究和开发能够有效地从数据中提取这些特征的压缩算法。 “极频繁模式”是指数据中重复出现的部分的最大数量。极其频繁的模式中包含较小的频繁模式，但是通过将它们提取为单个模式而不将它们分割成更小的模式，可以大大提高压缩性能。然而，传统的压缩方法无法有效地提取这种极其频繁的模式。 “串”是指连续出现相同模式的数据部分。传统方法无法有效地捕获和提取该序列而不对其进行碎片化，因此无法利用潜在的压缩性能。鉴于这些问题，申请人开发了一种可逆压缩算法，可以有效地提取“极其频繁的模式”和“游程”。在此过程中，我们采用了扩展上下文无关语法的模型，该模型在传统方法中被用作可逆压缩模型，并从压缩模型研究方面获得了成果。此外，我们实现了所开发的算法并进行了计算机实验，以通过实验证实所提出算法的有效性。