Autocorrect using NLP
Tags: datascience, machinelearning, python
Published: 2020-10-10 21:22:35

In this era of Digitalization, almost every individual has a smartphone with them, may it be Android or iOS. The benefits of smartphone would be a never-ending list and we ain't going to focus on that in this blog ! The purpose of this post, as you can guess it from the title itself, is to build an Autocorrect System from Scratch. Yes, it's somewhat similar, definitely not the exact copy , to that of the smartphone you are using now, but this would be just an implementation of Natural Language Processing  on a comparatively smaller dataset- Shakespeare.txt (a file full of words used by William Shakespeare in his works). 
This algorithm was first created by __Peter Norvig__ back in 2007 in his [article](https://norvig.com/spell-correct.html).

# Overview of the Problem :
In this model, we are going to consider __edit distance__ between every pair of words in a list containing the vocabulary. Basically, edit distance is a **measure of minimum edits required to convert one word to another**.
This process of conversion includes steps like __Delete__,__Replace__,__Switch__ and __Insert__ on a pair of words. In this blog, to reduce complexity, we would go for words that are __1 or 2 edit distance away__.
The goal of our model to produce the right output is to compute the __probability of a word being correct, _P(c/w)_ ,is probability of certain word _w_ given that is is correct, _P(w/c)_ , multiplied to probability of being correct in general, _P(c)_ , divided by probability of that word appearing, _P(w)_ .__

Formula :               __𝑃(𝑐|𝑤)=𝑃(𝑤|𝑐)×𝑃(𝑐)/𝑃(𝑤)__

The method used above is called __Bayes Theorem__.

###_And we are all set for the journey ahead !_

Import the necessary packages :

```
import re
from collections import Counter
import numpy as np
import pandas as pd
```
Pre-processing the data :

```
def process_data(file_name):
    words = [] 
    with open(file_name) as f:
        file_name_data = f.read()
    file_name_data=file_name_data.lower()
    words = re.findall(r'\w+',file_name_data)

    return words

word_l = process_data('shakespeare.txt')
vocab = set(word_l)
```
Here we are using the function process data which takes the file 
_shakespeare.txt_ as input and returns a __words__, list of all words in the file by ignoring the numerical values and converting every word to lower case. Again, we set vocabulary for the text file , __vocab__ , as a set of all words from the list of words received by __word_l__, i.e making a list of all unique words.

Now, we would create a count dictionary for the words in vocab and their number of occurrences in the list of words from the input file :

```
def get_count(word_l):
    word_count_dict = {}  # fill this with word counts
    word_count_dict = Counter(word_l)
    return word_count_dict

word_count_dict = get_count(word_l)
``` 
The above function will return a dictionary, _word_count_dict_ where each word will be a key and the value assigned to each word will be the number of times it has appeared in the list of words _word_l_ .

Next, we will need a dictionary that will contain every word as the key and the value assigned to each key would be the probability of the occurrence of that specific word(key) in the input file _shakespeare.txt_.

```
def get_probs(word_count_dict):
    probs = {}  # return this variable correctly

    m = sum(word_count_dict.values())
    for key in word_count_dict :
        probs[key] = word_count_dict[key]/m
    return probs

probs = get_probs(word_count_dict)
```
_probs_ is the required dictionary that will contain each word _w_ and the respective probability _P(w)_.

Now, here comes the most important aspect of our model ! In the following code snippets below, we would be implementing functiones to carry out the tasks : __Delete__, __Switch__, __Replace__ and __Insert__ and return the respective list of words from each task.

```
def delete_letter(word):
    delete_l = []
    split_l = []
 
    for i in range(len(word)):
        split_l.append([word[:i],word[i:]])
    for a,b in split_l :
        delete_l.append(a+b[1:])

    return delete_l
```

```
def switch_letter(word):
    switch_l = []
    split_l = []
    
    for c in range(len(word)):
        split_l.append([word[:c],word[c:]])
    switch_l = [a + b[1] + b[0] + b[2:] for a,b in split_l if len(b) >= 2]    
   
    return switch_l
```

```
def replace_letter(word):
    letters = 'abcdefghijklmnopqrstuvwxyz'
    replace_l = []
    split_l = []
    
    for c in range(len(word)):
        split_l.append((word[0:c],word[c:]))
    replace_l = [a + l + (b[1:] if len(b)> 1 else '') for a,b in split_l if b for l in letters]
    replace_set=set(replace_l)    
    replace_set.remove(word)
    # turn the set back into a list and sort it, for easier viewing
    replace_l = sorted(list(replace_set))
   
    return replace_l
```

```
def insert_letter(word):
    letters = 'abcdefghijklmnopqrstuvwxyz'
    insert_l = []
    split_l = []

    for c in range(len(word)+1):
        split_l.append((word[0:c],word[c:]))
    insert_l = [ a + l + b for a,b in split_l for l in letters]
 
    return insert_l
```

The functions used above produce lists of words on specific type of edits. We need to use these as a whole for each word in the list of input words from the file by using the __n-edit distance algorithm__ where we will use __n=1,2__ only.

So, if we want to edit __one letter at a time__ then we choose __n=1__ and implement the following function :

```
def edit_one_letter(word, allow_switches = True):
    edit_one_set = set()
    
    edit_one_set.update(delete_letter(word))
    if allow_switches:
        edit_one_set.update(switch_letter(word))
    edit_one_set.update(replace_letter(word))
    edit_one_set.update(insert_letter(word))

    return edit_one_set
```
Similarly, if we choose to edit __two letters at a time__, so we go for __n=2__ and implement the following function on our list of words, that is going to use the above function two times, i.e first on actual set of words and second on every word in the output of above function :

```
def edit_two_letters(word, allow_switches = True):
    edit_two_set = set()
    
    edit_one = edit_one_letter(word,allow_switches=allow_switches)
    for w in edit_one:
        if w:
            edit_two = edit_one_letter(w,allow_switches=allow_switches)
            edit_two_set.update(edit_two)
    
    return edit_two_set
```
Finally, we will use __edit_two_letters()__ and __edit_one_letter()__  in the given function to get a list of all suggested words along with their respective probabilities in a list named __n_best__.

```
def get_corrections(word, probs, vocab, n=2):    
    suggestions = []
    n_best = []
    
    suggestions = list((word in vocab and word) or edit_one_letter(word).intersection(vocab) or edit_two_letters(word).intersection(vocab))
    n_best = [[s,probs[s]] for s in list(reversed(suggestions))]
   
    return n_best
```

Here, _suggestions_ will have the words that are in vocab or the common words between the list of words obtained from _edit_one_letter()_ and vocab or _edit_two_letters()_ and vocab.
As it can be seen, __n_best__ returns the list of all suggested words with their respective probabilities of being correct.

#Testing our Model :

The following code snippet will be used to test our Autocorrect Model :

```
my_word = 'dys' 
tmp_corrections = get_corrections(my_word, probs, vocab, 2) 
for i, word_prob in enumerate(tmp_corrections):
    print(f"word {i}: {word_prob[0]}, probability {word_prob[1]:.6f}")
```
The results obtained were : __dye__ with probability of __0.000019__ and __days__ with probability __0.000410__ .

#####**That's all Folks !**
This is how you can make your own autocorrect model using Natural Language Processing and Python.   
Thank you for your valuable time and patience !