Development of Intelligent full text retrieval system based on data compression and fast string pattern matching algorithms

基于数据压缩和快速字符串模式匹配算法的智能全文检索系统开发

基本信息

批准号：
13558029
负责人：
SHINOHARA Ayumi
金额：
$ 7.17万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2003
项目状态：
已结题

项目摘要

Suffix trees and Directed Acyclic Word Graphs(DAWGs) are well-known data structures as efficient indexingstructures for strings. We focus on Compact Directed Acyclic Word Graphs(CDAWGs) which are more compact indexing structures, and showed online construction algorithms for them. We also showed an online construction algorithm for an indexing structure consists of every DAWGs for all prefixes of given strings, and proved a lower-bound of the number of states of subsequence automata accepting all subsequences of a given string. We then introduced a new implementation technique based on ternary trees for DAWGs, which balances space efficiency and search time for a large alphabet, such as Japanese texts.We proposed an inverse problem in which we infer an original string from a given unlabelled graph corresponding to the indexing structures of the string. We showed linear-time algorithms for DAWG, subsequence automata, and suffix arrays in this setting. Moreover, we succeeded to prove a tight upper-bound of the length of solutions of world equations containing one variable.Concerning with data compression, we showed a space, efficient algorithm which outputs a compact context-free grammar representing a given string, and proved its approximation ratio. We also showed a linear-time compression algorithm using longest first replacement heuristics.In order to find patterns from large database in reasonable time, we developed several algorithms for classes of generalized patterns. Especially, we proposed an efficient pattern discovery algorithm in which we allow small mismatches of the pattern with data, and verified that it is practical by a series of computational experiments.

后缀树和有向无环字图（DAWG）是众所周知的数据结构，是字符串的有效索引结构。我们专注于紧凑有向无环字图（CDAWG），它是更紧凑的索引结构，并展示了它们的在线构建算法。我们还展示了一种索引结构的在线构建算法，该索引结构由给定字符串的所有前缀的每个 DAWG 组成，并证明了接受给定字符串的所有子序列的子序列自动机的状态数下界。然后，我们为 DAWG 引入了一种基于三元树的新实现技术，该技术平衡了大型字母表（例如日语文本）的空间效率和搜索时间。我们提出了一个逆问题，其中我们从给定的未标记图中推断出原始字符串，该字符串对应于字符串的索引结构。我们在此设置中展示了 DAWG、子序列自动机和后缀数组的线性时间算法。此外，我们成功地证明了包含一个变量的世界方程解的长度的严格上限。关于数据压缩，我们展示了一种空间高效的算法，该算法输出表示给定字符串的紧凑上下文无关语法，并证明其近似比。我们还展示了一种使用最长首次替换启发式的线性时间压缩算法。为了在合理的时间内从大型数据库中找到模式，我们开发了几种针对广义模式类的算法。特别是，我们提出了一种有效的模式发现算法，其中允许模式与数据的微小不匹配，并通过一系列计算实验验证了它的实用性。