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

点击翻译按钮获取中文摘要

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.