WEKO3
アイテム
ダブル配列オートマトンによる圧縮文字列辞書の実装
https://ipsj.ixsq.nii.ac.jp/records/191253
https://ipsj.ixsq.nii.ac.jp/records/191253bcc71eb4-b7ac-4f4c-a26d-e495fee06419
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-IFAT18132015.pdf (1.2 MB)
|
Copyright (c) 2018 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2018-09-05 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | ダブル配列オートマトンによる圧縮文字列辞書の実装 | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | jpn | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | DBアルゴリズム | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||||
| 資源タイプ | technical report | |||||||||||||
| 著者所属 | ||||||||||||||
| 徳島大学大学院先端技術科学教育部 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 理化学研究所革新知能統合研究センター | ||||||||||||||
| 著者所属 | ||||||||||||||
| 徳島大学大学院先端技術科学教育部 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 徳島大学大学院先端技術科学教育部 | ||||||||||||||
| 著者名 |
松本, 拓真
× 松本, 拓真
× 神田, 峻介
× 森田, 和宏
× 泓田, 正雄
|
|||||||||||||
| 論文抄録 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 文字列辞書は，文字列集合を保管し検索 ・ 復元機能を備えるデータ構造であり，近年，様々な用途でそのコンパクト性が求められている．辞書を実現するための優れた技法として Trie などがあり，これらを効率よく表現するデータ構造が多く提案されている．本稿では，文字列集合の接頭辞と接尾辞を効率的に圧縮できる DFA (決定性有限オートマトン) を用いた圧縮文字列辞書を提案する．DFA の表現に用いるデータ構造にはダブル配列オートマトンを採用し，辞書の機能を実現するための実装と，それに伴う圧縮手法を紹介する．提案手法は文字列の復元時間に理論的課題を有していたものの，実データを用いた実験では，メモリ効率と検索性能のトレードオフにおいて他の手法と同等の性能を示しつつ，高い検索性能を持つことを示した． | |||||||||||||
| 書誌レコードID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AN10114171 | |||||||||||||
| 書誌情報 |
研究報告情報基礎とアクセス技術（IFAT） 巻 2018-IFAT-132, 号 15, p. 1-6, 発行日 2018-09-05 |
|||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 2188-8884 | |||||||||||||
| Notice | ||||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||||
| 出版者 | ||||||||||||||
| 言語 | ja | |||||||||||||
| 出版者 | 情報処理学会 | |||||||||||||
