Speedup of Text Database by Data Compression

通过数据压缩加速文本数据库

• 批准号: 07558159
• 负责人: SHINOHARA Takeshi
• 金额: $ 2.37万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (A)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 1997
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07558159/
• 关键词: Information Retrieval; Sequential Pattern Matching; Data Compression; Text Database

The objective of this research is to establish a speedup method for sequential pattern matching by data compression and demonstrate its availability in text database.We design a pattern matching machine for compressed data by Huffman codes without decoding. In the experiment on this algorithm, although the effect of this method depends on the characteristics of data, the text size and the response time of searching are reduced to 60% and 70%, respectively, for English text.We also design a similar technique for new compression scheme, called Byte-Pair-Encoding (BPE,for short). This technique compresses English text to around 50% and reduces search time to 60%. BPE is basically a fixed length code, and therefore compresses text by BPE is efficiently distributed to processors in parallel environment.

为了建立一种基于数据压缩的序列模式匹配加速方法，并证明其在文本数据库中的有效性，本文设计了一个无需解码的霍夫曼编码压缩数据的模式匹配机。在对该算法的实验中，虽然该方法的效果取决于数据的特性，但对于英文文本，文本大小和搜索响应时间分别减少了60%和70%。这项技术将英文文本压缩到50%左右，并将搜索时间减少到60%。BPE基本上是一个固定长度的代码，因此，BPE压缩文本有效地分布到并行环境中的处理器。

项目成果

H.Arimura, H.Ishizaka, T.Shinohara: "Learning unions of tree patterns using queries" Theretical Computer Science (Netherlands). 47-62 (1997)

H.Arimura、H.Ishizaka、T.Shinohara：“使用查询学习树模式的并集”理论计算机科学（荷兰）。

宮崎哲司: "圧縮された日本語テキストのためのパターン照合機械の設計" 情報処理学会第51回全国大会講演論文集. 4. 239-240 (1995)

Tetsushi Miyazaki：“压缩日语文本的模式匹配机的设计”日本信息处理学会第 51 届全国会议论文集 4. 239-240 (1995)。

N,Harada, S.Arikawa, H.Ishizaka: "A class of elementary formal systems that has an efficient parsing algorithm" Information Modelling and knowledge Bases, VIII,IOS Press. 89-101 (1997)

N，Harada，S.Arikawa，H.Ishizaka：“一类具有高效解析算法的基本形式系统”信息建模和知识库，VIII，IOS Press。

有村博紀,渡木厚,下薗真一: "Maximum agreement problem for word association patterns" 電子情報通信学会コンピュテーション研究会. 92-102 (1997)

Hironori Arimura、Atsushi Wataki、Shinichi Shimozono：“单词关联模式的最大一致性问题”IEICE 计算研究小组。

山口美千代: "複数文字列パターンによるアミノ酸配列からのタンパク質モティーフの発見" 情報処理学会研究報告,情報学基礎. No.38. 33-40 (1995)

Michiyo Yamaguchi：“使用多个字符串模式从氨基酸序列中发现蛋白质基序”日本信息处理学会研究报告，信息学基础第 38 期 33-40（1995 年）。