权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

基于数据压缩和模式匹配的高效机器发现系统的开发

基本信息

批准号：
15300049
负责人：
TAKEDA Masayuki
金额：
$ 9.22万
依托单位：
KYUSHU UNIVERSITY
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

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.

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

项目成果

期刊论文数量（112）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

DEVELOPING DYNAMIC GAITS FOR FOUR LEGGED ROBOTS

DOI：
发表时间：
2003
期刊：
影响因子：
0
作者：
Makoto Toyomasu;A. Shinohara
通讯作者：
Makoto Toyomasu;A. Shinohara

On-line Linear-time Construction of Word Suffix Trees

词后缀树的在线线性时间构建

DOI：
发表时间：
2006
期刊：
Lecture Note in Computer Science(In Proc.17^<th> Annual Symposium on Combinatorial Pattern Matching) 4009
影响因子：
0
作者：
Shunsuke Inenaga;他1名
通讯作者：
他1名

The Size of Subsequence Automaton

子序列自动机的大小

DOI：
发表时间：
2005
期刊：
Theoretical Computer Science Vol.341 Issue 1-3
影响因子：
0
作者：
Kazuhito Hagio;Shuichi Mitarai;Akira Ishino;and Masayuki Takeda.;Hideo Bannai 他3名;Hisashi Tsuji他2名;Shunsuke Inenaga 他2名;Zdenek Tronicek 他1名
通讯作者：
Zdenek Tronicek 他1名

部分構造を統合的に活用するためのXMLデータ管理システム.

用于集成使用子结构的 XML 数据管理系统。

DOI：
发表时间：
2006
期刊：
情報処理学会第68回全国大会講演論文集 (印刷中)
影响因子：
0
作者：
Toshiyuki Kochi;et al.;Jun Inoue et al.;Jun Inoue et al.;Hayato Kobayashi et al.;Shunsuke Inenaga et al.;福田智子;福田智子他;今井明他;Jun Inoue et al.;Jun Inoue et al.;Hayato Kobayashi et al.;黒木香他;杉本典子他
通讯作者：
杉本典子他

<恵慶百首>秋部試注.

<Kekei Hyakushu>秋部预购。