データ圧縮に基づく高速テキストマイニング

基于数据压缩的快速文本挖掘

• 批准号: 13780248
• 负责人: 竹田 正幸
• 金额: $ 1.54万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13780248/
• 关键词: データ圧縮; 機械発見; 類似性指標; パターン発見; 計算量; 索引; 圧縮と発見; パターン照合

本研究では,「データ圧縮に基づく高速テキストマイニング」という研究課題を掲げ,以下の3つの研究項目について研究を進めた。(A)文字列処理に基づく知識発見手法の開発。(B)文字列データ圧縮と知識発見。(C)知識発見処理の高速化のための基礎技術開発。(A)については,国文学研究あるいは音楽情報処理において用いることのできる類似性指標を,本研究で導入した形式的体系であるSRSに沿って,実際に定義し,実装して有効性を検証した。また,本研究で開発したパタン発見アルゴリズムを,ゲノム情報に適用し,生物学的知見を得ることに成功した。(B)については,代表的索引構造であるDAWGに基づくLempel-Ziv圧縮法の新しい実装法を開発した。また,圧縮テキストを表す形式的体系として本研究で導入したコラージュシステムを対象とし,この形式で表された入力に対して編集距離を求める効率的アルゴリズムを開発した。この手法により,相同配列検索の高速化が期待できる。(C)については,テキスト索引方式の研究を集中して行い,DAWGという索引構造をもとにした新しい索引構造であるMASDAWGを開発・実装し,この構造を用いることで,長年の課題であった「機械学習システムBONSAIで正規パタンを扱えるようにすること」に成功した。これによって,従来は事実上不可能であった計算を実時間内に終了することができるようになり,塩基配列やアミノ酸配列からのより高度な知識発見処理が可能となった。さらに(C)に関して,半構造テキストデータからの発見が重要であるとの認識に立ち,大量のXML文書データを効率的に処理する独自の方式を考案し,プロトタイプシステムを構築した。現段階においても,きわめて高速であり,検索のみならず,データの集計・変換・抽出など具体的な多くの用途に使用できる。

This study is based on the research topic of "high speed and low pressure", and the following three research projects are developed. (A)The development of basic knowledge discovery methods for character string processing. (B)Text string compression and knowledge discovery. (C)Basic technology development for high speed knowledge discovery processing. (A)In this paper, we introduce a formal SRS system, which is defined in practice and verified in practice. This study was successful in discovering and applying biological knowledge. (B)The index structure represented by DAWG is based on Lempel-Ziv compression method and the new method is developed. In this paper, we introduce the system of the form of compression and compression, and develop the system of the form of compression and compression. This approach is expected to speed up the same configuration model. (C)DAWG and MASDAWG index structure are developed, installed and used successfully in the research of index structure. This is the first time that a computer has been installed. In this paper, we discuss the importance of semi-structured data structure, and discuss how to deal with a large number of XML documents in a unique way. At the present stage, there are many kinds of high-speed equipment, such as high-speed equipment, high-speed equipment, high-speed equipment and high-speed equipment.

项目成果

H.Hori et al.: "Fragmentary Pattern Matching : Complexity, Algorithms and Applications for Analyzing Classic Literary Works"Proc. 12^<th> Annual International Symposium on Algorithms and Computation. 719-730 (2001)

H.Hori 等人：“片段模式匹配：分析经典文学作品的复杂性、算法和应用”Proc。

S.Inenaga et al.: "On-Line Construction of Symmetric Compact. Directed Acyclic Word Graphs"Proc. 8^<th> International Symposium on String Processing and Information Retrieval. 96-110 (2001)

S.Inenaga 等人：“对称紧凑有向无环字图的在线构造”Proc。

Y.Hayashi et al.: "Uniform characterization of polynomial-query learnabilities"Theoretical Computer Science. 292(2). 377-385 (2003)

Y.Hayashi 等人：“多项式查询可学习性的统一表征”理论计算机科学。

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

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

T.Kida et al.: "A unifying framework for compressed pattern matching"Theoretical Computer Science. (to appear).

T.Kida 等人：“压缩模式匹配的统一框架”理论计算机科学。