Word_Prediction_Add-1_Smoothing_with_Interpolation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <u>Word prediction</u> \n",
    "### Language Model based on n-gram Probabilistic Model\n",
    "### Add-1 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": {},
   "outputs": [],
   "source": [
    "#returns: string\n",
    "#arg: string\n",
    "#remove punctuations, change to lowercase ,retain the apostrophe mark\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 done 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": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "#returns : void\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 declaration 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": {},
   "outputs": [],
   "source": [
    "#creates dict for storing probable words with their probabilities for a trigram sentence\n",
    "# ADD 1 Smoothing used\n",
    "\n",
    "#returns: void\n",
    "#arg: dict,dict,dict,dict,dict\n",
    "def findQuadgramProbAdd1(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict):\n",
    "    i = 0\n",
    "    V = len(vocab_dict)\n",
    "    \n",
    "    #using the fourth word of the quadgram sentence as the probable word and calculate its\n",
    "    #probability,here ADD 1 smoothing has been used during the probability calculation\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",
    "        #add 1 smoothing has been used\n",
    "        prob = ( quad_dict[quad_sen] + 1 ) / ( tri_dict[tri_sen] + V)\n",
    "        \n",
    "        #if the trigram sentence is not present in the Dictionary then add it\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",
    "        #the trigram sentence is present but the probable word is missing,then add it\n",
    "        else:\n",
    "            quad_prob_dict[tri_sen].append([prob,quad_token[-1]])\n",
    "        \n",
    "   \n",
    "    prob = None\n",
    "    quad_token = None\n",
    "    tri_sen = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For creating Probability Dictionary for Trigram Probabilities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#for creating prob dict for trigram probabilities\n",
    "#creates dict for storing probable words with their probabilities for a trigram sentence\n",
    "# ADD 1 Smoothing used\n",
    "\n",
    "#returns: void\n",
    "#arg: dict,dict,dict,dict\n",
    "def findTrigramProbAdd1(vocab_dict, bi_dict, tri_dict, tri_prob_dict):\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",
    "        #add 1 smoothing has been used\n",
    "        prob = ( tri_dict[tri] + 1 ) / ( bi_dict[bi_sen] + V)\n",
    "\n",
    "        #tri_prob_dict is a dict of list\n",
    "        #if the bigram sentence is not present in the Dictionary then add it\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",
    "        #the bigram sentence is present but the probable word is missing,then add it\n",
    "        else:\n",
    "            tri_prob_dict[bi_sen].append([prob,tri_token[-1]])\n",
    "            \n",
    "  \n",
    "    prob = None\n",
    "    tri_token = None\n",
    "    bi_sen = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For creating Probability Dictionary for Bigram Probabilities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#for creating prob dict for bigram probabilities\n",
    "#creates dict for storing probable words with their probabilities for a trigram sentence\n",
    "# ADD 1 Smoothing used\n",
    "\n",
    "#returns: void\n",
    "#arg: dict,dict,dict,dict\n",
    "def findBigramProbAdd1(vocab_dict, bi_dict, bi_prob_dict):\n",
    "    \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",
    "        #add 1 smoothing has been used\n",
    "        prob = ( bi_dict[bi] + 1 ) / ( vocab_dict[unigram] + V)\n",
    "\n",
    "        #bi_prob_dict is a dict of list\n",
    "        #if the unigram sentence is not present in the Dictionary then add it\n",
    "        if unigram not in bi_prob_dict:\n",
    "            bi_prob_dict[unigram] = []\n",
    "            bi_prob_dict[unigram].append([prob,bi_token[-1]])\n",
    "        #the unigram sentence is present but the probable word is missing,then add it\n",
    "        else:\n",
    "            bi_prob_dict[unigram].append([prob,bi_token[-1]])\n",
    "    \n",
    "   \n",
    "    prob = None\n",
    "    bi_token = None\n",
    "    unigram = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Parameter estimation for Interpolation </u>\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": 7,
   "metadata": {},
   "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": [
    "## <u> For Computing Interpolated Probability</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#returns: float\n",
    "#arg: list,list,dict,dict,dict,dict,float,float,float,float\n",
    "#for calculating the interpolated probablity given the Trigram sentence and the given word\n",
    "def interpolatedProbability(quad_token,token_len, vocab_dict, bi_dict, tri_dict, quad_dict, qc, tc, bc,\n",
    "                            l1 = 0.25, l2 = 0.25, l3 = 0.25 , l4 = 0.25):\n",
    "    V = len(vocab_dict)\n",
    "    \n",
    "    sen = ' '.join(quad_token)\n",
    "    prob = (   \n",
    "              l1*((quad_dict[sen] + 1)/ (tri_dict[' '.join(quad_token[0:3])] + V)) \n",
    "            + l2*((tri_dict[' '.join(quad_token[1:4])] + 1) / (bi_dict[' '.join(quad_token[1:3])] + V)) \n",
    "            + l3*((bi_dict[' '.join(quad_token[2:4])] + 1) / (vocab_dict[quad_token[2]] + V)) \n",
    "            + l4*((vocab_dict[quad_token[3]] + 1) / (token_len + V))\n",
    "           )\n",
    "    \n",
    "    if sen  in quad_dict:\n",
    "        qc[0] += 1\n",
    "    if ' '.join(quad_token[1:4]) in tri_dict:\n",
    "        tc[0] += 1\n",
    "    if ' '.join(quad_token[2:4])  in bi_dict:\n",
    "        bc[0] += 1    \n",
    "        \n",
    "    #since log10(1) is zero so it doesn't add upto anything but log10(0) is undefined\n",
    "    if prob <= 0:\n",
    "        return 1\n",
    "    \n",
    "    return prob"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sort the probable words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#for sorting the probable word acc. to their probabilities\n",
    "\n",
    "#returns: void\n",
    "#arg: dict, dict, dict\n",
    "def sortProbWordDict(bi_prob_dict, tri_prob_dict, quad_prob_dict):\n",
    "    #sort bigram 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",
    "    #sort trigram dict\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",
    "    #sort quadgram dict\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>Word Prediction related Driver functions</u>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For choosing prediction word candidates for Word Prediction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "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": [
    "### Finds the Predicted Word using Interpolation with Add -1 Smoothing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#does prediction for the the sentence using Interpolation\n",
    "#Uses Add-1 Smoothing\n",
    "#returns: string\n",
    "#arg: string,dict,dict,dict,dict,int,list,list\n",
    "def doInterpolatedPredictionAdd1(sen, bi_dict, tri_dict, quad_dict, \n",
    "                             vocab_dict,token_len, word_choice, param):\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",
    "        prob = (   \n",
    "                  param[0]*((quad_dict[key] + 1)/ (tri_dict[' '.join(quad_token[0:3])] + V)) \n",
    "                + param[1]*((tri_dict[' '.join(quad_token[1:4])] + 1) / (bi_dict[' '.join(quad_token[1:3])] + V)) \n",
    "                + param[2]*((bi_dict[' '.join(quad_token[2:4])] + 1) / (vocab_dict[quad_token[2]] + V)) \n",
    "                + param[3]*((vocab_dict[quad_token[3]] + 1) / (token_len + V))\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[1]\n",
    "    else:\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>For Taking input from the User</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "#for taking input from user\n",
    "\n",
    "#returns: string\n",
    "#arg: void\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": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "#computes the score for test data i,e no. of right predictions against no. of wrong predictions\n",
    "\n",
    "#return:int\n",
    "#arg:list,dict,dict,dict,dict\n",
    "def computeTestScore(test_token,bi_dict, tri_dict, quad_dict, vocab_dict,\n",
    "                     bi_prob_dict, tri_prob_dict, quad_prob_dict, token_len,param):\n",
    "    \n",
    "    \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/add1_smoothing_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",
    "            #select probable word candidates for prediction\n",
    "            word_choice = chooseWords(sen, bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "            result = doInterpolatedPredictionAdd1(sen, bi_dict, tri_dict, quad_dict, vocab_dict,token_len, word_choice, param)\n",
    "            \n",
    "            if result == correct_word:\n",
    "                score+=1\n",
    "            else:\n",
    "                wrong += 1\n",
    "            \n",
    "            total += 1\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": 14,
   "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,token_len,tri_dict,quad_dict,vocab_dict,prob_dict):\n",
    "    \n",
    "    perplexity = float(1.0)\n",
    "    n = token_len\n",
    "    V = len(vocab_dict)\n",
    "    for item in quad_dict:\n",
    "        sen_token = item.split()\n",
    "        tri_sen = ' '.join(sen_token[0:3])\n",
    "        prob = (quad_dict[item] + 1) / (tri_dict[tri_sen] + V)\n",
    "        perplexity = perplexity * ( prob**(1./n))\n",
    "    with open('Test_Scores/add1_smoothing_score.txt','w') as w:\n",
    "        w.write('\\nPerplexity: '+str(perplexity))\n",
    "    return perplexity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Driver Function for Testing the Language Model</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "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",
    "    score = 0\n",
    "    \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",
    "    #estimate the lambdas for interpolation\n",
    "    #found earlier usign estimate Function\n",
    "    param = [0.7,0.1,0.1,0.1]\n",
    "    #param = estimateParameters(token_len, vocab_dict, bi_dict, tri_dict, quad_dict)\n",
    "    #print(param)\n",
    "    \n",
    "    #create trigram Probability Dictionary\n",
    "    findTrigramProbAdd1(vocab_dict, bi_dict, tri_dict, tri_prob_dict)\n",
    "    #create bigram Probability Dictionary\n",
    "    findBigramProbAdd1(vocab_dict, bi_dict, bi_prob_dict)\n",
    "    #create quadgram Probability Dictionary\n",
    "    findQuadgramProbAdd1(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict)\n",
    "    #sort the probability dictionaries\n",
    "    sortProbWordDict(bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "    gc.collect()\n",
    "    print(\"---Preprocessing 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",
    "    #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, vocab_dict,\n",
    "                     bi_prob_dict, tri_prob_dict, quad_prob_dict, token_len,param)\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_token,token_len,tri_dict,quad_dict,vocab_dict,prob_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</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def main():\n",
    "\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 = defaultdict(list)         #for storing the probable  words for Quadgram sentences     \n",
    "    tri_prob_dict = defaultdict(list)          #for storing the probable  words for Trigram sentences     \n",
    "    bi_prob_dict = defaultdict(list)           #for storing the probable  words for Bigram sentences\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",
    "    #estimate the lambdas for interpolation\n",
    "    #param = estimateParameters(token_len, vocab_dict, bi_dict, tri_dict, quad_dict)\n",
    "    param = [0.7,0.1,0.1,0.1]\n",
    "    \n",
    "    #create bigram Probability Dictionary\n",
    "    findBigramProbAdd1(vocab_dict, bi_dict, bi_prob_dict)\n",
    "    #create trigram Probability Dictionary\n",
    "    findTrigramProbAdd1(vocab_dict, bi_dict, tri_dict, tri_prob_dict)\n",
    "    #create quadgram Probability Dictionary\n",
    "    findQuadgramProbAdd1(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict)\n",
    "    #sort the probability dictionaries\n",
    "    sortProbWordDict(bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "\n",
    "    #take user input \n",
    "    input_sen = takeInput()\n",
    "\n",
    "\n",
    "    ### PREDICTION\n",
    "    #choose most probable words for prediction\n",
    "    word_choice = chooseWords(input_sen, bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "    prediction = doInterpolatedPredictionAdd1(input_sen, bi_dict, tri_dict, quad_dict, vocab_dict,token_len, word_choice, param)\n",
    "    print('Word Prediction:',prediction)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the string\n",
      "today the\n",
      "Please enter atleast 3 words !\n",
      "Enter the string\n",
      "today the mood\n",
      "Word Prediction: \n"
     ]
    }
   ],
   "source": [
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <i><u>For Debugging Purpose Only</u></i>\n",
    "<i>Ignore running the cells below if not debugging</i>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "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 = defaultdict(list)         #for storing the probable  words for Quadgram sentences     \n",
    "tri_prob_dict = defaultdict(list)          #for storing the probable  words for Trigram sentences     \n",
    "bi_prob_dict = defaultdict(list)           #for storing the probable  words for Bigram sentences     "
   ]
  },
  {
   "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": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\SEEKER\\Anaconda3\\envs\\tensorflow\\lib\\site-packages\\ipykernel_launcher.py:63: DeprecationWarning: generator 'ngrams' raised StopIteration\n",
      "C:\\Users\\SEEKER\\Anaconda3\\envs\\tensorflow\\lib\\site-packages\\ipykernel_launcher.py:77: DeprecationWarning: generator 'ngrams' raised StopIteration\n"
     ]
    }
   ],
   "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": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "#estimate the lambdas for interpolation\n",
    "#param = estimateParameters(token_len, vocab_dict, bi_dict, tri_dict, quad_dict)\n",
    "param = [0.8,0.2,0.0,0.0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create bigram Probability Dictionary\n",
    "findBigramProbAdd1(vocab_dict, bi_dict, bi_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create trigram Probability Dictionary\n",
    "findTrigramProbAdd1(vocab_dict, bi_dict, tri_dict, tri_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#create quadgram Probability Dictionary\n",
    "findQuadgramProbAdd1(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#sort the probability dictionaries\n",
    "sortProbWordDict(bi_prob_dict, tri_prob_dict, quad_prob_dict)"
   ]
  },
  {
   "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": [
    "#take user input \n",
    "input_sen = takeInput()\n",
    "\n",
    "\n",
    "### PREDICTION\n",
    "start_time2 = time.time()\n",
    "#choose most probable words for prediction\n",
    "word_choice = chooseWords(input_sen, bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "prediction = doInterpolatedPredictionAdd1(input_sen, bi_dict, tri_dict, quad_dict, vocab_dict,token_len, word_choice, param)\n",
    "#prediction = doPrediction(input_sen,prob_dict)\n",
    "print('Word Prediction:',prediction)\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
}