A compact static double-array keeping character codes

A compact static double-array keeping character codes,10.1016/j.ipm.2006.04.004,Information Processing and Management,Susumu Yata,Masaki Oono,Kazuhiro

A compact static double-array keeping character codes   (Citations: 2)
BibTex | RIS | RefWorks Download
A trie represented by a double-array enables us to search a key fast with a small space. However, the double-array uses extra space to be updated dynamically. This paper presents a compact structure for a static double-array. The new structure keeps character codes instead of indices in order to compress elements of the double-array. In addition, the new structure unifies common suffixes and consists of less elements than the old structure. Experimental results for English keys show that the new structure reduces space usage of the double-array up to 40%.
Journal: Information Processing and Management - IPM , vol. 43, no. 1, pp. 237-247, 2007
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ... DAT: a compact and static variant of double-array [12], [13] with an improved variant of node links [14] for firstChild() and nextSibling()...

    Susumu Yataet al. Customized Tries for Weighted Key Completion

    • ...Thus, this paper proposes the use of compacted double-arrays (CDA) [10] for DAWGs because the double-array [11] is an efficient and practical internal structure for the trie...
    • ...A double-array is efficient but not directly applicable to a DAWG, because a double-array does not support vertices with in-degrees more than 1. Instead, a compacted double-array (CDA) [10] using the following formula solves this problem and enables a much compact DAWG...

    Susumu Yataet al. Fast string matching with space-efficient word graphs

Sort by: