Knesser Ney.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Word prediction using Quadgram \n",
    "### Knesser-Ney Smoothing Used with Interpolation\n",
    "### Time Complexity for word prediction only: O(1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Import corpus</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "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": 3,
   "metadata": {
    "collapsed": true
   },
   "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": null,
   "metadata": {
    "collapsed": true
   },
   "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 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": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def loadCorpus1(bi_dict,tri_dict,quad_dict,vocab_dict):\n",
    "    token_len = 0\n",
    "    #load bigrams\n",
    "    with open('w2_.txt','r',encoding='ISO-8859-1') as file:\n",
    "            #each line contains first the frequency then the sentence\n",
    "            for line in file:\n",
    "                #split the line into tokens\n",
    "                tokens = line.split()\n",
    "                #set bigram dict values\n",
    "                \n",
    "                #set value if already not present\n",
    "                if ' '.join(tokens[1:]) not in bi_dict:\n",
    "                    bi_dict[' '.join(tokens[1:])] = int(tokens[0])\n",
    "                    \n",
    "                #check if there is any new word or not\n",
    "                for word in tokens[1:]:\n",
    "                    if word not in vocab_dict:\n",
    "                        vocab_dict[word] = 1\n",
    "                    else:\n",
    "                        vocab_dict[word] += 1\n",
    "                token_len += 2\n",
    "                        \n",
    "    #load trigrams\n",
    "    with open('w3_.txt','r',encoding='ISO-8859-1') as file:\n",
    "            #each line contains first the frequency then the sentence\n",
    "            for line in file:\n",
    "                #split the line into tokens\n",
    "                tokens = line.split()\n",
    "                #set trigram dict values\n",
    "                \n",
    "                #set value if already not present\n",
    "                if ' '.join(tokens[1:]) not in tri_dict:\n",
    "                    tri_dict[' '.join(tokens[1:])] = int(tokens[0])\n",
    "                    \n",
    "                #check if there is any new word or not\n",
    "                for word in tokens[1:]:\n",
    "                    if word not in vocab_dict:\n",
    "                        vocab_dict[word] = 1\n",
    "                    else:\n",
    "                        vocab_dict[word] += 1\n",
    "                token_len += 3\n",
    "                \n",
    "    #load quadgrams\n",
    "    with open('w4_.txt','r',encoding='ISO-8859-1') as file:\n",
    "            #each line contains first the frequency then the sentence\n",
    "            for line in file:\n",
    "                #split the line into tokens\n",
    "                tokens = line.split()\n",
    "                #set quadgram dict values\n",
    "                \n",
    "                #set value if already not present\n",
    "                if ' '.join(tokens[1:]) not in quad_dict:\n",
    "                    quad_dict[' '.join(tokens[1:])] = int(tokens[0])\n",
    "                    \n",
    "                #check if there is any new word or not\n",
    "                for word in tokens[1:]:\n",
    "                    if word not in vocab_dict:\n",
    "                        vocab_dict[word] = 1\n",
    "                    else:\n",
    "                        vocab_dict[word] += 1\n",
    "                token_len += 4\n",
    "    \n",
    "    print(len(bi_dict),len(tri_dict),len(quad_dict))\n",
    "    return token_len"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Create a Hash Table for Probable words for Trigram sentences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#returns: void\n",
    "#arg: dict,dict,dict,dict,dict,int,list\n",
    "#creates dict for storing probable words with their probabilities for a trigram sentence\n",
    "def findQuadgramProb(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict):\n",
    "    print(len(vocab_dict),len(bi_dict),len(tri_dict),len(quad_dict))\n",
    "    i = 0\n",
    "    V = len(vocab_dict)\n",
    "    #NOTE: reading from a file rather than the dict itself saves around 100mb of RAM space\n",
    "    #with open('quad_dict.txt','r') as file:\n",
    "        #for quad_sen in file:\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 i smoothing has been used\n",
    "        prob = ( quad_dict[quad_sen] + 1 ) / ( tri_dict[tri_sen] + V)\n",
    "\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",
    "        #i += 1\n",
    "    print('Quad_Prb_dict len:',len(quad_prob_dict))\n",
    "    #print('i:',i)\n",
    "    prob = None\n",
    "    quad_token = None\n",
    "    tri_sen = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sort the probable words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "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",
    "   \n",
    "    for key in quad_prob_dict:\n",
    "        if len(quad_prob_dict[key])>1:\n",
    "            #only at most top 2 most probable words have been taken\n",
    "            quad_prob_dict[key] = sorted(quad_prob_dict[key],reverse = True)[:2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For writing the Quad_Dict values to a file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#returns: void\n",
    "#arg: dict\n",
    "#for writing the contents of quad_dict to a text file\n",
    "def writeQuads(bi_dict,tri_dict,quad_dict):\n",
    "    with open('quad_dict.txt','w') as file:\n",
    "        for quad in quad_dict:\n",
    "            file.write(quad+'\\n')\n",
    "    with open('tri_dict.txt','w') as file:\n",
    "        for tri in tri_dict:\n",
    "            file.write(tri+'\\n')\n",
    "    with open('bi_dict.txt','w') as file:\n",
    "        for bi in bi_dict:\n",
    "            file.write(bi+'\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#for writing prob dictionary values to file of quad,tri and bi dicts\n",
    "def writeProbDicts(bi_prob_dict, tri_prob_dict, quad_prob_dict):\n",
    "    with open('quad_prob_dict_KN.txt','w') as file:\n",
    "        for quad in quad_prob_dict:\n",
    "            file.write( quad + \": \" + str(quad_prob_dict[quad]) + '\\n\\n')\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#for creating prob dict for trigram probabilities\n",
    "def findTrigramProb(vocab_dict, bi_dict, tri_dict, tri_prob_dict):\n",
    "    print(len(vocab_dict),len(bi_dict),len(tri_dict))\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",
    "    #with open('tri_dict.txt','r') as file:\n",
    "    for tri in tri_dict:\n",
    "    #for tri in file:\n",
    "        tri_token = tri.split()\n",
    "        #bigram sentence for key\n",
    "        bi_sen = ' '.join(tri_token[:2])\n",
    "        #find the probability\n",
    "\n",
    "        #add i 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 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",
    "    print('Tri_Prb_dict len:',len(tri_prob_dict))\n",
    "    prob = None\n",
    "    tri_token = None\n",
    "    bi_sen = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#for creating prob dict for bigram probabilities\n",
    "def findBigramProb(vocab_dict, bi_dict, bi_prob_dict):\n",
    "    print(len(vocab_dict),len(bi_dict))\n",
    "    V = len(vocab_dict)\n",
    "    #create a dictionary of probable words with their probabilities for bigram probabilites\n",
    "    #with open('bi_dict.txt','r') as file:\n",
    "    for bi in bi_dict:\n",
    "    #for bi in file:\n",
    "        bi_token = bi.split()\n",
    "        #unigram for key\n",
    "        unigram = bi_token[0]\n",
    "        #find the probability\n",
    "\n",
    "        #add i 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 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",
    "    print('Bi_Prb_dict len:',len(bi_prob_dict))\n",
    "    prob = None\n",
    "    bi_token = None\n",
    "    unigram = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Driver function for doing the prediction</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#returns: string\n",
    "#arg: string,dict,int\n",
    "#does prediction for the the sentence\n",
    "def doPrediction(sen, prob_dict, rank = 1):\n",
    "    if sen in prob_dict:\n",
    "        if rank <= len(prob_dict[sen]):\n",
    "            return prob_dict[sen][rank-1][1]\n",
    "        else:\n",
    "            return prob_dict[sen][0][1]\n",
    "    else:\n",
    "        return \"Can't predict\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def doInterpolatedPrediction(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",
    "        print('quad_dict['+key+']:'+str(quad_dict[key]),'  tri_dict['+' '.join(quad_token[0:3])+']:'+str(tri_dict[' '.join(quad_token[0:3])]),\n",
    "             ' Res:',(quad_dict[key] + 1)/ (tri_dict[' '.join(quad_token[0:3])] + V))\n",
    "        #print('tri_dict['+' '.join(quad_token[0:3])+']:'+str(tri_dict[' '.join(quad_token[0:3])]))\n",
    "        print('tri_dict['+' '.join(quad_token[1:4])+']:'+str(tri_dict[' '.join(quad_token[1:4])]),'  bi_dict['+' '.join(quad_token[1:3])+']:'+str(bi_dict[' '.join(quad_token[1:3])]),\n",
    "             ' Res:',(tri_dict[' '.join(quad_token[1:4])] + 1) / (bi_dict[' '.join(quad_token[1:3])] + V))\n",
    "        #print('bi_dict['+' '.join(quad_token[1:3])+']:'+str(bi_dict[' '.join(quad_token[1:3])]))\n",
    "        print('bi_dict['+' '.join(quad_token[2:4])+']:'+ str(bi_dict[' '.join(quad_token[2:4])]),'  vocab_dict['+quad_token[2]+']:'+str(vocab_dict[quad_token[2]]),\n",
    "             ' Res:',(bi_dict[' '.join(quad_token[2:4])] + 1) / (vocab_dict[quad_token[2]] + V))\n",
    "        #print('vocab_dict['+quad_token[2]+']:'+str(vocab_dict[quad_token[2]]))\n",
    "        print('vocab_dict['+quad_token[3]+']:'+str(vocab_dict[quad_token[3]]),'  token_len:'+str(token_len),\n",
    "             ' Res:',(vocab_dict[quad_token[3]] + 1) / (token_len + V))\n",
    "        #print('token_len:'+str(token_len))\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",
    "        print(word[1],prob,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",
    "        print('\\n\\n')\n",
    "        if prob > max_prob:\n",
    "            max_prob = prob\n",
    "            pred = word\n",
    "    return pred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>For Taking input from the User</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#return:int\n",
    "#arg:list,dict,dict,dict,dict\n",
    "#computes the score for test data\n",
    "def computeTestScore(test_sent,tri_dict,quad_dict,vocab_dict,prob_dict):\n",
    "    #increment the score value if correct prediction is made else decrement its value\n",
    "    score = 0\n",
    "    w = open('test_result.txt','w')\n",
    "    for sent in test_sent:\n",
    "        sen_token = sent[:3]\n",
    "        sen = \" \".join(sen_token)\n",
    "        correct_word = sent[3]\n",
    "        #     print(sen,':',correct_word)\n",
    "\n",
    "        result = doPrediction(sen,prob_dict)\n",
    "        if result == correct_word:\n",
    "            s = sen +\" : \"+result+'\\n'\n",
    "            w.write(s)\n",
    "            score+=1\n",
    "\n",
    "    w.close()\n",
    "    return score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For Computing the Perplexity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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",
    "\n",
    "    for item in quad_dict:\n",
    "        sen_token = item.split()\n",
    "        sen = ' '.join(sen_token[0:3])\n",
    "        prob = quad_dict[item]/tri_dict[sen]\n",
    "        perplexity = perplexity * ( prob**(1./n))\n",
    "    \n",
    "    return perplexity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u> For Computing Interpolated Probability</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#returns: float\n",
    "#arg: list,list,dict,dict,dict,dict,float,float,float,float\n",
    "#for calculating the interpolated probablity\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",
    "    #with open('prob_stats.txt','w') as file:\n",
    "        #for picking the word we select the highest \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",
    "    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",
    "    #since log10(1) is zero so it doesn't add upto anything but log10(0) is undefined\n",
    "    #t = open('temp.txt','a')\n",
    "    #t.write('sen:'+sen+' quadKey:'+sen+','+str(quad_dict[sen])+'  triKey:'+' '.join(quad_token[1:4])+','+str(tri_dict[' '.join(quad_token[1:4])])+'  biKey:'+' '.join(quad_token[2:4])+','+str(bi_dict[' '.join(quad_token[2:4])])+'\\n')\n",
    "    #t.close()\n",
    "    if prob <= 0:\n",
    "        return 1\n",
    "    #print(prob)\n",
    "    return prob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#computes the knesser kney probability\n",
    "def computeKnesserNeyProb(tri_dict, quad_dict, quad_prob_dict):\n",
    "    #for knesser ney probability formula we need to find to important things \n",
    "    #first is for P(Wn|wn-1) if find no. of ngrams which ends with wn and no. of ngrams which starts \n",
    "    #with wn-1\n",
    "    #so we divide the formula into two parts ,first part can be found in constant time\n",
    "    #and second term is found here\n",
    "    i = 0\n",
    "    d = 0.75\n",
    "    #for storing count of quadgrams ending with wn\n",
    "    first_dict = {}\n",
    "    #for storing count of quadgrams having wn-1 as its starting part\n",
    "    sec_dict = {}\n",
    "    \n",
    "    for quad in quad_dict:\n",
    "        #split the quad sentence into tokens \n",
    "        quad_token = quad.split()\n",
    "        #for keeping track of count where wn finishes a quadgram\n",
    "        c1 = 0\n",
    "        #for keeping track of count where wn-1 finsishes a quadgram\n",
    "        c2 = 0\n",
    "        tri_sen = ' '.join(quad_token[:3])\n",
    "        \n",
    "        #now start looking in the quadgram dict\n",
    "        for quad1 in quad_dict:\n",
    "            quad_token1 = quad1.split()\n",
    "            if quad_token1[-1] == quad_token[-1]:\n",
    "                c1 += 1\n",
    "            if ' '.join(quad_token1[:3]) == tri_sen:\n",
    "                c2 += 1\n",
    "        \n",
    "        ############################################\n",
    "        #########################################3\n",
    "# #!!!!!!!#COMMENT THIS FOR DIFFERENT CORPUS R.THIS IS REQUIRED FOR THIS CORPUS ONLY\n",
    "        print(tri_sen,tri_dict[tri_sen])\n",
    "        if tri_dict[tri_sen] == 0:\n",
    "            tri_dict[tri_sen] = 1\n",
    "        #########################################\n",
    "        \n",
    "        prob = ( max(quad_dict[quad]-d,0) / tri_dict[tri_sen] ) + ( (c1/len(quad_dict)) * (d*c2/tri_dict[tri_sen]) ) \n",
    "        \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]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#computes the knesser kney probability\n",
    "def computeKnesserNeyProb1(tri_dict, quad_dict, quad_prob_dict):\n",
    "    #for knesser ney probability formula we need to find to important things \n",
    "    #first is for P(Wn|wn-1) if find no. of ngrams which ends with wn and no. of ngrams which starts \n",
    "    #with wn-1\n",
    "    #so we divide the formula into two parts ,first part can be found in constant time\n",
    "    #and second term is found here\n",
    "    i = 0\n",
    "    d = 0.75\n",
    "    #for storing count of quadgrams ending with wn,key:unigram\n",
    "    first_dict = {}\n",
    "    #for storing count of quadgrams having wn-1 as its starting part, key: trigram sentence\n",
    "    sec_dict = {}\n",
    "    \n",
    "    for quad in quad_dict:\n",
    "        #split the quad sentence into tokens \n",
    "        quad_token = quad.split()\n",
    "        \n",
    "        tri_sen = ' '.join(quad_token[:3])\n",
    "        \n",
    "        #tri_sen is the word that has stars in sec_dict[tri_sen] number of times in quad_dict \n",
    "        if tri_sen not in sec_dict:\n",
    "            sec_dict[ tri_sen ] = 1\n",
    "        else:\n",
    "            sec_dict[ tri_sen ] += 1\n",
    "            \n",
    "        if quad_token[-1] not in first_dict:\n",
    "            first_dict[ quad_token[-1] ] = 1\n",
    "        else:\n",
    "            first_dict[ quad_token[-1] ] += 1\n",
    "   \"\"\"\"\"\"         \n",
    "    for quad in quad_dict:\n",
    "        quad_token = quad.split()\n",
    "        tri_sen = ' '.join(quad_token[:3])\n",
    "        ############################################\n",
    "        #########################################3\n",
    "        # #!!!!!!!#COMMENT THIS FOR DIFFERENT CORPUS R.THIS IS REQUIRED FOR THIS CORPUS ONLY\n",
    "        if tri_dict[tri_sen] == 0:\n",
    "            tri_dict[tri_sen] = 1\n",
    "        #########################################\n",
    "    \n",
    "        prob = ( \n",
    "                ( max(quad_dict[quad]-d,0) / tri_dict[tri_sen] ) + \n",
    "                ( ( first_dict[quad_token[-1]]/len(quad_dict)) * (d*sec_dict[tri_sen]/tri_dict[tri_sen]) ) \n",
    "               )\n",
    "        #add the word to probability dictionary\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",
    "    \"\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>Driver Function for Testing the Language Model</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\n    test_data = \\'\\'\\n    #Now load the test corpus\\n    with open(\\'testing_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    #print(len(test_token))\\n    start_time1 = time.time()\\n    score = computeTestScore(test_quadgrams,tri_dict,quad_dict,vocab_dict,prob_dict)\\n    print(\\'Score:\\',score)\\n    print(\"---Processing Time for computing score: %s seconds ---\" % (time.time() - start_time1))\\n\\n    start_time2 = 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_time2))\\n\\n    test_result += \\'TEST RESULTS\\nScore: \\'+str(score) + \\'\\nPerplexity: \\'+str(perplexity)\\n    with open(\\'test_results.txt\\',\\'w\\') as file:\\n      \\tfile.write(test_result)\\n'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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 = loadCorpus1(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",
    "    #for writing the quad_dict to a file\n",
    "    #writeQuads(bi_dict,tri_dict,quad_dict)\n",
    "    \n",
    "    #param = estimateParameters(token_len, vocab_dict, bi_dict, tri_dict, quad_dict)\n",
    "    #print(param)\n",
    "    \n",
    "    #found using estimateParameters(..) fucntion\n",
    "    #param = [0,0.1,0,0.9]\n",
    "    \n",
    "    #creates a dictionary of probable words \n",
    "    #findQuadgramProb(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict)\n",
    "    \n",
    "    #sort the dictionary of probable words \n",
    "    #sortProbWordDict(prob_dict)\n",
    "    \n",
    "    gc.collect()\n",
    "    print(\"---Processing Time for Creating Probable Word Dict: %s seconds ---\" % (time.time() - start_time1))\n",
    "    return token_len\n",
    "\"\"\"\n",
    "    test_data = ''\n",
    "    #Now load the test corpus\n",
    "    with open('testing_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",
    "    #print(len(test_token))\n",
    "    start_time1 = time.time()\n",
    "    score = computeTestScore(test_quadgrams,tri_dict,quad_dict,vocab_dict,prob_dict)\n",
    "    print('Score:',score)\n",
    "    print(\"---Processing Time for computing score: %s seconds ---\" % (time.time() - start_time1))\n",
    "\n",
    "    start_time2 = 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_time2))\n",
    "\n",
    "    test_result += 'TEST RESULTS\\nScore: '+str(score) + '\\nPerplexity: '+str(perplexity)\n",
    "    with open('test_results.txt','w') as file:\n",
    "      \tfile.write(test_result)\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <u>main function</u>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "def main():\n",
    "\n",
    "    #variable declaration\n",
    "    tri_dict = defaultdict(int)            #for keeping count of sentences of three words\n",
    "    quad_dict = defaultdict(int)           #for keeping count of sentences of three words\n",
    "    vocab_dict = defaultdict(int)          #for storing the different words with their frequencies    \n",
    "    prob_dict = OrderedDict()              #for storing the probabilities of probable words for a sentence\n",
    "    bi_dict = defaultdict(int)\n",
    "\n",
    "    #load the corpus for the dataset\n",
    "    loadCorpus('corpusfile.txt',tri_dict,quad_dict,vocab_dict)\n",
    "    print(\"---Preprocessing Time for Corpus loading: %s seconds ---\" % (time.time() - start_time))\n",
    "\n",
    "    start_time1 = time.time()\n",
    "    #for writing the quad_dict to a file\n",
    "    writeQuads(quad_dict)\n",
    "    #creates a dictionary of probable words \n",
    "    createProbableWordDict(tri_dict,quad_dict,prob_dict)\n",
    "    #sort the dictionary of probable words \n",
    "    sortProbWordDict(prob_dict)\n",
    "\n",
    "    gc.collect()\n",
    "    print(\"---Preprocessing Time for Creating Probable Word Dict: %s seconds ---\" % (time.time() - start_time1))\n",
    "\n",
    "    input_sen = takeInput()\n",
    "\n",
    "    start_time2 = time.time()\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",
    "\"\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "if __name__ == '__main__':\n",
    "    main()\n",
    "\"\"\""
   ]
  },
  {
   "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": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---Preprocessing Time for Corpus loading: 60.84304690361023 seconds ---\n"
     ]
    }
   ],
   "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",
    "#load the corpus for the dataset\n",
    "#loadCorpus('corpusfile.txt',bi_dict,tri_dict,quad_dict,vocab_dict)\n",
    "print(\"---Preprocessing Time for Corpus loading: %s seconds ---\" % (time.time() - start_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1020385 1020009 1034307\n",
      "---Processing Time for Corpus Loading: 74.39337587356567 seconds ---\n",
      "---Processing Time for Creating Probable Word Dict: 0.059902191162109375 seconds ---\n"
     ]
    }
   ],
   "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)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "computeKnesserNeyProb1(tri_dict, quad_dict, quad_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "findBigramProb(vocab_dict, bi_dict, bi_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "findQuadgramProb(vocab_dict, bi_dict, tri_dict, quad_dict, quad_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "sortProbWordDict(bi_prob_dict, tri_prob_dict, quad_prob_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "writeProbDicts(bi_prob_dict, tri_prob_dict, quad_prob_dict)\n",
    "gc.collect()"
   ]
  }
 ],
 "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
}