| 講演名 | 2015-06-13 Ukkonenのオンライン接尾辞木構築アルゴリズムの多重ストリーム文字列への拡張について 髙木 拓也(北大), 有村 博紀(北大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本論文では，次第に伸長する$K$本の文字列の集合に対するテキスト索引のオンライン構築を研究する．この問題は，多数のセンサーストリームに対する文字列検索に役立つ．特にテキスト索引として，一般化接尾辞トライと一般化接尾辞木を対象とする．はじめに，Ukkonenによる接尾辞トライのオンライン構築アルゴリズムを拡張して，$N$文字からなる$K$本の文字列の集合$S$に対して，共通の一般化接尾辞トライを$O(N^2)$時間と領域でオンライン構築し，文字列照合クエリ$P$に$O(|P|)$時間で答えるアルゴリズムを与える．提案手法は，$K$個の接尾辞トライを同時に構築する素朴な方法に比べて，構築時間と領域は変わらないが，１つの木にまとめることでクエリ時間を$O(K|P|)$から$O(|P|)$に小さくする．次に，WeinerのRight-To-Left構築とUkkonenのLeft-to-Right構築のアルゴリズムを用いて，一般化接尾辞木に基づく線形領域のテキスト索引をオンライン構築する方法について議論する． |
| 抄録(英) | In this paper, we consider online construction of a text index for a set $S$ of $K$ strings in the dynamic setting thata new letter is appended to one of the strings from time to time. First, we present an online algorithm that constructs the generalized suffix trie of $S$ in $O(N^2)$ time and spacesupporting string matching query $P$ in $O(|P|)$ time, where $N$ is the total number of letters in $S$. Next, we discuss online construction of a linear space text index based on generalized suffix trees usingWeiner's algorithms and Ukkonen's algorithm. |
| キーワード(和) | 文字列アルゴリズム / テキスト索引 / 一般化接尾辞トライ / 一般化接尾辞木 / 先行者クエリ構造 |
| キーワード(英) | string algorithm / text index / generalized suffix trie and tree / predecessor dictionary |
| 資料番号 | COMP2015-13 |
| 発行日 | 2015-06-05 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2015/6/12(から2日開催) |
| 開催地（和） | 定山渓ビューホテル |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 和田 幸一(法政大) |
| 委員長氏名（英） | Koichi Wada(Hosei Univ.) |
| 副委員長氏名（和） | 増澤 利光(阪大) |
| 副委員長氏名（英） | Toshimitsu Masuzawa(Osaka Univ.) |
| 幹事氏名（和） | 亀井 清華(広島大) / 古賀 久志(電通大) |
| 幹事氏名（英） | Sayaka Kamei(Hiroshima Univ.) / Hisashi Koga(Univ. of Electro-Comm.) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Ukkonenのオンライン接尾辞木構築アルゴリズムの多重ストリーム文字列への拡張について |
| サブタイトル（和） | |
| タイトル（英） | On an Extension of Ukkonen's Online Suffix tree construction algorithm to Multi-Stream texts |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 文字列アルゴリズム / string algorithm |
| キーワード(2)（和/英） | テキスト索引 / text index |
| キーワード(3)（和/英） | 一般化接尾辞トライ / generalized suffix trie and tree |
| キーワード(4)（和/英） | 一般化接尾辞木 / predecessor dictionary |
| キーワード(5)（和/英） | 先行者クエリ構造 |
| 第 1 著者 氏名（和/英） | 髙木 拓也 / Takuya Takagi |
| 第 1 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 第 2 著者 氏名（和/英） | 有村 博紀 / Hiroki Arimura |
| 第 2 著者 所属（和/英） | 北海道大学(略称：北大) Hokkaido University(略称：Hokkaido Univ.) |
| 発表年月日 | 2015-06-13 |
| 資料番号 | COMP2015-13 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | COMP-84 |
| ページ範囲 | pp.125-132(COMP), |
| ページ数 | 8 |
| 発行日 | 2015-06-05 (COMP) |