A Novel and Efficient Data Structure to Facilitate Dictionary Search using Wildcards

In this paper, a novel and efficient data structure named as 'Augmented Trie' has been proposed that can store a large collection of English words and search them efficiently. The data structure has been specially designed in a way to facilitate the search for strings with wildcard characters. Even though the memory requirement for constructing 'Augmented Trie' is higher than simple trie, it does not become significant as memory allocation has been performed intelligently using bit masking. By experimental results we show that the proposed method of finding patterns with wildcard characters improves over the existing one by 13.5% (maximum). Keywords—data structure, algorithm, wildcard search.