Abstract—Key retrieval is the most basic and important
technology. The trie is one of the key retrieval methods that can
be retrieved without depending on the number of registered keys.
The development of implementation method of a trie is
indispensable for use in application fields. The double array is
an excellent implementation method of a trie with high speed
retrieval and compactness. However, there is room for the
improvement in comparison with the implementation method
given priority to memory efficiency because the size for two
integer types per one node is necessary. This paper presents a
novel implementation method for a trie by using the idea of the
randomized algorithm. From experimental observations, it was
shown that the proposal method promotes efficiency of a
trade-off of memory size and the speed well.
Index Terms—Trie, double array, randomized algorithm,
pseudorandom number generator.
Kazuhiro Morita and Masao Fuketa are with the Department of Computer
Science, Graduate School of Science and Technology, Tokushima
University, Tokushima, Japan (e-mail: kam@is.tokushima-u.ac.jp,
fuketa@is.tokushima-u.ac.jp).
Shunsuke Kanda is with the Department of Information Science and
Intelligent Systems, Graduate School of Advanced Technology and Science,
Tokushima University, Tokushima, Japan (e-mail: shnsk.knd@gmail.com).
[PDF]
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.
