| 講演名 | 2011-05-11 非線形コラージュシステムにおける文字列パターン照合 山本 淳一, 稲永 俊介, 坂内 英夫, 竹田 正幸, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 非線形テキストは,文字列を頂点ラベルとする有向グラフである.本論文では,頂点ラベルが圧縮形式で表現された非線形コラージュシステムを提案する.非線形コラージュシステムは,Kidaらが提案した辞書式圧縮法で圧縮されたテキストを統一的に表現する枠組みであるコラージュシステムの拡張である.nを辞書の句の数,mをパターン長、|E|を有向グラフの辺数,rをパターンの出現数としたとき、非線形コラージュシステムにおける文字列照合問題をO(n+m^2+|E|m+r)時間,O(n+m^2+|E|m)空間で解くアルゴリズムを提案する. |
| 抄録(英) | A non-linear text is a directed graph where each vertex is labeled with a string. In this paper, we propose a non-linear collage system where each vertex label is represented in compressed form. The non-linear collage system is a generalization of the collage system proposed by Kida et al., a unified framework for dictionary based text compression schemes. We propose an O(n+m^2+|E|m+r)-time O(n+m^2+|E|m)-space algorithm that solves the pattern matching problem on a non-linear collage system, where n is the number of variables, m is the length of the pattern, |E| is the number of edges in the graph, and r is the number of occurrences of the pattern. |
| キーワード(和) | 文字列照合 / 非線形テキスト / コラージュシステム |
| キーワード(英) | string pattern matching / non-linear texts / collage systems |
| 資料番号 | COMP2011-12 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2011/5/4(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 非線形コラージュシステムにおける文字列パターン照合 |
| サブタイトル（和） | |
| タイトル（英） | A String Pattern Matching Algorithm for Non-Linear Collage Systems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 文字列照合 / string pattern matching |
| キーワード(2)（和/英） | 非線形テキスト / non-linear texts |
| キーワード(3)（和/英） | コラージュシステム / collage systems |
| 第 1 著者 氏名（和/英） | 山本 淳一 / Junichi YAMAMOTO |
| 第 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-12 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 25 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |