Member-only story
Hands-on Tutorial
Graph Theory for Typo Corrector Using Python — How It Can Improve the String Matching Algorithm
How typo corrector can improve the string matching algorithm for matching the best string in the lexicon (master data)
After reading this short article, you will understand the implementation of graph theory for improving the string-matching algorithm. For any typos in our writing, the typo corrector not only calculates the string similarities between the input and the master database but also considers the distance between each character.
To get the distance of characters on the keyboard, the graph theory is proposed. The alphabet on the keyboard with a QWERTY layout will be restructured. Keep reading and find out the idea on how to implement graph theory for typos on the keyboard.
Problem identification
Typo might happen in writing. If you are using autocorrect, it will be replaced by the matchest one. For instance, if you were typing wsll, the autocorrect knows it is closer to well instead of will. How did the autocorrect know? Behind the user interface, the core process is performed, namely, string matching.
