Spell Checker

Introduction:

In this part of the assignment I have developed a spell checker for Hindi which identifies and offer upto 3 suggestions for both real word and non-word errors. I have used Dr. Peter Norvig's code which is available at www.norvig.com/ngrams. I have made several other modifications considering that the words belong to Hindi.

Tokenization:

I combined all the three Hindi corpus available to us. Then using the python program getSentence.py and getSentence2.py written by me, I extracted the sentences from the corpus. Then words were simply obtained from the corpus by using getWords.py and bigrams and trigrams were extracted from the Sentence data collected from the corpus using getGram2.py and getGram3.py. In case of the starting of sentence the tag "S within <>" was used.

Trial and effects -

• Removing the words having count 1 - This was done in the view of the problem of removing the incorrect/corrupted words. But doing this changes the accuracy +-1% and doesn't have a major effect because the corpus we are using has many other mis-spelled words which may be due to the fact that writers of the sources from which we picked our data, also does not have a good knowledge of Hindi spellings.
• Removing the not possible words - This has always been helpful. Removing the words which can never occur, such as those beginning with a bindu or a halant will certainly help. Plus it will also discourage the system to segment the words which can never exist.
• Removed the zero width joiner (\u200d).

Using Norvig's code:

After obtaining the unigrams and bigrams for Hindi, I ran the Peter Norvig's code to correct incorrect words. The result obtained are as follows: Accuracy - 20%

Obsevation -

• Our likelihood probability was not defined.
• Segmentation of words were not taken into account.
• The alphabet list of Hindi characters was not exhaustive.
• Some segmentation problems:
  हज़ारों (correct) - हजारों (incorrect)
  अँधेरा (correct) - अंधेरा (incorrect)
  We got these errors due to the corpus. The word count of हजारों in the corpus is 1208 and that of हज़ारों (correct) is only 54. Similarly, अंधेरा is 286 and अँधेरा (correct) is 198.

Ground truth Modification:

There were some problems in the ground truth given to us. I modified them manually. However, this is not a necessary step but just an independent effort on my side.

• At some places there were inadvertent spaces. No more than 1 space was allowed.
• Some problems with unigram encodings was resolved u'\u091C'+u'\u093C'=u'\u905B'

Validation set:

Along with what was already given to us for testing, I pulled out a list of non-word errors and a list of sentences having real word errors. Thanks to Amit Sharma, who gave them to me. He had used the same for his AI project in which he designed a spell checker for Hindi. They all are present in my code folder (attached below) in the name of (test1.txt, test2.txt, test3.txt).

Algorithm:

Error of a word: If the length of a word is more than 8, it is first segmented and then error is determined for the smaller words along with the original word. Irrespective of being a real word or a non word, a list of candidate words is generated and the probability of each is found out as the product of the likelihood and prior probability. Here, the prior probability is taken from the unigram data. The top 3 results are offered as suggestions.

Error in a sentence: A basic assumption that there is only 1 error in a sentence is made. Now if, there is any non-word in the sentence then it is corrected and the correct sentence is shown as suggestion. Otherwise, we generate a list of top 5 candidate words for all the real words in a sentence. Probability of a sentence is found based on the bigram and trigram data of each new sentence which has 1 modified word. The top 3 sentences are shown as suggestions.

My Modifications:

Likelihood probability: It is the probability of an incorrect word given a correct word P(w/c). In general, (for English) we will look at a large set of mis-spellings and their corrections and from that we will built a set of possible edits and accordingly assign a probability for an edit. Dr. Norvig used 1587 unique edits for English which is only 26 characters. It we are supposed to follow the same procedure in Hindi which has about 60 characters we would need almost three times the data available for English. However, it turns out that we don't even 1/3rd of the data available to us. Therefore, the same likelihood probability for all cases, later on adding the phonetic rules.

Phonetic Rules: As phonetic information is expected to be of importance for Indian languages, I try to use the comprehensive, table-driven phonetic code mechanism. The rules allow specifying, for example, that क sounds like ख, क like क्, कि like की, कु like कू, etc. This turns out to be the single most important factor for improving the performance for Hindi. Apart from what already was provided by aspell, I added some more rules (न|ं ब|व) based on my knowledge and this link.

Other tweaks:

1. Assigning different probabilities: A set of edits based on phonological rules are compiled in hi_class1.dat file. A likelihood probability of 0.5 is assigned to any edit belonging to this class. Probability of no edit is also assigned 0.5 due to the huge no. of errors in the corpus. Any other edit is assigned 0.01. Furthermore, as we increase the edit distance, we don't want many insertions and deletions and hence they are given a lower weight over substitutions.
2. Adding क्ष as a character: Many spelling mistakes (छण:क्षण, छमा:क्षमा) occur mistaking क्ष as छ or vice-versa. But this would be have an edit-distance of 3. Therefore I added क्ष as an independent character.
3. Increasing edit distance: I observed that as the word length increases we might need to look for errors at a greater edit distance. Therefore, with an increase in the length of the word we increase our edit distance. I go to a maximum of 3 edit distance and it also makes sense to have greater edit distance as Hindi has huge lexical diversity.
4. Palindrome edits: Some errors in Hindi occur just due to the misplace of the र् symbol (आर्दश:आदर्श). In this kind of errors we have an edit distance 2 and they represent a palindrome. Therefore, I give those kind of palindrome edits a slightly higher probability.

Final result:

Test1 (Mailed to us by Prof. Mukerjee): Accuracy = 81.5%, With Aspell, accuracy = 64%

Test2 (Another list of word errors): Accuracy = 85%, With Aspell, accuracy = 75%

Test3 (Real word errors in sentences): Accuracy = 33%

Definition of Accuracy: If for a test case the correct spelling is found in the top 3 suggestions then it is counted in correct, otherwise it is counted in incorrect. Accuracy is report using the formula correct/(correct+incorrect).

There were some errors like:

1. मौकाएवारदात:मौका-ए-वारदात:मौका ए वारदात
2. पनडुब्बियां:पनडुब्बियाँ

Attached files:

• Code
• Vocabulary