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 104
- Downloads 0
Monitoring Wireless Sensor Network using Android based Smart Phone Application
Abstract: Wireless Sensor Network application’s is use in detection of natural calamities like forest fire detection, flood detection, , earth quick early detection ,snow detection, traffic congestion and various o...
A Study to the different implementation approaches for the Grid YM-Algorithm DNA alignment
Abstract: DNA Multiple sequence alignment is common bioinformatics application that determines the similarity between a new sequence with other exist sequences. Needleman-Wunsch algorithm is the most famous algorithm for...
An Efficient Method to Prevent Information Leakage in Cloud
Abstract : Cloud Computing is storing and accessing data and programs over the Internet instead of personal computers. It is a computing paradigm shift where computing is moved away from personal computers or an in...
Off-Line Signature Verification Using Principal ComponentVariances
Abstract: Signature verification system is always the most sought after biometric verification system. Being abehavioral biometric feature which can always be imitated, the researcher faces a challenge in designing...
Analysis of service-oriented traffic classification with imperfect traffic classification methods
Typically the traffic through the network is heterogeneous and it flows from multiple utilities and applications Considering todays threats in network there is yet not a single solution to solve all the issues be...