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 133
- Downloads 0
Growth and Development Strategy of It Software and Service Industry
Classifying Evaluation Secure Patterns under Attacks
Abstract: Pattern Classification is one division for machine discovering that spotlights on acknowledgment of examples and regularities in information. In antagonistic applications such as biometric verification, spam si...
Distribution of RSA Public Key with Security Device based Identity for Multi-Agent secured Distributed Computing System
Abstract: In Mobile Agent Technology, interoperability between agents is indispensably to secure the data from malicious agents under Multi-Agent System. To protect data and agents from malicious attacks, the multi-agent...
Encryption Technique for a Trusted Cloud ComputingEnvironment
With varying amount of computing power present with everyone, it has become necessity of the hour to usecloud computing systems. It helps us to store our data within a virtual cloud structure. When we use the cloud...
An Intelligence System for Detection of Cancer and Diagnosis
Abstract: Currently the digital images are used in various areas like medical, fashion, architecture, face recognition, finger print recognition and bio metrics. Recently the CBIR reduced the semantic gap between t...