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

書誌事項

タイトル別名
  • Implementation of Dynamic Keyword Dictionary by Patricia Trie Using Double-Array

この論文をさがす

抄録

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

Double-Array Trie is widely used for implementing the keyword dictionaries. For applications that require dictionary updates, conventional implementations are space-efficient by representing key sets as Minimal-prefix Trie. However, it is fact that Patricia Trie which has only vertexes more than 2 degrees can represent key sets using less number of vertexes than Minimal-prefix Trie. Therefore, we propose implementation of dictionary as Patricia Trie using Double-Array and update methods that lean for memory consumption. Experiments using datasets in real world shows our proposed method is more efficient in memory consumption and time in search, that is large contribution for the time in search particularly.

収録刊行物

詳細情報 詳細情報について

  • CRID
    1050848249714570368
  • NII論文ID
    170000181871
  • NII書誌ID
    AA11464847
  • ISSN
    18827799
  • Web Site
    http://id.nii.ac.jp/1001/00204279/
  • 本文言語コード
    ja
  • 資料種別
    article
  • データソース種別
    • IRDB
    • CiNii Articles

問題の指摘

ページトップへ