非線形テキストにおける最長共通部分文字列・部分列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
非線形テキストは,文字列を頂点ラベルとする有向グラフである.本論文では,二つの非線形テキストに対して,その類似性を調べる為に,二つの非線形テキストにおける最長共通部分文字列問題と最長共通部分列問題を定義し,サイクルを含まない非線形テキストに対し,O(|E||E_2|)時間での解法を提案する.ここで,|E|,|E_2|は二つの非線形テキストG_1,G_2のそれぞれの辺の数を表す.また,サイクルを含む非線形テキストにおける最長共通部分列問題のO(|E_1|+|E_2|+|E'_1||E'_2|+|V'_1||V'_2|log|Σ|+|Σ|log|Σ|)時間での解法を提案する.ここで,|Σ|はアルファベットサイズE'_1,E'_2,V'_1,V'_2はそれぞれG_1,G_2をサイクルを一つの頂点と見なし,変形した後の辺の数と頂点数を表す.
- 2011-05-04
著者
-
稲永 俊介
九州大学大学院システム情報科学研究院
-
竹田 正幸
九州大学大学院システム情報科学研究院
-
坂内 英夫
九州大学大学院システム情報科学府情報理学専攻
-
坂内 英夫
九大
-
竹田 正幸
九州大学大学院システム情報科学府情報学専攻
-
下平 浩二
九州大学大学院システム情報科学府
-
稲永 俊介
九州大学 大学院システム情報科学研究院
-
坂内 英夫
九州大学大学院システム情報科学府
-
竹田 正幸
九州大学大学院システム情報科学府
関連論文
- オンラインランク統合問題 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 楽曲の分類と文字列間の類似性指標について (特集 「脳科学と知識処理」および一般)
- 『恵慶法師集』比良歌群試注
- 九州大学における一般情報処理教育支援システムについて
- 古典和歌からの知識発見 : モビルスーツを着た国文学者(失われゆく情報の復元・保存技術 : 人文科学における情報処理(文献学・データベース共有・史科編纂))
- 質問学習における学習可能性の統一的特徴づけ
- 圧縮文字列における最長共通部分文字列および回文を求める多項式時間アルゴリズム
- 平衡直線的プログラムで圧縮された文字列の非反復性検証アルゴリズム
- WindowsマシンにおけるSeepの実装
- 国文学の研究教育における機械学習応用(機械学習の科学研究への応用)