Practical rearrangement methods for dynamic double‐array dictionaries. (28th July 2017)

• Record Type: Journal Article
• Authors: Kanda, Shunsuke; Fujita, Yuma; Morita, Kazuhiro; Fuketa, Masao
• Is Part Of: Software, practice & experience. Volume 48:Number 1(2018)
• Page Start: 65
• Page End: 83
• Publication Date: 2017-07-28
• Subjects: data structure -- double‐array trie -- dynamic dictionary -- string processing; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2516
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: Double‐array structures have been widely used to implement dictionaries with string keys. Although the space efficiency of dynamic double‐array dictionaries tends to decrease with key updates, we can still maintain high efficiency using existing methods. However, these methods have practical problems of time and functionality. This paper presents several efficient rearrangement methods to solve these problems. Through experiments using real‐world datasets, we demonstrate that the proposed rearrangement methods are much more practical than existing methods.