講演抄録/キーワード |
講演名 |
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 |