NDLI: An Improved Approach of Dictionary Based Syntactic PR Using Trie

Content Provider	IEEE Xplore Digital Library
Author	Pradhan, S.K. Negi, A.
Copyright Year	2014
Description	Author affiliation: Sch. of Comput. & Inf. Sci., Univ. of Hyderabad, Hyderabad, India (Pradhan, S.K.; Negi, A.)
Abstract	Dictionary based syntactic pattern recognition of strings attempts to extract a set of strings X+ from the dictionary H, by processing its noisy version string Y, without sequentially comparing Y with each element of X, the strings of H. H is the dictionary that contains a finite set of strings. The best estimate X+ from all X* in H, is defined as the set of string from X* that has least Levenshtein edit distance with the searched string Y. Existing techniques are there to search approximately from a dictionary. All strings compared with the searched string stored in dictionary the least distance string are the X+. Few techniques also there who use trie as data structure to store the words set of dictionary and uses some heuristic to prune some search space while finding the X+. Efficiency in search and retrieval depends upon the success in pruning out words from the computation while searching for an approximate match. In this paper, we store all the words of dictionary in a trie data structure. We propose heuristics that apply to every node of the trie. These heuristics help to prune the search current path at a node. Our method of pruning path while searching can save space in computation as compare to other method with correct approximation. We have tested our approach with different data sets with different noisy word and our method gave the correct X+, the approximate words set as result. The proposed approaches are compared with the existing approach. The first approach is giving 19.03% and second approach showing 29.35% eficiency compared to existing approach.
Sponsorship	IEEE Bombay Sect.
Starting Page	386
Ending Page	391
File Size	297628
Page Count	6
File Format	PDF
ISBN	9781479921027
DOI	10.1109/ICESC.2014.76
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-01-09
Publisher Place	India
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computers Syntactic pattern recognition Dictionaries Heuristic algorithms Approximate string matching Approximation algorithms Data structures Levenshtein edit distance Noise measurement Approximation methods Trie
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in