文献

J-GLOBAL ID：202002248594640094   整理番号：20A0942294

ダブル配列を用いたパトリシアトライによる動的キーワード辞書の実装

Implementation of Dynamic Keyword Dictionary by Patricia Trie Using Double-Array

著者 (3件)： 松本拓真 (徳島大 大学院先端技術科学教育部) ,  森田和宏 (徳島大 大学院ソシオテクノサイエンス研究部) ,  泓田正雄 (徳島大 大学院ソシオテクノサイエンス研究部)
資料名： 情報処理学会論文誌トランザクション データベース(Web)  (情報処理学会論文誌 データベース(Web))
巻： 13  号： 2  ページ： 34-44 (WEB ONLY)  発行年： 2020年04月16日 
JST資料番号： U0476A  ISSN： 1882-7799  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ダブル配列トライは文字列をキーとした辞書の実現に広く用いられている.辞書の動的な更新を必要とする用途において,従来手法では,分岐のない頂点以降の接尾辞を文字列で表現した接頭辞トライとしてキー集合を表現し,空間効率の良い辞書を実現している.しかし辞書を実現するためのトライとしては,分岐のある頂点のみで構成されるパトリシアトライとして表現することでより少ない頂点数で辞書を実現できる.そこで我々は,ダブル配列トライをパトリシアトライで構成する方法と,空間効率の無駄のない枝の分岐アルゴリズムを提案した.実社会で用いられるデータセットを用いて辞書を構築する実験では,提案手法は従来手法に対してメモリ消費量と検索時間を改善し,特に検索時間を大きく改善した.(著者抄録)

シソーラス用語： *ツリー構造 ,  *キーワード ,  *辞書 ,  文字列 ,  文法 ,  アルゴリズム ,  記憶装置 ,  *ダブル配列
準シソーラス用語： メモリ ,  接尾辞

分類 (3件)： 検索技術  (AC06020S) ,  数値計算  (JE02000J) ,  その他の情報処理  (JE15050M)

引用文献 (23件)：

• Grossi, R. and Ottaviano, G.: Fast Compressed Tries through Path Decompositions, Journal of Experimental Algorithmics, Vol.19, No.1, pp.1.1-1.20 (online), DOI: 10.1145/2656332 (2015).
• Martínez-Prieto, M.A., Brisaboa, N., Cánovas, R., Claude, F. and Navarro, G.: Practical compressed string dictionaries, Information Systems, Vol.56, pp.73-108 (online), DOI: 10.1016/j.is.2015.08.008 (2016).
• 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 (online), DOI: 10.1007/s10115-016-0999-8 (2017).
• Zhang, H., Lim, H., Leis, V., Andersen, D.G., Kaminsky, M., Keeton, K. and Pavlo, A.: SuRF: Practical Range Query Filtering with Fast Succinct Tries, Proc. 2018 International Conference on Management of Data, SIGMOD ’18, pp.323-336, ACM Press (online), DOI: 10.1145/3183713.3196931 (2018).
• 松本拓真,神田峻介,森田和宏,泓田正雄:ダブル配列オートマトンによる圧縮文字列辞書の実装,情報処理学会技術報告 (2018).

タイトルに関連する用語 (4件)： ダブル配列 ,  キーワード ,  辞書 ,  実装