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

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

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