| 講演名 | 2011-05-11 非線形テキストにおける最長共通部分文字列・部分列アルゴリズム 下平 浩二, 稲永 俊介, 坂内 英夫, 竹田 正幸, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 非線形テキストは,文字列を頂点ラベルとする有向グラフである.本論文では,二つの非線形テキストに対して,その類似性を調べる為に,二つの非線形テキストにおける最長共通部分文字列問題と最長共通部分列問題を定義し,サイクルを含まない非線形テキストに対し,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をサイクルを一つの頂点と見なし,変形した後の辺の数と頂点数を表す. |
| 抄録(英) | 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|Σ|+|Σ|log|Σ|)-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 substing problem / Longest common subsequence problem |
| 資料番号 | COMP2011-13 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2011/5/4(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 非線形テキストにおける最長共通部分文字列・部分列アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Algorithms for computing Longest Common Substring/Subsequence on Non-linear Texts |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 非線形テキスト / Non-Linear texts |
| キーワード(2)（和/英） | 最長共通部分文字列問題 / Longest common substing problem |
| キーワード(3)（和/英） | 最長共通部分列問題 / Longest common subsequence problem |
| 第 1 著者 氏名（和/英） | 下平 浩二 / Kouji SHIMOHIRA |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学府 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 第 2 著者 氏名（和/英） | 稲永 俊介 / Shunsuke INENAGA |
| 第 2 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Faculty of Information Science and Electrical Engineering, Kyushu University |
| 第 3 著者 氏名（和/英） | 坂内 英夫 / Hideo BANNAI |
| 第 3 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Faculty of Information Science and Electrical Engineering, Kyushu University |
| 第 4 著者 氏名（和/英） | 竹田 正幸 / Masayuki TAKEDA |
| 第 4 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Faculty of Information Science and Electrical Engineering, Kyushu University |
| 発表年月日 | 2011-05-11 |
| 資料番号 | COMP2011-13 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 25 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |