Item type |
Trans(1) |
公開日 |
2020-04-16 |
タイトル |
|
|
タイトル |
ダブル配列を用いたパトリシアトライによる動的キーワード辞書の実装 |
タイトル |
|
|
言語 |
en |
|
タイトル |
Implementation of Dynamic Keyword Dictionary by Patricia Trie Using Double-Array |
言語 |
|
|
言語 |
jpn |
キーワード |
|
|
主題Scheme |
Other |
|
主題 |
[研究論文] キーワード辞書,ダブル配列,パトリシアトライ |
資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
著者所属 |
|
|
|
徳島大学大学院先端技術科学教育部 |
著者所属 |
|
|
|
徳島大学大学院ソシオテクノサイエンス研究部 |
著者所属 |
|
|
|
徳島大学大学院ソシオテクノサイエンス研究部 |
著者所属(英) |
|
|
|
en |
|
|
Faculty of Engineering, Tokushima University |
著者所属(英) |
|
|
|
en |
|
|
Institute of Technology and Science, Tokushima University |
著者所属(英) |
|
|
|
en |
|
|
Institute of Technology and Science, Tokushima University |
著者名 |
松本, 拓真
森田, 和宏
泓田, 正雄
|
著者名(英) |
Takuma, Matsumoto
Kazuhiro, Morita
Masao, Fuketa
|
論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
ダブル配列トライは文字列をキーとした辞書の実現に広く用いられている.辞書の動的な更新を必要とする用途において,従来手法では,分岐のない頂点以降の接尾辞を文字列で表現した接頭辞トライとしてキー集合を表現し,空間効率の良い辞書を実現している.しかし辞書を実現するためのトライとしては,分岐のある頂点のみで構成されるパトリシアトライとして表現することでより少ない頂点数で辞書を実現できる.そこで我々は,ダブル配列トライをパトリシアトライで構成する方法と,空間効率の無駄のない枝の分岐アルゴリズムを提案した.実社会で用いられるデータセットを用いて辞書を構築する実験では,提案手法は従来手法に対してメモリ消費量と検索時間を改善し,特に検索時間を大きく改善した. |
論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11464847 |
書誌情報 |
情報処理学会論文誌データベース(TOD)
巻 13,
号 2,
p. 34-44,
発行日 2020-04-16
|
ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1882-7799 |
出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |