Implementation of update algorithms for a double-array structure
Implementation of update algorithms for a double-array structure
复制标题
双数组结构更新算法的实现
DOI：
10.1109/icsmc.2001.969862
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
J. Aoe
中科院分区：
文献类型：
--
作者：
K. Morita;Akihiro Tanaka;M. Fuketa;J. Aoe
在许多信息检索应用中，需要能够采用trie查找来逐个字符地查看输入。作为一种快速、紧凑的trie树数据结构，提出了双数组。然而，插入时间并不比其他动态检索方法快，因为双数组是一种半静态检索方法，不能处理高频更新。此外，双阵列的空间效率随着删除的数量而降低，因为它保留了删除产生的空元素。本文提出了两种算法来建立双数组作为一种动态检索方法。从10万个密钥的仿真结果来看，插入时间和空间效率都得到了显著改善。
In many information retrieval applications, it is necessary to be able to adopt a trie search for looking at the input character by character. As a fast and compact data structure for a trie, a double-array is presented. However, the insertion time is not faster than other dynamic retrieval methods because the double-array is a semi-static retrieval method that cannot treat high frequency updating. Further, the space efficiency of the double-array degrades with the number of deletions because it keeps empty elements produced by deletion. The paper presents two algorithms to establish the double-array as a dynamic retrieval method. From the simulation results for 100 thousand keys, it turned out that the insertion time and the space efficiency are remarkably improved.