パターン圧縮に基づく機械発見における計算限界の打破

基于模式压缩突破机器发现的计算限制

• 批准号: 09J01104
• 负责人: 丸山 史郎
• 金额: $ 0.9万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09J01104/
• 关键词: テキストデータ圧縮; 文法変換に基づく圧縮; 圧縮データ構造; 文字列パターン検索; データ圧縮; 文字列パターン照合; 情報検索

冗長度の高いテキストデータのための軽量なオンライン圧縮アルゴリズムを提案した.このアルゴリズムの特徴として,オンラインで動作するため,次々に追加されていくデータを蓄積することなく逐次的に圧縮することが可能である.また,特別なデータ構造を使わずにデータの局所的な整数演算のみで共通の部分文字列を圧縮できるため,テキストが極端に圧縮可能な場合は十分に少ない主記憶領域で実行できる.実験の結果,重複部分を多く含む実データを約10分の1から1000分の1以下にまで圧縮可能であり,文字列索引を利用しているLZMA圧縮法と比較して約10分の1から100分の1以下の主記憶領域で高速に動作することを確認した.文法圧縮テキスト中の部分文字列の高速な参照のための索引付けに関する研究を行った.圧縮テキストを復元せずに元のテキストのように扱うためには,圧縮テキスト上でランダムアクセスを行い,任意の部分文字列を高速に参照できなければならない.本研究では,そのような操作を可能にする文法圧縮テキストのための索引付け手法を提案した.この索引付けは,索引領域も圧縮テキストの圧縮率に応じて圧縮されるという特徴を持っており,極端に圧縮されている圧縮データに対しても,その索引領域は十分に小さい.また,どんな位置にある部分文字列でも一定の時間で抽出できることが保障される.様々なコーパスに対する実験の結果,元の圧縮テキストサイズの1.2倍から1.5倍程度の主記憶領域で1秒間に500万から700万文字の部分文字列を参照できることを確認した.文法圧縮に基づく圧縮索引構造に関する研究を行った.Edit Sensitive Parsingという手法により圧縮された文法データの特性を使い,入力パターンを圧縮することで圧縮テキスト中の高速な検索が可能であり,本研究では,パターンの出現回数,出現位置,任意の部分文字列の報告を行えるように拡張し,実験による評価を行った.

我们提出了一种针对高冗余文本数据的轻量级在线压缩算法。该算法的一个特点是在线运行，因此可以对逐个添加的数据进行顺序压缩，而不会累积数据。此外，还可以压缩公共子串。仅通过对数据进行本地整数运算而不使用特殊的数据结构，因此如果文本具有极高的可压缩性就足够了。它可以在几分钟内用更少的主存空间执行。实验结果表明，可以将包含许多重复部分的真实数据从大约1/10压缩到小于1/1000，并且使用字符串索引的LZMA压缩确认主内存区域比传统方法小大约 10 到 100 倍，我采用了压缩文本。为了像对待原始文本一样对待文本而不恢复它，需要对压缩文本进行随机访问并高速引用任意子串。我们提出了一种语法压缩文本的索引方法。这种索引具有以下特点：索引区也按照压缩文本的压缩率进行压缩，即使对于数据文件来说，索引区域也足够小。这也保证了在固定的时间内可以提取出任意位置的子串。通过对各种语料库的实验结果，我们发现原始压缩文本的大小为1.2我们确认每秒可以引用 5 至 700 万个字符的子串，而主内存区域大约是原来的 1.5 倍。我们对基于语法压缩的压缩索引结构进行了研究。编辑通过利用使用“敏感解析”方法压缩的语法数据的特性，可以通过压缩输入模式在压缩文本中执行高速搜索，我们将其扩展为允许列报告，并通过实验对其进行了评估。

项目成果

Edit Sensitive Parsingを用いた文法圧縮による効率的な索引構造

使用编辑敏感解析进行语法压缩的高效索引结构

• 发表时间: 2010
• 作者: 丸山史郎

An Online Algorithm for Lightweight Compression of Highly Repetitive Text

一种高重复文本轻量级压缩的在线算法

• 发表时间: 2011
• 作者: Shirou Maruyama; Masaya Nakahara
• 通讯作者: Masaya Nakahara

Context-Sensitive Grammar Transform : Compression and Pattern Matching

上下文相关语法转换：压缩和模式匹配

• 发表时间: 2010
• 作者: Shirou.Maruyama; et al.
• 通讯作者: et al.

文法型圧縮法の全二分木表現による符号化とランダムアクセス手法の提案

使用语法型压缩方法的全二叉树表示的编码和随机访问方法的建议

• 发表时间: 2011
• 作者: 丸山史郎