SST: An Efficient Suffix-Sharing Trie Structure for Dictionary Lookup

In many information systems, a dictionary lookup is widely adopt and utilized as a part of computation. To use in-memory dictionary, one of the most popular techniques is the using of trie structure to store a collection of words. However, it is well-known that the using of trie will consume a large amount of memory when the collection of words is large and it cannot notify the nature of words which may help users to better understand context. Therefore, in this paper, an efficient Suffix-Sharing Trie structure, named SST, is proposed to store all of words. SST is a two-trie structure that not only share prefixes but it can also share suffixes of words. By doing this, SST can identify which words having a suffix as a component and it can also reduce the memory consumption from the trie structure. Experimental results show that the proposed SST structure is efficient on both runtime and memory usage to maintain a collection of words in-memory.