Word_Prediction_GoodTuring_Smoothing_with_Interpolation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <u>Word prediction</u> \n",
    "### Language Model based on n-gram Probabilistic Model\n",
    "### Good Turing Smoothing Used with Interpolation\n",
    "### Highest Order n-gram used is Quadgram\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Import corpus</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.util import ngrams\n",
    "from collections import defaultdict\n",
    "from collections import OrderedDict\n",
    "import string\n",
    "import time\n",
    "import gc\n",
    "from math import log10\n",
    "start_time = time.time()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Do preprocessing</u>:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Remove the punctuations and lowercase the tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#returns: string\n",
    "#arg: string\n",
    "#remove punctuations and make the string lowercase\n",
    "def removePunctuations(sen):\n",
    "    #split the string into word tokens\n",
    "    temp_l = sen.split()\n",
    "    #print(temp_l)\n",
    "    i = 0\n",
    "    j = 0\n",
    "    \n",
    "    #changes the word to lowercase and removes punctuations from it\n",
    "    for word in temp_l :\n",
    "        j = 0\n",
    "        #print(len(word))\n",
    "        for l in word :\n",
    "            if l in string.punctuation:\n",
    "                if l == \"'\":\n",
    "                    if j+1<len(word) and word[j+1] == 's':\n",
    "                        j = j + 1\n",
    "                        continue\n",
    "                word = word.replace(l,\" \")\n",
    "                #print(j,word[j])\n",
    "            j += 1\n",
    "\n",
    "        temp_l[i] = word.lower()\n",
    "        i=i+1   \n",
    "\n",
    "    #spliting is being don here beacause in sentences line here---so after punctuation removal it should \n",
    "    #become \"here so\"   \n",
    "    content = \" \".join(temp_l)\n",
    "\n",
    "    return content"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tokenize and load the corpus data\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#returns : int\n",
    "#arg: string,dict,dict,dict,dict\n",
    "#loads the corpus for the dataset and makes the frequency count of quadgram ,bigram and trigram strings\n",
    "def loadCorpus(file_path, bi_dict, tri_dict, quad_dict, vocab_dict):\n",
    "\n",
    "    w1 = ''    #for storing the 3rd last word to be used for next token set\n",
    "    w2 = ''    #for storing the 2nd last word to be used for next token set\n",
    "    w3 = ''    #for storing the last word to be used for next token set\n",
    "    token = []\n",
    "    #total no. of words in the corpus\n",
    "    word_len = 0\n",
    "\n",
    "    #open the corpus file and read it line by line\n",
    "    with open(file_path,'r') as file:\n",
    "        for line in file:\n",
    "\n",
    "            #split the string into word tokens\n",
    "            temp_l = line.split()\n",
    "            i = 0\n",
    "            j = 0\n",
    "            \n",
    "            #does the same as the removePunctuations() function,implicit declratation for performance reasons\n",
    "            #changes the word to lowercase and removes punctuations from it\n",
    "            for word in temp_l :\n",
    "                j = 0\n",
    "                #print(len(word))\n",
    "                for l in word :\n",
    "                    if l in string.punctuation:\n",
    "                        if l == \"'\":\n",
    "                            if j+1<len(word) and word[j+1] == 's':\n",
    "                                j = j + 1\n",
    "                                continue\n",
    "                        word = word.replace(l,\" \")\n",
    "                        #print(j,word[j])\n",
    "                    j += 1\n",
    "\n",
    "                temp_l[i] = word.lower()\n",
    "                i=i+1   \n",
    "\n",
    "            #spliting is being done here beacause in sentences line here---so after punctuation removal it should \n",
    "            #become \"here so\"   \n",
    "            content = \" \".join(temp_l)\n",
    "\n",
    "            token = content.split()\n",
    "            word_len = word_len + len(token)  \n",
    "\n",
    "            if not token:\n",
    "                continue\n",
    "\n",
    "            #add the last word from previous line\n",
    "            if w3!= '':\n",
    "                token.insert(0,w3)\n",
    "\n",
    "            temp0 = list(ngrams(token,2))\n",
    "\n",
    "            #since we are reading line by line some combinations of word might get missed for pairing\n",
    "            #for trigram\n",
    "            #first add the previous words\n",
    "            if w2!= '':\n",
    "                token.insert(0,w2)\n",
    "\n",
    "            #tokens for trigrams\n",
    "            temp1 = list(ngrams(token,3))\n",
    "\n",
    "            #insert the 3rd last word from previous line for quadgram pairing\n",
    "            if w1!= '':\n",
    "                token.insert(0,w1)\n",
    "\n",
    "            #add new unique words to the vocaulary set if available\n",
    "            for word in token:\n",
    "                if word not in vocab_dict:\n",
    "                    vocab_dict[word] = 1\n",
    "                else:\n",
    "                    vocab_dict[word]+= 1\n",
    "                  \n",
    "            #tokens for quadgrams\n",
    "            temp2 = list(ngrams(token,4))\n",
    "\n",
    "            #count the frequency of the bigram sentences\n",
    "            for t in temp0:\n",
    "                sen = ' '.join(t)\n",
    "                bi_dict[sen] += 1\n",
    "\n",
    "            #count the frequency of the trigram sentences\n",
    "            for t in temp1:\n",
    "                sen = ' '.join(t)\n",
    "                tri_dict[sen] += 1\n",
    "\n",
    "            #count the frequency of the quadgram sentences\n",
    "            for t in temp2:\n",
    "                sen = ' '.join(t)\n",
    "                quad_dict[sen] += 1\n",
    "\n",
    "\n",
    "            #then take out the last 3 words\n",
    "            n = len(token)\n",
    "\n",
    "            #store the last few words for the next sentence pairing\n",
    "            if (n -3) >= 0:\n",
    "                w1 = token[n -3]\n",
    "            if (n -2) >= 0:\n",
    "                w2 = token[n -2]\n",
    "            if (n -1) >= 0:\n",
    "                w3 = token[n -1]\n",
    "    return word_len"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Hash Table for Probable words for Trigram sentences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#returns: void\n",
    "#arg: dict,dict,dict,dict,dict,dict,int\n",
    "#creates dict for storing probable words with their probabilities for a trigram sentence\n",
    "def findQuadgramProbGT(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict, nc_dict, k):\n",
    "    \n",
    "    i = 0\n",
    "    V = len(vocab_dict)\n",
    "   \n",
    "    for quad_sen in quad_dict:\n",
    "        quad_token = quad_sen.split()\n",
    "        \n",
    "        #trigram sentence for key\n",
    "        tri_sen = ' '.join(quad_token[:3])\n",
    "\n",
    "        #find the probability\n",
    "        #Good Turing smoothing has been used\n",
    "        quad_count = quad_dict[quad_sen]\n",
    "        tri_count = tri_dict[tri_sen]\n",
    "        \n",
    "        if quad_dict[quad_sen] <= k  or (quad_sen not in quad_dict):\n",
    "            quad_count = findGoodTuringAdjustCount( quad_dict[quad_sen], k, nc_dict)\n",
    "        if tri_dict[tri_sen] <= k  or (tri_sen not in tri_dict):\n",
    "            tri_count = findGoodTuringAdjustCount( tri_dict[tri_sen], k, nc_dict)\n",
    "        \n",
    "        prob = quad_count / tri_count\n",
    "        \n",
    "        #add the trigram to the quadgram probabiltity dict\n",
    "        if tri_sen not in quad_prob_dict:\n",
    "            quad_prob_dict[tri_sen] = []\n",
    "            quad_prob_dict[tri_sen].append([prob,quad_token[-1]])\n",
    "        else:\n",
    "            quad_prob_dict[tri_sen].append([prob,quad_token[-1]])\n",
    "\n",
    "    prob = None\n",
    "    quad_token = None\n",
    "    tri_sen = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Hash Table for Probable words for Bigram sentences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#returns: void\n",
    "#arg: dict,dict,dict,dict,dict,int\n",
    "#creates dict for storing probable words with their probabilities for a bigram sentence\n",
    "def findTrigramProbGT(vocab_dict, bi_dict, tri_dict, tri_prob_dict, nc_dict, k):\n",
    "    \n",
    "    #vocabulary length\n",
    "    V = len(vocab_dict)\n",
    "    \n",
    "    #create a dictionary of probable words with their probabilities for\n",
    "    #trigram probabilites,key is a bigram and value is a list of prob and word\n",
    "    for tri in tri_dict:\n",
    "        tri_token = tri.split()\n",
    "        #bigram sentence for key\n",
    "        bi_sen = ' '.join(tri_token[:2])\n",
    "        \n",
    "        #find the probability\n",
    "        #Good Turing smoothing has been used\n",
    "        tri_count = tri_dict[tri]\n",
    "        bi_count = bi_dict[bi_sen]\n",
    "        \n",
    "        if tri_dict[tri] <= k or (tri not in tri_dict):\n",
    "            tri_count = findGoodTuringAdjustCount( tri_dict[tri], k, nc_dict)\n",
    "        if bi_dict[bi_sen] <= k or (bi_sen not in bi_dict):\n",
    "            bi_count = findGoodTuringAdjustCount( bi_dict[bi_sen], k, nc_dict)\n",
    "        \n",
    "        prob = tri_count / bi_count\n",
    "        \n",
    "        #add the bigram sentence  to the trigram probability dict\n",
    "        #tri_prob_dict is a dict of list\n",
    "        if bi_sen not in tri_prob_dict:\n",
    "            tri_prob_dict[bi_sen] = []\n",
    "            tri_prob_dict[bi_sen].append([prob,tri_token[-1]])\n",
    "        else:\n",
    "            tri_prob_dict[bi_sen].append([prob,tri_token[-1]])\n",
    "            \n",
    "    prob = None\n",
    "    tri_token = None\n",
    "    bi_sen = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Hash Table for Probable words for Unigram"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#returns: void\n",
    "#arg: dict,dict,dict,dict,int\n",
    "#creates dict for storing probable words with their probabilities for a unigram\n",
    "def findBigramProbGT(vocab_dict, bi_dict, bi_prob_dict, nc_dict, k):\n",
    "    \n",
    "    #vocabulary size\n",
    "    V = len(vocab_dict)\n",
    "    \n",
    "    #create a dictionary of probable words with their probabilities for bigram probabilites\n",
    "    for bi in bi_dict:\n",
    "        bi_token = bi.split()\n",
    "        #unigram for key\n",
    "        unigram = bi_token[0]\n",
    "       \n",
    "        #find the probability\n",
    "        #Good Turing smoothing has been used\n",
    "        bi_count = bi_dict[bi]\n",
    "        uni_count = vocab_dict[unigram]\n",
    "        \n",
    "        if bi_dict[bi] <= k or (bi not in bi_dict):\n",
    "            bi_count = findGoodTuringAdjustCount( bi_dict[bi], k, nc_dict)\n",
    "        if vocab_dict[unigram] <= k or (unigram not in vocab_dict):\n",
    "            uni_count = findGoodTuringAdjustCount( vocab_dict[unigram], k, nc_dict)\n",
    "        \n",
    "        prob = bi_count / uni_count\n",
    "        \n",
    "        #add the unigram to the bigram probability dict\n",
    "        #bi_prob_dict is a dict of list\n",
    "        if unigram not in bi_prob_dict:\n",
    "            bi_prob_dict[unigram] = []\n",
    "            bi_prob_dict[unigram].append([prob,bi_token[-1]])\n",
    "        else:\n",
    "            bi_prob_dict[unigram].append([prob,bi_token[-1]])\n",
    "    \n",
    "    prob = None\n",
    "    bi_token = None\n",
    "    unigram = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sort the probable words for the various Probability Dictionaries according to their probability"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#returns: void\n",
    "#arg: dict\n",
    "#for sorting the probable word acc. to their probabilities\n",
    "def sortProbWordDict(bi_prob_dict, tri_prob_dict, quad_prob_dict):\n",
    "    for key in bi_prob_dict:\n",
    "        if len(bi_prob_dict[key])>1:\n",
    "            bi_prob_dict[key] = sorted(bi_prob_dict[key],reverse = True)\n",
    "    \n",
    "    for key in tri_prob_dict:\n",
    "        if len(tri_prob_dict[key])>1:\n",
    "            tri_prob_dict[key] = sorted(tri_prob_dict[key],reverse = True)\n",
    "    \n",
    "    for key in quad_prob_dict:\n",
    "        if len(quad_prob_dict[key])>1:\n",
    "            quad_prob_dict[key] = sorted(quad_prob_dict[key],reverse = True)[:2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>For Taking input from the User</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#returns: string\n",
    "#arg: void\n",
    "#for taking input from user\n",
    "def takeInput():\n",
    "    cond = False\n",
    "    #take input\n",
    "    while(cond == False):\n",
    "        sen = input('Enter the string\\n')\n",
    "        sen = removePunctuations(sen)\n",
    "        temp = sen.split()\n",
    "        if len(temp) < 3:\n",
    "            print(\"Please enter atleast 3 words !\")\n",
    "        else:\n",
    "            cond = True\n",
    "            temp = temp[-3:]\n",
    "    sen = \" \".join(temp)\n",
    "    return sen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Test Score ,Perplexity Calculation:</u>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For computing the Test Score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#computes the score for test data\n",
    "def computeTestScore(test_token, bi_dict, tri_dict, quad_dict, \n",
    "                             vocab_dict,token_len, param, k, quad_nc_dict, tri_nc_dict,\n",
    "                              bi_nc_dict, uni_nc_dict ):\n",
    "     #increment the score value if correct prediction is made else decrement its value\n",
    "    score = 0\n",
    "    wrong = 0\n",
    "    total = 0\n",
    "    with open('Test_Scores/Good_Turing_Interpolated_Score.txt','w') as w:\n",
    "        for sent in test_token:\n",
    "            sen_token = sent[:3]\n",
    "            sen = \" \".join(sen_token)\n",
    "            correct_word = sent[3]\n",
    "            #find the the most probable words for the bigram, trigram and unigram  sentence               \n",
    "            word_choice = chooseWords(sen, bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "\n",
    "            result = doInterpolatedPredictionGT(sen, bi_dict, tri_dict, quad_dict, \n",
    "                             vocab_dict,token_len, word_choice, param, k, quad_nc_dict, tri_nc_dict,\n",
    "                              bi_nc_dict, uni_nc_dict )\n",
    "            if result:\n",
    "                if result[1] == correct_word:\n",
    "                    score+=1\n",
    "                else:\n",
    "                    wrong += 1\n",
    "            else:\n",
    "                wrong += 1\n",
    "            total += 1\n",
    "            \n",
    "        w.write('Total Word Prdictions: '+str(total) + '\\n' +'Correct Prdictions: '+str(score) +\n",
    "                '\\n'+'Wrong Prdictions: '+str(wrong) + '\\n'+'ACCURACY: '+str((score/total)*100)+'%' )\n",
    "        #print stats\n",
    "        print('Total Word Prdictions: '+str(total) + '\\n' +'Correct Prdictions: '+str(score) +\n",
    "                '\\n'+'Wrong Prdictions: '+str(wrong) + '\\n'+'ACCURACY:'+str((score/total)*100)+'%' )\n",
    "    return score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For Computing the Perplexity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "#return:float\n",
    "#arg:list,int,dict,dict,dict,dict\n",
    "#computes the score for test data\n",
    "def computePerplexity(test_quadgrams, bi_dict, tri_dict, quad_dict, \n",
    "                                     vocab_dict,token_len, param, k, quad_nc_dict, tri_nc_dict,\n",
    "                                      bi_nc_dict, uni_nc_dict):\n",
    "    \n",
    "    perplexity = float(1.0)\n",
    "    n = token_len\n",
    "    \n",
    "    for key in quad_dict:\n",
    "        quad_token = key.split()\n",
    "         \n",
    "        quad_count = quad_dict[key]\n",
    "        tri_count = tri_dict[' '.join(quad_token[0:3])]\n",
    "        \n",
    "        if quad_dict[key] <= k or (key not in quad_dict):\n",
    "            quad_count = findGoodTuringAdjustCount( quad_dict[key], k, quad_nc_dict)\n",
    "        if tri_dict[' '.join(quad_token[0:3])] <= k  or (' '.join(quad_token[0:3]) not in tri_dict):\n",
    "            tri_count = findGoodTuringAdjustCount( tri_dict[' '.join(quad_token[0:3])], k, tri_nc_dict)\n",
    "        prob = quad_count / tri_count\n",
    "        if prob != 0:\n",
    "            perplexity = perplexity * ( prob**(1./n))\n",
    "    with open('Test_Scores/Good_Turing_Interpolated_Score.txt','a') as w:\n",
    "        w.write('\\nPerplexity: '+str(perplexity))\n",
    "    \n",
    "    return perplexity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Regression related stuff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## Regression related stuff\n",
    "#calculate best fit line for simple regression \n",
    "from statistics import mean\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt \n",
    "from matplotlib import style\n",
    "\n",
    "#finds the slope for the best fit line\n",
    "def findBestFitSlope(x,y):\n",
    "    m = (( mean(x)*mean(y) - mean(x*y) ) / \n",
    "          ( mean(x)** 2 - mean(x**2)))\n",
    "\n",
    "    return m\n",
    "      \n",
    "#finds the intercept for the best fit line\n",
    "def findBestFitIntercept(x,y,m):\n",
    "    c = mean(y) - m*mean(x)\n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find the count Nc for quadgrams and trigrams where c > 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Find the count Nc for quadgrams and trigrams where c > 5\n",
    "#arg: dict, int, int, int, int\n",
    "#returns: dict\n",
    "#token_len : total no. of ngram tokens\n",
    "def findFrequencyOfFrequencyCount(ngram_dict, k, n, V, token_len):\n",
    "    #for keeping count of 'c' value i.e Nc\n",
    "    nc_dict = {}\n",
    "    #we find the value of Nc,c = 0 by V^n - (total n-gram tokens)\n",
    "    nc_dict[0] = V**n - token_len\n",
    "    #find the count Nc till c = k,we will take k = 5\n",
    "    #find counts for n-gram\n",
    "    for key in ngram_dict:\n",
    "        if ngram_dict[key] <= k + 1:\n",
    "            if ngram_dict[key] not in nc_dict:\n",
    "                nc_dict[ ngram_dict[key]] = 1\n",
    "            else:\n",
    "                nc_dict[ ngram_dict[key] ] += 1\n",
    "    \n",
    "    #check if all the values of Nc are there in the nc_dict or not ,if there then return           \n",
    "    val_present = True\n",
    "    for i in range(1,7):\n",
    "        if i not in nc_dict:\n",
    "            val_present = False\n",
    "            break\n",
    "    if val_present == True:\n",
    "        return nc_dict\n",
    "    \n",
    "    #now fill in the values of nc in case it is not there using regression upto c = 6\n",
    "    #we use :[ log(Nc) = blog(c) + a ] as the equation\n",
    "\n",
    "    #we first need to find data for regression that is values(Nc,c) we take 5 data points\n",
    "    data_pts = {}\n",
    "    i = 0\n",
    "    #get first 5 counts value i.e c\n",
    "    #for quadgram\n",
    "    for key in ngram_dict:\n",
    "        if ngram_dict[key] not in data_pts:\n",
    "                data_pts[ ngram_dict[key] ] = 1\n",
    "                i += 1\n",
    "        if i >5:\n",
    "            break\n",
    "            \n",
    "    #now get Nc for those c values\n",
    "    for key in ngram_dict:\n",
    "        if ngram_dict[key] in data_pts:\n",
    "            data_pts[ ngram_dict[key] ] += 1\n",
    "    \n",
    "    #make x ,y coordinates for regression \n",
    "    x_coor = [ np.log(item) for item in data_pts ]\n",
    "    y_coor = [ np.log( data_pts[item] ) for item in data_pts ]\n",
    "    x = np.array(x_coor, dtype = np.float64)\n",
    "    y = np.array(y_coor , dtype = np.float64)\n",
    "   \n",
    "\n",
    "    #now do regression\n",
    "    #find the slope and intercept for the regression equation\n",
    "    slope_m = findBestFitSlope(x,y)\n",
    "    intercept_c = findBestFitIntercept(x,y,slope_m)\n",
    "\n",
    "    #now find the missing Nc terms and give them value using regression\n",
    "    for i in range(1,(k+2)):\n",
    "        if i not in nc_dict:\n",
    "            nc_dict[i] = (slope_m*i) + intercept_c\n",
    "    \n",
    "    return nc_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## For finding the Good Turing Probability"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#for finding the adjusted count c* in Good Turing Smoothing\n",
    "def findGoodTuringAdjustCount(c, k, nc_dict):\n",
    "   \n",
    "    adjust_count = ( ( (( c + 1)*( nc_dict[c + 1] / nc_dict[c])) - ( c * (k+1) * nc_dict[k+1] / nc_dict[1]) ) /\n",
    "                     ( 1 - (( k + 1)*nc_dict[k + 1] / nc_dict[1]) )\n",
    "                   )\n",
    "    return adjust_count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Parameter estimation\n",
    "For estimating parameters we try to maximise the value of lambdas l1,l2,l3 and l4<br>\n",
    "We do that by try all possible combinations of lambdas with step size 0.1 and try to maximise the \n",
    "<br> probabilty of held out data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#finds the lambda values required for doing Interpolation\n",
    "\n",
    "#arg: int, dict, dict, dict, dict\n",
    "#returns: list\n",
    "def estimateParameters(token_len, vocab_dict, bi_dict, tri_dict, quad_dict):\n",
    "    max_prob = -9999999999999999999.0\n",
    "    curr_prob = 0.0\n",
    "    parameters = [0.0,0.0,0.0,0.0]\n",
    "    i = 1\n",
    "    \n",
    "    #load the held out data \n",
    "    file = open('held_out_corpus.txt','r')\n",
    "    held_out_data = file.read()\n",
    "    file.close()\n",
    "    \n",
    "    #remove punctuations and other cleaning stuff\n",
    "    held_out_data = removePunctuations(held_out_data)\n",
    "    held_out_data = held_out_data.split()\n",
    "    #make quad tokens for parameter estimation\n",
    "    quad_token_heldout = list(ngrams(held_out_data,4))\n",
    "    \n",
    "    #for storing the stats \n",
    "    f = open('interpolation_prob_stats.txt','w') \n",
    "    \n",
    "    #lambda values1 and 4\n",
    "    l1 = 0\n",
    "    l4 = 0\n",
    "\n",
    "    while l1 <= 1.0:\n",
    "        l2 = 0\n",
    "        while l2 <= 1.0:\n",
    "            l3 = 0\n",
    "            while l3 <= 1.0:\n",
    "                \n",
    "                #when the sum of lambdas is greater than 1 or when all 4 are zero we don't need to check so skip\n",
    "                if l1 == 0 and l2 == 0 and l3 == 0 or ((l1+l2+l3)>1):\n",
    "                    l3 += 0.1\n",
    "                    i += 1\n",
    "                    continue\n",
    "                    \n",
    "                #find lambda 4\n",
    "                l4 = 1- (l1 + l2 + l3)\n",
    "                \n",
    "                curr_prob = 0\n",
    "                qc = [0]\n",
    "                bc = [0]\n",
    "                tc = [0]\n",
    "                \n",
    "                #find the probability for the held out set using the current lambda values\n",
    "                for quad in quad_token_heldout:\n",
    "                    #take log of prob to avoid underflow \n",
    "                    curr_prob += log10( interpolatedProbability(quad,token_len, vocab_dict, bi_dict, tri_dict, \n",
    "                                                                quad_dict,qc,bc,tc,l1, l2, l3, l4) )\n",
    "                \n",
    "                if curr_prob > max_prob:\n",
    "                    max_prob = curr_prob\n",
    "                    parameters[0] = l1\n",
    "                    parameters[1] = l2\n",
    "                    parameters[2] = l3\n",
    "                    parameters[3] = l4\n",
    "                l3 += 0.1\n",
    "                i += 1\n",
    "               \n",
    "            l2 += 0.1\n",
    "        l1 += 0.1\n",
    "    \n",
    "    f.write('\\n\\n\\nL1: '+str(parameters[0])+'  L2: '+str(parameters[1])+'  L3: '+str(parameters[2])+'  L4: '+str(parameters[3])+'  MAX PROB: '+str(max_prob)+'\\n')        \n",
    "    f.close()\n",
    "    return parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For choosing Probable words as Word Prediction candidate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#pick the top most probable words from bi,tri and quad prob dict as word prediction candidates\n",
    "\n",
    "#returns: list[float,string]\n",
    "#arg: string,dict,dict,dict\n",
    "def chooseWords(sen, bi_prob_dict, tri_prob_dict, quad_prob_dict):\n",
    "    word_choice = []\n",
    "    token = sen.split()\n",
    "    if token[-1] in bi_prob_dict:\n",
    "        word_choice +=  bi_prob_dict[token[-1]][:1]\n",
    "        #print('Word Choice bi dict')\n",
    "    if ' '.join(token[1:]) in tri_prob_dict:\n",
    "        word_choice +=  tri_prob_dict[' '.join(token[1:])][:1]\n",
    "        #print('Word Choice tri_dict')\n",
    "    if ' '.join(token) in quad_prob_dict:\n",
    "        word_choice += quad_prob_dict[' '.join(token)][:1]\n",
    "        #print('Word Choice quad_dict')\n",
    "    \n",
    "    return word_choice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Driver function for doing the prediction</u>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Do word Prediction using Interpolation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "#For doing word prediction using Interpolation\n",
    "def doInterpolatedPredictionGT(sen, bi_dict, tri_dict, quad_dict, \n",
    "                             vocab_dict,token_len, word_choice, param, k, quad_nc_dict, tri_nc_dict,\n",
    "                              bi_nc_dict, uni_nc_dict ):\n",
    "    \n",
    "    \n",
    "    pred = ''\n",
    "    max_prob = 0.0\n",
    "    V = len(vocab_dict)\n",
    "    #for each word choice find the interpolated probability and decide\n",
    "    for word in word_choice:\n",
    "        key = sen + ' ' + word[1]\n",
    "        quad_token = key.split()\n",
    "        \n",
    "        #find the Good Turing probabilty for quadgram probability\n",
    "        quad_count = quad_dict[key]\n",
    "        tri_count = tri_dict[' '.join(quad_token[0:3])]\n",
    "        \n",
    "        if quad_dict[key] <= k or (key not in quad_dict):\n",
    "            quad_count = findGoodTuringAdjustCount( quad_dict[key], k, quad_nc_dict)\n",
    "        if tri_dict[' '.join(quad_token[0:3])] <= k  or (' '.join(quad_token[0:3]) not in tri_dict):\n",
    "            tri_count = findGoodTuringAdjustCount( tri_dict[' '.join(quad_token[0:3])], k, tri_nc_dict)\n",
    "        quad_prob = quad_count / tri_count\n",
    "        \n",
    "        #find the Good Turing probabilty for trigram probability\n",
    "        tri_count = tri_dict[' '.join(quad_token[1:4])]\n",
    "        bi_count = bi_dict[' '.join(quad_token[1:3])]\n",
    "        \n",
    "        if tri_dict[' '.join(quad_token[1:4])] <= k  or (' '.join(quad_token[1:4]) not in tri_dict):\n",
    "            tri_count = findGoodTuringAdjustCount( tri_dict[' '.join(quad_token[1:4])], k, tri_nc_dict)\n",
    "        if bi_dict[' '.join(quad_token[1:3])] <= k or (' '.join(quad_token[1:3]) not in bi_dict):\n",
    "            bi_count = findGoodTuringAdjustCount( bi_dict[' '.join(quad_token[1:3])], k, bi_nc_dict)\n",
    "        tri_prob = tri_count / bi_count\n",
    "       \n",
    "        #find the Good Turing probabilty for bigram probability\n",
    "        bi_count = bi_dict[' '.join(quad_token[2:4])]\n",
    "        uni_count = vocab_dict[quad_token[2]]\n",
    "        \n",
    "        if bi_dict[' '.join(quad_token[2:4])] <= k or (' '.join(quad_token[2:4]) not in bi_dict):\n",
    "            bi_count = findGoodTuringAdjustCount( bi_dict[' '.join(quad_token[2:4])], k, bi_nc_dict)\n",
    "        if vocab_dict[quad_token[2]] <= k or (quad_token[2] not in vocab_dict):\n",
    "            uni_count = findGoodTuringAdjustCount( vocab_dict[quad_token[2]], k, uni_nc_dict)\n",
    "        bi_prob = bi_count / uni_count\n",
    "        \n",
    "        #find the Good Turing probabilty for unigram probability\n",
    "        uni_count = vocab_dict[quad_token[3]]\n",
    "        \n",
    "        if vocab_dict[quad_token[3]] <= k or (quad_token[3] not in vocab_dict):\n",
    "            bi_count = findGoodTuringAdjustCount( vocab_dict[quad_token[3]], k, uni_nc_dict)\n",
    "        uni_prob = uni_count / token_len\n",
    "        \n",
    "        prob = (   \n",
    "                  param[0]*( quad_prob ) \n",
    "                + param[1]*( tri_prob ) \n",
    "                + param[2]*( bi_prob ) \n",
    "                + param[3]*(uni_prob)\n",
    "               )\n",
    "       \n",
    "        if prob > max_prob:\n",
    "            max_prob = prob\n",
    "            pred = word\n",
    "    #return only pred to get word with its prob\n",
    "    if pred:\n",
    "        return pred\n",
    "    else:\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Driver Function for Testing the Language Model</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "#return: void\n",
    "#arg:string,string,dict,dict,dict,dict,dict\n",
    "#Used for testing the Language Model\n",
    "def trainCorpus(train_file,test_file,bi_dict,tri_dict,quad_dict,vocab_dict,prob_dict):\n",
    "      \n",
    "    test_result = ''\n",
    "    score = 0\n",
    "    #load the training corpus for the dataset\n",
    "    token_len = loadCorpus(train_file, bi_dict, tri_dict, quad_dict, vocab_dict)\n",
    "    print(\"---Processing Time for Corpus Loading: %s seconds ---\" % (time.time() - start_time))\n",
    "\n",
    "    start_time1 = time.time()\n",
    "    \n",
    "    #create the different Nc dictionaries for ngrams\n",
    "    #threshold value\n",
    "    k = 5\n",
    "    V = len(vocab_dict)\n",
    "    quad_nc_dict = findFrequencyOfFrequencyCount(quad_dict, k, 4, V, len(quad_dict))\n",
    "    tri_nc_dict = findFrequencyOfFrequencyCount(tri_dict, k, 3, V, len(tri_dict))\n",
    "    bi_nc_dict = findFrequencyOfFrequencyCount(bi_dict, k, 2, V, len(bi_dict))\n",
    "    uni_nc_dict = findFrequencyOfFrequencyCount(bi_dict, k, 1, V, len(vocab_dict))\n",
    "\n",
    "    #create quadgram probability dictionary\n",
    "    findQuadgramProbGT(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict, quad_nc_dict, k)\n",
    "    #create trigram probability dictionary\n",
    "    findTrigramProbGT(vocab_dict, bi_dict, tri_dict, tri_prob_dict, tri_nc_dict, k)\n",
    "    #create bigram probability dictionary\n",
    "    findBigramProbGT(vocab_dict, bi_dict, bi_prob_dict, bi_nc_dict, k)\n",
    "    #sort the probability dictionaries of quad,tri and bi grams\n",
    "    sortProbWordDict(bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "    #Do only when required to find the lambda value as this can take some time\n",
    "    #param = estimateParameters(token_len, vocab_dict, bi_dict, tri_dict, quad_dict)\n",
    "    #found earlier using Held out data\n",
    "    param = [0.0,0.0,0.7999999999999999,0.20000000000000007]\n",
    "    print(\"---Processing Time for Creating Probable Word Dict: %s seconds ---\" % (time.time() - start_time1))\n",
    "    \n",
    "    \n",
    "    ### TESTING WITH TEST CORPUS\n",
    "    test_data = ''\n",
    "    #Now load the test corpus\n",
    "    with open('test_corpus.txt','r') as file :\n",
    "        test_data = file.read()\n",
    "\n",
    "\n",
    "    #remove punctuations from the test data\n",
    "    test_data = removePunctuations(test_data)\n",
    "    test_token = test_data.split()\n",
    "\n",
    "    #split the test data into 4 words list\n",
    "    test_token = test_data.split()\n",
    "    test_quadgrams = list(ngrams(test_token,4))\n",
    "    \n",
    "    #choose most probable words for prediction\n",
    "    start_time2 = time.time()\n",
    "    score = computeTestScore(test_quadgrams, bi_dict, tri_dict, quad_dict, \n",
    "                             vocab_dict,token_len, param, k, quad_nc_dict, tri_nc_dict,\n",
    "                              bi_nc_dict, uni_nc_dict )\n",
    "    print('Score:',score)\n",
    "    print(\"---Processing Time for computing score: %s seconds ---\" % (time.time() - start_time2))\n",
    "\n",
    "    start_time3 = time.time()\n",
    "    perplexity = computePerplexity(test_quadgrams, bi_dict, tri_dict, quad_dict, \n",
    "                                     vocab_dict,token_len, param, k, quad_nc_dict, tri_nc_dict,\n",
    "                                      bi_nc_dict, uni_nc_dict)\n",
    "    print('Perplexity:',perplexity)\n",
    "    print(\"---Processing Time for computing Perplexity: %s seconds ---\" % (time.time() - start_time3))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>main function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def main():\n",
    "    #variable declaration\n",
    "    vocab_dict = defaultdict(int)          #for storing the different words with their frequencies    \n",
    "    bi_dict = defaultdict(int)             #for keeping count of sentences of two words\n",
    "    tri_dict = defaultdict(int)            #for keeping count of sentences of three words\n",
    "    quad_dict = defaultdict(int)           #for keeping count of sentences of four words\n",
    "    quad_prob_dict = OrderedDict()              \n",
    "    tri_prob_dict = OrderedDict()\n",
    "    bi_prob_dict = OrderedDict()\n",
    "\n",
    "    train_file = 'corpusfile.txt'\n",
    "    #load the corpus for the dataset\n",
    "    token_len = loadCorpus(train_file, bi_dict, tri_dict, quad_dict, vocab_dict)\n",
    "\n",
    "    #create the different Nc dictionaries for ngrams\n",
    "    #threshold value\n",
    "    k = 5\n",
    "    V = len(vocab_dict)\n",
    "    quad_nc_dict = findFrequencyOfFrequencyCount(quad_dict, k, 4, V, len(quad_dict))\n",
    "    tri_nc_dict = findFrequencyOfFrequencyCount(tri_dict, k, 3, V, len(tri_dict))\n",
    "    bi_nc_dict = findFrequencyOfFrequencyCount(bi_dict, k, 2, V, len(bi_dict))\n",
    "    uni_nc_dict = findFrequencyOfFrequencyCount(bi_dict, k, 1, V, len(vocab_dict))\n",
    "\n",
    "    #create quadgram probability dictionary\n",
    "    findQuadgramProbGT(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict, quad_nc_dict, k)\n",
    "    #create trigram probability dictionary\n",
    "    findTrigramProbGT(vocab_dict, bi_dict, tri_dict, tri_prob_dict, tri_nc_dict, k)\n",
    "    #create bigram probability dictionary\n",
    "    findBigramProbGT(vocab_dict, bi_dict, bi_prob_dict, bi_nc_dict, k)\n",
    "    #sort the probability dictionaries of quad,tri and bi grams\n",
    "    sortProbWordDict(bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "    #Do only when required to find the lambda value as this can take some time\n",
    "    #param = estimateParameters(token_len, vocab_dict, bi_dict, tri_dict, quad_dict)\n",
    "    #found earlier using Held out data\n",
    "    param = [0.7,0.1,0.1,0.1]\n",
    "\n",
    "    ##WORD PREDICTION \n",
    "\n",
    "    start_time2 = time.time()\n",
    "    #take user input \n",
    "    input_sen = takeInput()\n",
    "    #find the the most probable words for the bigram, trigram and unigram  sentence               \n",
    "    word_choice = chooseWords(input_sen, bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "\n",
    "\n",
    "    prediction = doInterpolatedPredictionGT(input_sen, bi_dict, tri_dict, quad_dict, \n",
    "                                 vocab_dict,token_len, word_choice, param, k, quad_nc_dict, tri_nc_dict,\n",
    "                                  bi_nc_dict, uni_nc_dict )\n",
    "    if prediction:\n",
    "        print('Word Prediction:',prediction[1])\n",
    "    print(\"---Time for Prediction Operation: %s seconds ---\" % (time.time() - start_time2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the string\n",
      "emma by jane\n",
      "Word Prediction: austen\n",
      "---Time for Prediction Operation: 7.338468313217163 seconds ---\n"
     ]
    }
   ],
   "source": [
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <i><u>For Debugging Purpose Only</u></i>\n",
    "<i>Uncomment the above two cells and ignore running the cells below if not debugging</i>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#variable declaration\n",
    "vocab_dict = defaultdict(int)          #for storing the different words with their frequencies    \n",
    "bi_dict = defaultdict(int)             #for keeping count of sentences of two words\n",
    "tri_dict = defaultdict(int)            #for keeping count of sentences of three words\n",
    "quad_dict = defaultdict(int)           #for keeping count of sentences of four words\n",
    "quad_prob_dict = OrderedDict()              \n",
    "tri_prob_dict = OrderedDict()\n",
    "bi_prob_dict = OrderedDict()\n",
    "\n",
    "print(\"---Preprocessing Time for Corpus loading: %s seconds ---\" % (time.time() - start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For Testing the Language Model\n",
    "Calculates % Accuracy and Perplexity<br>\n",
    "NOTE : If this is run then no need to run the cells following it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "train_file = 'training_corpus.txt'\n",
    "test_file = 'test_corpus.txt'\n",
    "#load the corpus for the dataset\n",
    "token_len = trainCorpus(train_file,test_file,bi_dict,tri_dict,quad_dict,vocab_dict,quad_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "train_file = 'corpusfile.txt'\n",
    "#load the corpus for the dataset\n",
    "token_len = loadCorpus(train_file, bi_dict, tri_dict, quad_dict, vocab_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create the different Nc dictionaries for ngrams\n",
    "#threshold value\n",
    "k = 5\n",
    "V = len(vocab_dict)\n",
    "quad_nc_dict = findFrequencyOfFrequencyCount(quad_dict, k, 4, V, len(quad_dict))\n",
    "tri_nc_dict = findFrequencyOfFrequencyCount(tri_dict, k, 3, V, len(tri_dict))\n",
    "bi_nc_dict = findFrequencyOfFrequencyCount(bi_dict, k, 2, V, len(bi_dict))\n",
    "uni_nc_dict = findFrequencyOfFrequencyCount(bi_dict, k, 1, V, len(vocab_dict))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create quadgram probability dictionary\n",
    "findQuadgramProbGT(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict, quad_nc_dict, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create trigram probability dictionary\n",
    "findTrigramProbGT(vocab_dict, bi_dict, tri_dict, tri_prob_dict, tri_nc_dict, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create bigram probability dictionary\n",
    "findBigramProbGT(vocab_dict, bi_dict, bi_prob_dict, bi_nc_dict, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#sort the probability dictionaries of quad,tri and bi grams\n",
    "sortProbWordDict(bi_prob_dict, tri_prob_dict, quad_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Do only when required to find the lambda value as this can take some time\n",
    "#param = estimateParameters(token_len, vocab_dict, bi_dict, tri_dict, quad_dict)\n",
    "#found earlier using Held out data\n",
    "param = [0.7,0.1,0.1,0.1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#FOR DEBUGGING ONLY\n",
    "writeProbDicts(bi_prob_dict, tri_prob_dict, quad_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "##WORD PREDICTION \n",
    "\n",
    "start_time2 = time.time()\n",
    "#take user input \n",
    "input_sen = takeInput()\n",
    "#find the the most probable words for the bigram, trigram and unigram  sentence               \n",
    "word_choice = chooseWords(input_sen, bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "\n",
    "\n",
    "prediction = doInterpolatedPredictionGT(input_sen, bi_dict, tri_dict, quad_dict, \n",
    "                             vocab_dict,token_len, word_choice, param, k, quad_nc_dict, tri_nc_dict,\n",
    "                              bi_nc_dict, uni_nc_dict )\n",
    "if prediction:\n",
    "    print('Word Prediction:',prediction[1])\n",
    "print(\"---Time for Prediction Operation: %s seconds ---\" % (time.time() - start_time2))\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}