文献

J-GLOBAL ID：201802268826873091   整理番号：18A2083958

ダブル配列オートマトンによる圧縮文字列辞書の実装

著者 (4件)： 松本拓真 (徳島大 大学院先端技術科学教育部) ,  神田峻介 (理研 革新知能統合研究セ) ,  森田和宏 (徳島大 大学院先端技術科学教育部) ,  泓田正雄 (徳島大 大学院先端技術科学教育部)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2018  号： IFAT-132  ページ： Vol.2018-IFAT-132,No.15,1-6 (WEB ONLY)  発行年： 2018年09月05日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 文字列辞書は,文字列集合を保管し検索・復元機能を備えるデータ構造であり,近年,様々な用途でそのコンパクト性が求められている。辞書を実現するための優れた技法としてTrieなどがあり,これらを効率よく表現するデータ構造が多く提案されている。本稿では,文字列集合の接頭辞と接尾辞を効率的に圧縮できるDFA(決定性有限オートマトン)を用いた圧縮文字列辞書を提案する。DFAの表現に用いるデータ構造にはダブル配列オートマトンを採用し,辞書の機能を実現するための実装と,それに伴う圧縮手法を紹介する。提案手法は文字列の復元時間に理論的課題を有していたものの,実データを用いた実験では,メモリ効率と検索性能のトレードオフにおいて他の手法と同等の性能を示しつつ,高い検索性能を持つことを示した。(著者抄録)

シソーラス用語： *辞書 ,  *文字列 ,  *データ圧縮 ,  *決定性オートマトン ,  有限オートマトン ,  ツリー構造 ,  配列 ,  *データ構造 ,  集合 ,  評価試験 ,  データ検索 ,  アルゴリズム ,  コーパス ,  C++言語 ,  ダブル配列
準シソーラス用語： *圧縮文字列辞書 ,  *決定性有限オートマトン ,  ルックアップアルゴリズム

分類 (2件)： 自然語処理  (JE06000L) ,  オートマトン理論  (JB04000O)

引用文献 (11件)：

• Martnez-Prieto, M. A., Brisaboa, N., Cnovas, R., Claude, F. and Navarro, G.: Practical compressed string dictionaries, Information Systems, Vol. 56, pp. 73 - 108 (online), DOI: https://doi.org/10.1016/j.is.2015.08.008 (2016).
• 矢田 晋:Prefix/Patricia Trie の入れ子による辞書圧縮, 言語処理学会第17回年次大会発表論文集,pp. 576-578 (2011).
• Grossi, R. and Ottaviano, G.: Fast Compressed Tries throwgh Path Decompositions, Journal of Experimental Algorithmics (JEA), Vol. 19, pp. 3-4 (2014).
• Kanda, S., Morita, K. and Fuketa, M.: Compressed double-array tries for string dictionaries supporting fast lookup, Knowledge and Information Systems, Vol. 51, No. 3, pp. 1023-1042 (2017).
• Hopcroft, J. E., Ullman, J. and Motowani, R.: オートマトン・言語理論・計算論 (2003).

タイトルに関連する用語 (5件)： ダブル配列 ,  オートマトン ,  文字列 ,  辞書 ,  実装