最適複合文字列パターン発見アルゴリズムに関する研究

最优复合串模式发现算法研究

• 批准号: 18700153
• 负责人: 坂内 英夫
• 金额: $ 1.98万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18700153/
• 关键词: パターン発見; 接尾辞配列; 接尾辞木グラフ; 窓付き最長共通部分列長; 部分文字列

本年度の主な成果は以下の3点である.1)昨年度に引き続き,最適複合文字列パターン発見を行う際に不必要なパターン候補を減らす手法について研究を行った.部分文字列パターンの候補を減らすために,テキストにおける出現箇所に関する部分文字列上の同値関係を定義し,部分文字列を同値類に分解することが考えられる.この部分文字列の同値類分解問題は接尾辞木やCDAWGなどのデータ構造を用いることで,テキスト長に関して線形時間でできることが知られてはいたものの,大きな記憶容量を要した.これに対し,本研究ではこの同値類分解を接尾辞配列と二つの補助配列のみを用いて線形時間で行うアルゴリズムを考案した.また,接尾辞木などを用いた従来アルゴリズムと比べ,計算速度と記憶容量の両面で優れていることを様々なデータに対する計算機実験で示した.2)上述の部分文字列上の同値類分解アルゴリズムを利用することで,インターネット上の掲示板データから特徴的な部分文字列同値類を複数抽出し,それを基に掲示板におけるスパム投稿を検出する効率の良い教師無し学習アルゴリズムを提案した.また計算機実験によりその有効性を確認した.3)様々なパターンクラスに対して最適パターン発見アルゴリズムの実装を行う際に必要な,パターンクラスに依存しない共通点を明確にし,実装作業を簡易化するためのソフトウェア基盤開発に取り組んだ.C++言語のテンプレートを利用したライブラリの基礎設計を行い,プロトタイプを作成した.

The main results of this year are as follows: 1) yesterday's quotation, the most complex text column, the most complex text column, is not necessary. Part of the text column is the same as the definition of the same text column, and some text columns are the same as those of the same type of text column. This part of the text column ends with the same kind of decomposition problem. This is the end of the word. The CDAWG system is used to make the system. For long periods of time, you need to know that you are aware of the problem, and that the large storage capacity is important. In this study, the two-year program is used to help train the users of the same class of decomposition in this study. In the end, the word word is used to compare and calculate the speed and capacity of the computer. The computer is displayed on the computer. 2) some of the above text columns are similar to those of the same class of text. The part of the text in the text column of the display board is the same as that in the same type of text column, and the basic information board is displayed in the same way. The contribution rate is shown in the paper. The computer

项目成果

A New Family of String Classifiers based on Local Relatedness

基于局部相关性的一类新的字符串分类器

• 发表时间: 2006
• 期刊: Lecture Notes in Artificial Intelligence(Proc.9^<th> International Conference on Discovery Science) 4265
• 作者: Yasuto Higa;他3名
• 通讯作者: 他3名