講演抄録/キーワード |
講演名 |
2011-05-11 13:35
非線形テキストにおける最長共通部分文字列・部分列アルゴリズム ○下平浩二・稲永俊介・坂内英夫・竹田正幸(九大) COMP2011-13 |
抄録 |
(和) |
非線形テキストは,文字列を頂点ラベルとする有向グラフである.本論文では,二つの非線形テキストに対して,その類似性を調べる為に,二つの非線形テキストにおける最長共通部分文字列問題と最長共通部分列問題を定義し,サイクルを含まない非線形テキストに対し,$O(|E_1||E_2|)$時間での解法を提案する.
ここで,$|E_1|,|E_2|$ は二つの非線形テキスト$G_1,G_2$ のそれぞれの辺の数を表す.
また,サイクルを含む非線形テキストにおける最長共通部分列問題の$O(|E_1|+|E_2|+|E'_1||E'_2|+|V'_1||V'_2|\log|\Sigma|+|\Sigma|\log|\Sigma|)$時間での解法を提案する.
ここで,$|\Sigma|$はアルファベットサイズ$E'_1,E'_2,V'_1,V'_2$はそれぞれ$G_1,G_2$をサイクルを一つの頂点と見なし,変形した後の辺の数と頂点数を表す. |
(英) |
A non-linear text is a directed graph where each vertex is labeled with a string.
In this paper, we define Longest common substring/subsequence problems on Non-linear texts and solve them, to measure degree of similarity between two non-linear texts.We propose $O(|E_1||E_2|)$-time algorithms on acyclic non-linear texts, where $|E_1|,|E_2|$ are the numbers of edges in the non-linear texts $G_1,G_2$.
In addition we propose an $O(|E_1|+|E_2|+|E'_1||E'_2|+|V'_1||V'_2|\log|\Sigma|+|\Sigma|\log|\Sigma|)$-time algorithm to solve a longest common subsequence problem on cyclic non-linear texts, where $|E'_1|,|E'_2|,|V'_1|,|V'_2|$ are the numbers of edges and vertexes in the non-linear texts which are transformed from $G_1,G_2$. |
キーワード |
(和) |
非線形テキスト / 最長共通部分文字列問題 / 最長共通部分列問題 / / / / / |
(英) |
Non-linear texts / Longest common substring problem / Longest common subsequence problem / / / / / |
文献情報 |
信学技報, vol. 111, no. 25, COMP2011-13, pp. 9-16, 2011年5月. |
資料番号 |
COMP2011-13 |
発行日 |
2011-05-04 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2011-13 |
|