Efficient Construction of Dictionary using Directed Acyclic Word Graph
Journal Title: IOSR Journals (IOSR Journal of Computer Engineering) - Year 2016, Vol 18, Issue 4
Abstract
Abstract: Implementation of dictionary is a topic on which research is going on since a long time in the search of a better and efficient algorithm both in terms of space and time complexity. Its necessity has increased due to the advent of recent technical advances in the fields of Pattern Recognition, Image Processing, Natural Language Processing and Machine Learning. The matter is of utter importance when it comes to handheld devices where limited memory availability is a crucial factor. From a programmer’s point of view, the earlierand the conventional methods used to implement a dictionary were hashing and suffix trees which subsequently failed in order to provide the desired space efficiency. By far the data structure which has proved to be the best for storing a dictionary has been Directed Acyclic Word Graph (DAWG), which merges the common suffixes inaddition to the common prefixes of the words. The current method used for implementing it, requires construction of an intermediate Trie which puts a lot of memory constraints and is very time inefficient. In this paper, we describe a new method for creating a compressed dictionary with DAWG using Associative Arrays and concepts of Finite Automata on-the-fly as and when a new word is encountered in the lexicographic order. The method presented in the paper doesn’t require construction of an intermediate Trie and hence has a bettertime complexity. The concept of right language has been crucial to derive the algorithm and is mentioned in the paper. The algorithm is well explained with an example. In the end, the time complexity of the algorithm is analyzed and a small comparison is made in the terms of the maximum memory requirement, for different number of words, for both of the above mentioned methods of constructing DAWG at runtime
Authors and Affiliations
Srinivas. H , Amruth. V
Keywords
Related Articles
- EP ID EP133590
- DOI -
- Views 95
- Downloads 0
Graphical Password Strength in Cloud Computing
Abstract: In a Network we have various issues to work with our services & data (maintenances) & today Cloud computing provides convenient on-demand network access to a shared pool of configurable enumerate resour...
Automated Detection of Microaneurysm, Hard Exudates, and Cotton Wool Spots in Retinal fundus Images
Abstract: The The automatic identification of Image processing techniques for abnormalities in retinal images. Its very importance in diabetic retinopathy screening. Manual annotations of retinal images are rare and excl...
A review on Visualization Approaches of Data mining in heavyspatial databases
Abstract: Data mining is the phenomenon to extract and recognized the new required pattern or types from thelarge data seta or data bases and whatever required data is being extracted and separated from large datab...
A Study on Relational Semantic Video Content Extraction Using Bayesian Network Classifier
Abstract: Multimedia data mining is an emergent field, which consists of image mining, video data mining etc. The content based extraction in videos is an important application due to the rapid growth in the video...
Comparative study on Cache Coherence Protocols
Abstract: In this new age of technology, not only the software but also the computer architecture has beenevoluted to support those softwares. The main motive of evolution of architecture day by day is to make thes...