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
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-13558029/
• 关键词: Pattern matching algorithm; Data compression; Full-text retrieval system; Knowledge discovery; Optimal pattern discovery; Suffix tree; Indexing structure; Machine learning

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)这一更为紧凑的索引结构，并给出了在线构造算法。我们还给出了一个由每个Dawgs组成的索引结构的在线构造算法，并证明了接受给定串的所有子序列的子序列自动机的状态数的下界。然后介绍了一种新的基于三叉树的Dawgs实现技术，该技术平衡了空间效率和搜索时间对大字母表(如日语文本)的影响，提出了一个反问题，即从给定的未标记图中推断出与字符串的索引结构相对应的原始字符串。在这种情况下，我们展示了Dawg、子序列自动机和后缀数组的线性时间算法。此外，我们成功地证明了一元世界方程的解的长度的一个紧上界，结合数据压缩，我们给出了一个空间高效的算法，该算法输出一个表示给定字符串的紧致上下文无关文法，并证明了它的逼近比。为了在合理的时间内从大型数据库中发现模式，我们提出了几种针对广义模式类的算法。特别是，我们提出了一种高效的模式发现算法，允许模式与数据的小失配，并通过一系列的计算实验验证了该算法的实用性。

项目成果

Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa: "Compact Directed Acyclic Word Graphs for a Sliding Window"Lecture Notes in Computer Science. 2476(SPIRE2002). 310-324 (2002)

Shunsuke Inenaga、Ayumi Shinohara、Masayuki Takeda、Setsuo Arikawa：“滑动窗口的紧凑有向非循环字图”计算机科学讲义。

Masahiro Hirao, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa: "A practical algorithm to find the best episode patterns"Lecture Notes in Artificial Intelligence. 2226(DS2001). 435-440 (2001)

Masahiro Hirao、Shunsuke Inenaga、Ayumi Shinohara、Masayuki Takeda、Setsuo Arikawa：“寻找最佳剧集模式的实用算法”人工智能讲义。

S.Inenaga et al.: "Compact Directed Acyclic Word Graphs for a Sliding Window"Lecture Notes in Computer Science. 2476. 310-324 (2002)

S.Inenaga 等人：“滑动窗口的紧凑有向非循环字图”计算机科学讲义。

Masayuki Takeda et al.: "Discovering Most Classificatory Patterns for Very Expressive Pattern Classes"Lecture Notes in Computer Science. 2843. 486-493 (2003)

Masayuki Takeda 等人：“发现极具表现力的模式类的大多数分类模式”计算机科学讲义。

Takuya Kida, Tetsuya Matsumoto, Y.Shibata, Masayuki Takeda, Ayumi Shinohara, Setsuo Arikawa: "Collage system : A unifying framework for compressed pattern matching"Theoretical Computer Science. Vol.298, Isse 1. 253-272 (2003)

Takuy​​a Kida、Tetsuya Matsumoto、Y.Shibata、Masayuki Takeda、Ayumi Shinohara、Setsuo Arikawa：“拼贴系统：压缩模式匹配的统一框架”理论计算机科学。