doi: 10.18178/ijfcc.2016.5.6.476
An Implementation Method of Trie Structure Using Xorshift
Kazuhiro Morita
1
,
Shunsuke Kanda
2
,
Masao Fuketa
1
- 1 Department of Computer Science, Graduate School of Science and Technology, Tokushima University, Tokushima, Japan.
- 2 Department of Information Science and Intelligent Systems, Graduate School of Advanced Technology and Science, Tokushima University, Tokushima, Japan.
Abstract
Key retrieval is the most basic and importanttechnology. The trie is one of the key retrieval methods that canbe retrieved without depending on the number of registered keys.The development of implementation method of a trie isindispensable for use in application fields. The double array isan excellent implementation method of a trie with high speedretrieval and compactness. However, there is room for theimprovement in comparison with the implementation methodgiven priority to memory efficiency because the size for twointeger types per one node is necessary. This paper presents anovel implementation method for a trie by using the idea of therandomized algorithm. From experimental observations, it wasshown that the proposal method promotes efficiency of atrade-off of memory size and the speed well.
Keywords
- Trie
- double array
- randomized algorithm
- pseudorandom number generator
How to Cite
Kazuhiro Morita, Shunsuke Kanda, and Masao Fuketa, "An Implementation Method of Trie Structure Using Xorshift," International Journal of Future Computer and Communication, vol. 5, no. 6, pp. 229-232, 2016. https://doi.org/ 10.18178/ijfcc.2016.5.6.476
Copyright & License
Copyright © 2016 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).