Development of efficient machine discovery system based on data compression and pattern matching

我们研究了以下三个项目来构建高效的机器发现系统。（1）文本压缩和模式匹配。重点研究了基于语法的压缩，并开发了高效的压缩算法。利用它们，我们解决了压缩模式匹配问题，并获得了有效的算法。（2）文本和半结构化文本的高效处理。我们开发了文本索引结构来加速文本处理。作为用于子串模式匹配的索引结构，后缀树和DAWG是公知的。本文以CDAWG为研究对象，设计了一种CDAWG的在线线性时间构造算法。然后，我们设计了一个CDAWG与滑动窗口，它有一个应用程序的文本数据压缩的构造算法。我们还提出了一种新的索引结构，为大型字母（如日语文本），并证明了其效率的实验。另一方面，我们分析了子序列自动机的性质，子序列自动机是子序列模式匹配的索引结构，以加速子序列模式发现。本文成功地解决了词后缀树的在线线性时间构造问题，提出了一种基于位并行技术的快速树模式匹配算法，有效地处理了半结构化文本数据。（3）模式发现与信息提取：针对不同类型的模式，提出了有效的模式发现算法。我们将这些技术集成到一个知识发现系统中，并将其应用于语言数据和文学数据，与语言学家和文学学者合作，取得了良好的效果。

We studied the following three items to build efficient machine discovery systems.(1)Text compression and pattern matching.We focused on grammar-based compression and develop efficient compression algorithms. Using them we addressed the compressed pattern matching problem and obtained efficient algorithms.(2)Time-efficient processing of text and semi-structured text.We developed text index structures to accelerate text processing. As index structures for substring pattern matching, suffix trees and DAWGs are well-known. We focus on CDAWG which is a hybrid structure of them, and devised an online linear-time construction algorithm for CDAWGs. We then devised a construction algorithm for CDAWGs with sliding windows, which has an application to text data compression. We also proposed a new index structure for large alphabets (such as Japanese texts), and proved its efficiency experimentally. On the other hand, we analyze the properties of subsequence automata which are index structures for subsequence pattern matching to accelerate subsequence pattern discovery. We successfully gave a solution to the problem of online linear-time construction of word suffix trees, which has been open over 10 years.We developed a fast tree pattern matching algorithm based on bit-parallel technique for efficient processing of semi-structured text data.(3)Pattern discovery and information extraction.We developed efficient pattern discovery algorithms for various classes of patterns. We implemented them and estimated their performances experimentally.We integrated the techniques developed into a knowledge discovery system, applied it to linguistic data and literary data and then obtained good results in corporation with linguists and literary scholars.