Research Library

open-access-imgOpen AccessEfficient Algorithm for Auto Correction Using n-gram Indexing
Mahesh Lalwani,
Nishant Bagmar,
Saurin Parikh
Publication year2013
Auto correction functionality is very popular in search portals. Its principal purpose is to correct common spelling or typing errors, saving time for the user. However, when there are millions of strings in a dictionary, it takes considerable amount of time to find the nearest matching string. Various approaches have been proposed for efficiently implementing auto correction functionality. All of these approaches focus on using suitable data structure and few heuristics to solve the problems. Here, we propose a new idea which eliminates the need for calculating edit distance with each string in the dictionary. It uses the concept of Ngram based indexing and hashing to filter out irrelevant strings from dictionary. Experiments suggest that proposed algorithm provides both efficient and accurate results.
Subject(s)algorithm , approximate string matching , artificial intelligence , commentz walter algorithm , computer science , computer vision , edit distance , filter (signal processing) , focus (optics) , hash function , hash table , heuristics , language model , locality sensitive hashing , mathematical physics , mathematics , n gram , operating system , optics , pattern matching , physics , programming language , search engine indexing , string (physics) , string searching algorithm

Seeing content that should not be on Zendy? Contact us.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here