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

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

• 批准号: 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++言語のテンプレートを利用したライブラリの基礎設計を行い,プロトタイプを作成した.

今年的主要成果如下： 1）延续去年，我们研究了一种在发现最佳复合串模式时减少不必要的模式候选的方法。为了减少子串的数量，可以定义等价。关于文本中出现的子串的关系，并将子串分解为等价类。尽管众所周知，可以通过使用后缀树和 CDAWG 等数据结构在相对于文本长度的线性时间内解决等价类分解问题，但它需要大量的存储容量，我们设计了一种在文本中执行类分解的算法。仅使用一个后缀数组和两个辅助数组即可实现线性时间。它也优于使用后缀树的传统算法。我们通过对各种数据的计算机实验表明，它在计算速度和存储容量上都具有优越性。2）利用上述子串的等价类分解算法，提取了多个特征子串等价类，并提出了一种高效的无监督学习算法根据它们检测留言板上的垃圾邮件帖子。我们通过计算机实验证实了其有效性。3）澄清独立于模式类的共同点并简化实现工作，这在为各种模式类实现最佳模式发现算法时是必要的。我们致力于为该项目开发软件基础设施。我们使用C++语言模板设计了基础库并创建了原型。

项目成果

Efficient computation of substring equivalence classes with suffix arrays

• DOI: 10.1007/s00453-016-0178-z
• 发表时间: 2007-01-01
• 期刊: COMBINATORIAL PATTERN MATCHING, PROCEEDINGS
• 作者: Narisawa, Kazuyuki;Inenaga, Shunsuke;Takeda, Masayuki
• 通讯作者: Takeda, Masayuki

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名