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.

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