| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-09-03 09:30 マルチトラック文字列の順列パターン照合と索引構造 ○桂 敬史・成澤和志・篠原 歩（東北大）・坂内英夫・稲永俊介（九大）  COMP2012-26 |
|
| 抄録 | （和） | 文字列の多重集合，すなわちマルチトラック文字列上の 新しいパターン照合として順列パターン照合を提案する． 順列パターン照合では， トラック長$n$，トラック数$N$のマルチトラックテキスト中に出現する トラック長$m$，トラック数$M$のマルチトラックパターンを探す． 我々はこの問題が，一般のアルファベットでは$O(nN\log|\Sigma|)$時間・$O(mM+N)$領域， 整数型のアルファベットでは$O(nN)$時間・領域で解くことができることを示す． また，テキストとパターンのトラック数が等しい場合（全順列パターン照合）に対し， 我々はマルチトラック接尾辞木と呼ばれる新たな索引構造を提案し， このデータ構造の$O(nN \log |\Sigma|)$時間・ $O(nN)$領域構築アルゴリズムを示す． マルチトラック接尾辞木を用いることで，全順列パターン照合問題が $O(mN \log |\Sigma| + \occ)$時間で計算可能であることを示す． |
| （英） | We propose a new variant of pattern matching on a multi-set of strings, or multi-tracks, called permuted-matching, that looks for occurrences of a multi-track pattern of length $m$ with $M$ tracks, in a multi-track text of length $n$ with $N$ tracks. We show that the problem can be solved in $O(nN\log|\Sigma|)$ time and $O(mM+N)$ space, and further in $O(nN)$ time and space when assuming an integer alphabet. For the case where the number of strings in the text and pattern multi-track are equal (full-permuted-matching), we propose a new index structure called the multi-track suffix tree, as well as an $O(nN \log |\Sigma|)$ time and $O(nN)$ space construction algorithm. Using this data structure, we can solve the full-permuted-matching problem in $O(mN \log |\Sigma| + \occ)$ time for any multi-track pattern of length $m$ with $N$ tracks. |
|
| キーワード | （和） | パターン照合 / マルチトラック文字列 / 接尾辞木 / 索引構造 / / / / |
| （英） | pattern matching / multi-track string / suffix tree / index structure / / / / | |
| 文献情報 | 信学技報, vol. 112, no. 199, COMP2012-26, pp. 1-8, 2012年9月. | |
| 資料番号 | COMP2012-26 | |
| 発行日 | 2012-08-27 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2012-26 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2012-09-03 - 2012-09-03 |
| 開催地（和） | 法政大学 |
| 開催地（英） | Hosei University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2012-09-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | マルチトラック文字列の順列パターン照合と索引構造 |
| サブタイトル（和） | |
| タイトル（英） | Permuted Pattern Matching and Indexing Structure for Multi-Track Strings |
| サブタイトル（英） | |
| キーワード(1)（和/英） | パターン照合 / pattern matching |
| キーワード(2)（和/英） | マルチトラック文字列 / multi-track string |
| キーワード(3)（和/英） | 接尾辞木 / suffix tree |
| キーワード(4)（和/英） | 索引構造 / index structure |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 桂 敬史 / Takashi Katsura / カツラ タカシ |
| 第1著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 成澤 和志 / Kazuyuki Narisawa / ナリサワ カズユキ |
| 第2著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 篠原 歩 / Ayumi Shinohara / シノハラ アユミ |
| 第3著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 坂内 英夫 / Hideo Bannai / バンナイ ヒデオ |
| 第4著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第5著者 氏名（和/英/ヨミ） | 稲永 俊介 / Shunsuke Inenaga / イネナガ シュンスケ |
| 第5著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-09-03 09:30:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2012-26 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.199 |
| ページ範囲 | pp.1-8 |
| ページ数 | 8 |
| 発行日 | 2012-08-27 (COMP) |
[研究会発表申込システムのトップページに戻る]