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

松本, 拓真, 森田, 和宏, 泓田, 正雄

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

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.

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

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

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

書き出し

問題の指摘

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

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

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

書き出し

問題の指摘

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