| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2015-06-13 14:20 Ukkonenのオンライン接尾辞木構築アルゴリズムの多重ストリーム文字列への拡張について ○髙木拓也・有村博紀（北大）  COMP2015-13 |
|
| 抄録 | （和） | 本論文では，次第に伸長する$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 that a 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 space supporting 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 using Weiner's algorithms and Ukkonen's algorithm. |
|
| キーワード | （和） | 文字列アルゴリズム / テキスト索引 / 一般化接尾辞トライ / 一般化接尾辞木 / 先行者クエリ構造 / / / |
| （英） | string algorithm / text index / generalized suffix trie and tree / predecessor dictionary / / / / | |
| 文献情報 | 信学技報, vol. 115, no. 84, COMP2015-13, pp. 125-132, 2015年6月. | |
| 資料番号 | COMP2015-13 | |
| 発行日 | 2015-06-05 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2015-13 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2015-06-12 - 2015-06-13 |
| 開催地（和） | 定山渓ビューホテル |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2015-06-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 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)（和/英） | 先行者クエリ構造 / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 髙木 拓也 / Takuya Takagi / タカギ タクヤ |
| 第1著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 有村 博紀 / Hiroki Arimura / アリムラ ヒロキ |
| 第2著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2015-06-13 14:20:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2015-13 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | no.84 |
| ページ範囲 | pp.125-132 |
| ページ数 | 8 |
| 発行日 | 2015-06-05 (COMP) |
[研究会発表申込システムのトップページに戻る]