巨大データからの知識発見を可能にする圧縮文字列処理基盤技術

压缩字符串处理平台技术，实现海量数据知识发现

• 批准号: 13J04937
• 负责人: 後藤 啓介
• 金额: $ 0.64万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2013
• 资助国家: 日本
• 起止时间: 2013 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13J04937/
• 关键词: アルゴリズム; 圧縮文字列処理

LZ77圧縮に着目し, LZ77圧縮を省領域で計算するアルゴリズムの開発を行った. LZ77圧縮は理論的にも実用的にも圧縮率の良い圧縮法であることが知られており, 圧縮用途以外にも, 連の解析や周期の発見など文字列解析に幅広く応用される, 汎用かつ知識発見において重要な位置づけにある圧縮データ構造である. そのような応用を考える上でボトルネックとなるのがLZ77圧縮の計算にかかる時間と領域であり, 省領域で動作する線形時間アルゴリズムの開発が求められている. LZ77圧縮は入力テキスト全体に渡る繰り返し構造を計算する必用があるため, 線形時間アルゴリズムの開発にはテキストの索引構造とその補助データ構造を使うことが一般的であり, より省領域なアルゴリズムの開発はこれらのデータ構造の領域を如何に削減するかが課題であった. 筆者は計算に必要な使用領域の削減に取り組み, NlogN+0(σlog N) bits領域を使用する線形時間アルゴリズムを提案した, ここでNは入力テキストサイズ, σはアルファベットサイズである. 先行研究で最も省領域な2N log Nbitsを使用する線形時間アルゴリズムKKP2と比較すると, アルファベットサイズが小さい場合, 提案手法はKKP2に比べほぼ半分の領域で動作し, 大きな改善に成功している. 計算機実験によりKKP2と新手法の実行時間を比較した場合, 新手法は領域を半分程度に抑えた事による計算の複雑さが増したにも関わらず, 実行時間はKKP2の2倍ほどの実行時間の増加に留まっているとの結果が得られた.

为了关注LZ77压缩，我们开发了一种算法，该算法在低范围区域中计算LZ77压缩。 LZ77压缩是一种压缩方法，在理论和实际术语中均具有良好的压缩率，并且是一种压缩数据结构，广泛应用于诸如连续分析和周期发现之类的字符串分析，并且是知识发现中的通用和重要位置。在考虑此类应用时，需要计算LZ77压缩所需的时间和面积，以及在低范围区域内运行的线性时间算法的开发。由于LZ77压缩需要计算整个输入文本中的迭代结构，因此通常使用文本索引结构及其辅助数据结构来开发线性时间算法，并且还需要更换算法的发展是如何减少这些数据结构面积的。作者努力减少计算所需的使用面积，我们建议使用NLOGN+0（σlogn）块域提出了线性时间算法，其中n是输入文本大小，σ是字母表大小。与使用2N日志NBIT的KKP2相比，在先前研究中节省的最大节省是，当字母大小很小时，与KKP2相比，所提出的方法几乎运作该区域的一半，并且取得了很大的改进。当将新方法的执行时间与新方法进行比较时，我们发现，由于减少面积约为一半而导致计算的复杂性增加，但新方法的执行时间仅是KKP2的两倍。

项目成果

Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets

• DOI: 10.1109/dcc.2014.62
• 发表时间: 2014-03
• 期刊: 2014 Data Compression Conference
• 作者: Keisuke Goto;H. Bannai