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

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

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