nlp_basics/nltk/performance_comparison_of_spell_corrector.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data set Source\n",
    "\n",
    "Data set is downloaded from:\n",
    "\n",
    "https://en.wikipedia.org/wiki/Wikipedia:Lists_of_common_misspellings/A\n",
    "\n",
    "- Data set contains misspelled words and correct words\n",
    "- Words are selected randomly from data set\n",
    "- Around 670 words are selected randomly from data set to evaluate the performance of spell correctors\n",
    "\n",
    "## Two spell correcters are used\n",
    "\n",
    "    - Spell corrector using Ngrams,Jaccard coefficient and Minimum edit distance\n",
    "    - Spell corrector using Minimum Edit Distance(MED)\n",
    "   \n",
    "\n",
    "- Each spell corrector, checks misspelled word and suggest correct work according to misspelled word\n",
    "- Both spell correctors are evaluated based on their performance(accuracy of correcting words)\n",
    "\n",
    "### Spell Correction Using Ngram, Jaccard Coefficient and Edit Distance\n",
    "\n",
    "#### Steps performed:\n",
    "\n",
    "1. Find Misspelled words\n",
    "2. Check Suggested Words\n",
    "3. Filter suggested words which are different within some distance using edit distance\n",
    "4. Compute Ngram of misspelled word and each suggested word\n",
    "5. Compute Jaccard coefficient of misspelled word and each suggested word\n",
    "6. Replace suggested word with maximum jaccard coefficient\n",
    "\n",
    "\n",
    "# Levenshtein Distance(Minimum Edit distance) in NLTK\n",
    "\n",
    "It computes minimum edit distance between two strings by performing three operations:\n",
    "\n",
    "1. Substitution\n",
    "2. Insertion\n",
    "3. Deletion\n",
    "\n",
    "It is mainly used for spelling correction, I have tried to use as spelling corrector, but it does not performs always in optimal way\n",
    "\n",
    "\n",
    "# PyEnchant Library \n",
    "\n",
    "It is spell checking library for python, it has built-in english dictionary and functions to check the spelling of words in the sentences \n",
    "\n",
    "# Conclusion\n",
    "\n",
    "After evaluating performance of spell corrector using Ngram, Jaccard Coefficient, Edit Distance and spell corrector using Levenshtein distance(Minimum edit distance) on dataset of misspelled words from Wikipedia, both the methods have achieved accuracy of 69.19% and 59.75% respectively. It can be concluded that accuracy achieved is not sufficient to replace misspelled word by corrected word, but since in automatic short answer grading we need to detect misspelled words in student's answer, this can be done with the help of Pyenchant library.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from __future__ import division\n",
    "import numpy as np\n",
    "import enchant  # spell checker library pyenchant\n",
    "import string_similarity # import string similarity notebook"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Load enchant english dictionary\n",
    "spell_dictionary = enchant.Dict('en')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# create object of string similarity class(present in another notebook)\n",
    "obj = string_similarity.string_similarity(spell_dictionary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Load Data set that contain misspelled and corrected words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def load_misspelled_dataset(dataset):\n",
    "    words_dictionary = dict()\n",
    "    for i in range(len(dataset)):\n",
    "        words_dictionary[dataset[i][0]] = dataset[i][2] \n",
    "        \n",
    "    return words_dictionary\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "load_dataset = np.loadtxt('dataset/dataset_misspelled.txt',dtype='str')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Performance of Spell Corrector using Ngrams on Dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lee 666\n",
      "============================================================================================\n",
      "Total number of misspelled words in database 666\n",
      "Total number of corrected words 461\n",
      "Total percentage  69.2192192192\n",
      "============================================================================================\n"
     ]
    }
   ],
   "source": [
    "def check_misspelledWords_ngramCorrector(dataset):\n",
    "    number_of_corrected_words = 0\n",
    "    words = []\n",
    "    dictionary_misspelled_and_corrected_words = load_misspelled_dataset(dataset)\n",
    "    print \"lee\", len(dictionary_misspelled_and_corrected_words)\n",
    "    for i in range(len(dictionary_misspelled_and_corrected_words)):\n",
    "        corrected_word = obj.ngram_spell_corrector(dataset[i][0])\n",
    "        # if suggested word by ngram spell corrector is equal to correct word in data set\n",
    "        if corrected_word == dataset[i][2]:\n",
    "            number_of_corrected_words += 1\n",
    "    print \"============================================================================================\"\n",
    "    print \"Total number of misspelled words in database\", len(dictionary_misspelled_and_corrected_words) \n",
    "    print \"Total number of corrected words\",number_of_corrected_words\n",
    "    print \"Total percentage \", (number_of_corrected_words/len(dictionary_misspelled_and_corrected_words)) * 100\n",
    "    print \"============================================================================================\"\n",
    "check_misspelledWords_ngramCorrector(load_dataset)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Performance of Spell Corrector using Minimum Edit Distance(MED) on Dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "============================================================================================\n",
      "Total number of misspelled words in database 666\n",
      "Total number of corrected words 398\n",
      "Total percentage  59.7597597598\n",
      "============================================================================================\n"
     ]
    }
   ],
   "source": [
    "def check_misspelledWords_medCorrector(dataset):\n",
    "    number_of_corrected_words = 0\n",
    "    words = []\n",
    "    dictionary_misspelled_and_corrected_words = load_misspelled_dataset(dataset)\n",
    "    for i in range(len(dictionary_misspelled_and_corrected_words)):\n",
    "        corrected_word = obj.minimumEditDistance_spell_corrector(dataset[i][0])\n",
    "        if corrected_word == dataset[i][2]:\n",
    "            number_of_corrected_words += 1\n",
    "    print \"============================================================================================\"\n",
    "    print \"Total number of misspelled words in database\", len(dictionary_misspelled_and_corrected_words) \n",
    "    print \"Total number of corrected words\",number_of_corrected_words\n",
    "    print \"Total percentage \", (number_of_corrected_words/len(dictionary_misspelled_and_corrected_words)) * 100\n",
    "    print \"============================================================================================\"\n",
    "check_misspelledWords_medCorrector(load_dataset)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}