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
A Multi-Purpose Voice Controlled System on Android Platform
Abstract: This paper describes a method which helps in making Android operating system based mobile phonedetect a voice command and perform the operation accordingly. We also introduce a new secured backup and rest...
Classification of Cardiovascular Disease from ECG using Artificial Neural Network and Hidden Markov Model.
Abstract: this paper deals with the classification of cardiovascular disease for its future analysis. If future progression of the disease can be predicted earlier with proper change in medication patients treatmen...
Overview of Improving Robustness of MAODV Protocol byCombining Tree and Mesh Structures
Abstract: Mobile ad hoc networks (MANETs) plays an important role in the communication in the networkmust be set up temporarily and quickly. Since the nodes move randomly routing protocols must bring strong andcons...
Survey on Various Security Issues and prevention method in Vehicular Ad hoc Networks
Vehicular adhoc networks are a subset of mobile adhoc networks. This forms wireless network between vehicles for better communications and to break away from the hindrance caused by attackers. Various security ar...
Defended Data Embedding For Chiseler Avoidance in Visible Cryptography by Using Morphological Transform Domain
This paper proposes a data-veiling technique for binate images in morphological transform domain for authen- tication purpose. To attain blind watermark drawing, it is difficult to use the detail coordinate pre...