Implementation of update algorithms for a double-array structure

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