WEKO3
アイテム
長いパターンを検出するための文法圧縮に基づく索引構造
https://ipsj.ixsq.nii.ac.jp/records/71720
https://ipsj.ixsq.nii.ac.jp/records/717202488389b-c6b7-4fdd-a1a8-2b912a5490d8
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL11133005.pdf (744.2 kB)
|
Copyright (c) 2011 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2011-01-05 | |||||||
| タイトル | ||||||||
| タイトル | 長いパターンを検出するための文法圧縮に基づく索引構造 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A data structure based on grammatical compression to detect long pattern | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 九州工業大学大学院情報工学府 | ||||||||
| 著者所属 | ||||||||
| 九州工業大学大学院情報工学府 | ||||||||
| 著者所属 | ||||||||
| 九州大学大学院システム情報科学府 | ||||||||
| 著者所属 | ||||||||
| 九州工業大学大学院情報工学研究院 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyushu Institute of Technology Graduate School of Computer Science and Systems Engineering | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyushu Institute of Technology Graduate School of Computer Science and Systems Engineering | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyushu University Graduate School of Information Science and Electrical Engineering | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Kyushu Institute of Technology Faculty of Computer Science and Systems Engineering | ||||||||
| 著者名 |
岸上, 直也
× 岸上, 直也
|
|||||||
| 著者名(英) |
Naoya, Kishiue
× Naoya, Kishiue
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本研究では，文脈自由文法に基づいた圧縮索引から長いパターンを高速に検索する手法を提案する．提案手法では，2(1 + ε)n log n + 4n + o(n) ビット領域，O( 1/ε (mlog n + occc(log m log u))) 時間でパターンの出現回数を検出できる．ここで n はサイズ u の原テキストを圧縮し得られた変数の数であり，m = |P|, 0 < ε < 1 である．実験の結果，ある程度以上の長さを持つパターンについて，LZ-index8) や FM-index3) などの既存手法よりも高速に検出できることを確認した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | In this research, we propose the method to search long pattern from compressed index based on Context-free Grammar. The proposed method can detect the pattern at O( 1/ε (mlog n+occc(logmlog u))) time with 2(1+ε)n log n+4n+o(n) bits, where n is generated variables compressed text (original size u), m = |P|, 0 < ε < 1. Result of experiments, we confirmed our proposed method was faster than existing method (e.g, LZ-index8), FM-index3)) at long pattern. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2011-AL-133, 号 5, p. 1-7, 発行日 2011-01-05 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
