Development of Intelligent Full-text Search System using Efficient Pattern Matching Algorithms on Compressed Data

利用压缩数据的高效模式匹配算法开发智能全文搜索系统

• 批准号: 10558047
• 负责人: SHINOHARA Ayumi
• 金额: $ 6.66万
• 依托单位: KYUSHU UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B).
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-10558047/
• 关键词: Pattern matching; Data compression; Compressed pattern matching; Data mining; Machine learning; Subsequence automaton; Straight-line program; 文字列照合; パタンマッチング; 全文検索; 計算学習理論; 圧縮パタン照合; BPE圧縮; Lempel-Ziv圧縮

From a theoretical point of view on compressed pattern matching, we introduced a unified frame work, called Collage System, for various dictionary-based data compression methods. We developed both Knuth-Morris-Pratt type and Boyer-Moore type pattern matching algorithms for Collage Systems. We adopted these algorithms for Byte-Pair-Encoding compression method, that yields the fastest compressed pattern matching algorithm in practice. Multiple pattern matching and approximate string matching were also successfully dealt with Collage Systems. We also applied the method for Sequitur, that is another hopeful a compression program, and verified its performance. Moreover, we studied an efficient fully compressed pattern matching for balanced straight-line programs, where not only text strings but also pattern strings are compressed. We also developed an online algorithm that constructs a subsequence automaton from given set of strings, that accepts all subsequences of any string in the set. The algorithm is the fastest, and we verified that it is quite useful to accelerate a knowledge discovery system. On the other hand, concerning with knowledge discovery from database, we studied on the learnability of transformation rules of trees from examples, and searching optimal association rules of words from large text databases. Journal of Discrete Algorithms, 1(1), 2000

从压缩模式匹配的理论角度来看，我们为各种基于字典的数据压缩方法引入了一个统一的框架，称为拼贴系统。我们为拼贴系统开发了 Knuth-Morris-Pratt 型和 Boyer-Moore 型模式匹配算法。我们采用这些算法进行字节对编码压缩方法，产生实践中最快的压缩模式匹配算法。拼贴系统还成功地处理了多重模式匹配和近似字符串匹配。我们还应用了另一个有希望的压缩程序Sequitur的方法，并验证了其性能。此外，我们研究了一种用于平衡直线程序的高效完全压缩模式匹配，其中不仅压缩文本字符串，而且还压缩模式字符串。我们还开发了一种在线算法，可以根据给定的字符串集构造子序列自动机，该子序列自动机接受该集中任何字符串的所有子序列。该算法是最快的，我们验证了它对于加速知识发现系统非常有用。另一方面，针对数据库知识发现，我们研究了树的变换规则从实例中的可学习性，以及从大型文本数据库中搜索单词的最佳关联规则。离散算法杂志，1(1)，2000

项目成果

Y.Shibata et al.: "Speeding Up Pattern Matching by Text Compression"Proc. 4th Italian Conf.on Algorithms and Complexity. LNCS1767. 306-316 (2000)

Y.Shibata 等人：“通过文本压缩加速模式匹配”Proc。

H.Sakamoto et al.: "Identification of tree translation rules from examples"Proc.5th International Colloquium on Grammatical Inference. LNAI1891. 240-255 (2000)

H.Sakamoto 等人：“从示例中识别树翻译规则”Proc.5th International Colloquium on Grammatical Inference。

M.Miyazaki,A.Shinohara and M.Takeda: "An Improved Pattern Matching Algorithm for Strings in terms of Straight-line Programs"Journal of Discrete Algorithms. 1(1). (2000)

M.Miyazaki、A.Shinohara 和 M.Takeda：“一种改进的直线程序字符串模式匹配算法”离散算法杂志。

M.Takeda,Y.Shibata,T.Matsumoto,T.Kida,A.Shinohara,S.Fukamachi,T.Shinohara and S.Arikawa: "Speeding up string pattern matching by text compression : The dawn of a new era"情報処理学会論文誌. 42(3). (2001)

M.Takeda、Y. Shibata、T. Matsumoto、T. Kida、A. Shinohara、S. Fukamachi、T. Shinohara 和 S. Arikawa：“通过文本压缩加速字符串模式匹配：新时代的黎明”信息日本加工协会杂志42(3) (2001)。

M. Yamasaki et al.: "Discovering characteritic patterns from collections of classical Japanese Poems" Prof. 1st Int. Conf. on Discovery Science. LNAI1532. 129-140 (1998)

M. Yamasaki 等人：“从日本古典诗歌集中发现特征模式”教授 1st Int。