Assignment_2_18QE30008.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Assignment_2_18QE30008.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "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.10"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "zyJ25uz0kSaw"
      },
      "source": [
        "# Assignment 2 on Natural Language Processing\n",
        "\n",
        "### Date : 15th Sept, 2020\n",
        "\n",
        "### Instructor : Prof. Sudeshna Sarkar\n",
        "\n",
        "### Teaching Assistants : Alapan Kuila, Aniruddha Roy, Anusha Potnuru, Uppada Vishnu"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Ao1nhg9RknmF"
      },
      "source": [
        "The central idea of this assignment is to make you familiar with programming in python and also the language modelling task of natural language processing using the python.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "stk58juYkzEr"
      },
      "source": [
        "**Dataset:** \n",
        "\n",
        " Use the text file provided along."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pRQfVQSjlmU0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "!pip install --upgrade --force-reinstall nltk 1> /dev/null"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8kpmaKdaum4h",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 101
        },
        "outputId": "8d513ea3-582c-491e-db64-e21a48d5981a"
      },
      "source": [
        "import re\n",
        "import string\n",
        "import nltk\n",
        "from nltk.tokenize import word_tokenize,sent_tokenize\n",
        "from nltk.lm.preprocessing import padded_everygram_pipeline\n",
        "from nltk.lm.preprocessing import pad_both_ends\n",
        "from nltk.lm.preprocessing import flatten\n",
        "from nltk.lm import MLE\n",
        "from nltk.util import ngrams\n",
        "from nltk.corpus import stopwords\n",
        "nltk.download('punkt')\n",
        "nltk.download('stopwords')"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[nltk_data] Downloading package punkt to /root/nltk_data...\n",
            "[nltk_data]   Package punkt is already up-to-date!\n",
            "[nltk_data] Downloading package stopwords to /root/nltk_data...\n",
            "[nltk_data]   Package stopwords is already up-to-date!\n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "rT6byv49kdmo",
        "colab": {}
      },
      "source": [
        "# read dataset\n",
        "\n",
        "file = open(\"corpus.txt\", \"r\")\n",
        "corpus = file.read()\n",
        "# print(corpus)"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "SRGqKaDn1pJy"
      },
      "source": [
        "Preprocess the data"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EtT_VaZaFpGC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# print(sentences)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "C1OtHn6B1oc2",
        "colab": {}
      },
      "source": [
        "sentences = sent_tokenize(corpus)       # tokenize sentences\n",
        "tokenized_text = []\n",
        "remove = []                     \n",
        "\n",
        "for i, sentence in enumerate(sentences):\n",
        "    sentence = sentence.lower().replace('_', '')    # convert to lowercase\n",
        "    sentences[i] = re.sub(r'[^\\w\\s]', '', sentence)     # remove punctuation\n",
        "    if sentences[i][:7] == 'chapter':          # remove all \"chapter X\" sentences from the corpus, as they aren't a part of the actual text\n",
        "        remove.append(i)\n",
        "\n",
        "for index in sorted(remove, reverse=True):\n",
        "    del sentences[index]        \n",
        "\n",
        "for sentence in sentences:\n",
        "    tokenized_text.append(word_tokenize(sentence))\n",
        "\n",
        "# print(tokenized_text)"
      ],
      "execution_count": 61,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "YDL7yfpXkMRS"
      },
      "source": [
        "### Task: In this sub-task, you are expected to carry out the following tasks:\n",
        "\n",
        "1. **Create the following language models** on the training corpus: <br>\n",
        "    i.   Unigram <br>\n",
        "    ii.  Bigram <br>\n",
        "    iii. Trigram <br>\n",
        "    iv.  Fourgram <br>\n",
        "\n",
        "2. **List the top 5 bigrams, trigrams, four-grams (with and without Add-1 smoothing).**\n",
        "(Note: Please remove those which contain only articles, prepositions, determiners. For Example: “of the”, “in a”, etc)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aBVvRQmK6MvZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "ngrams_all = {1: [], 2: [], 3: [], 4: []}       # will store all ngrams (uni, bi, tri, four) without stopword removal\n",
        "for i in range(4):\n",
        "    for sentence in tokenized_text:\n",
        "        for j in ngrams(sentence, i + 1):\n",
        "            ngrams_all[i + 1].append(j);\n",
        "\n",
        "# print(ngrams_all[1])\n",
        "# print(ngrams_all[2])\n",
        "# print(ngrams_all[3])\n",
        "# print(ngrams_all[4])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wbKBndIn9_TX",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 138
        },
        "outputId": "8b3754d2-4ad8-4c24-a301-1ecd8016eacb"
      },
      "source": [
        "print(\"Top 10 ngrams without stopword removal, without smoothing, with their respective counts:\\n\")\n",
        "fdist = nltk.FreqDist(ngrams_all[1])\n",
        "print(\"Unigrams: \" + str(fdist.most_common(10)))        # gets the 10 most common unigrams\n",
        "fdist = nltk.FreqDist(ngrams_all[2])\n",
        "print(\"Bigrams: \" + str(fdist.most_common(10)))         # 10 most common bigrams, and so on\n",
        "fdist = nltk.FreqDist(ngrams_all[3])                    \n",
        "print(\"Trigrams: \" + str(fdist.most_common(10)))\n",
        "fdist = nltk.FreqDist(ngrams_all[4])\n",
        "print(\"Fourgrams: \" + str(fdist.most_common(10)))"
      ],
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Top 10 ngrams without stopword removal, without smoothing, with their respective counts:\n",
            "\n",
            "Unigrams: [(('the',), 1627), (('and',), 842), (('to',), 721), (('a',), 625), (('she',), 537), (('it',), 526), (('of',), 507), (('said',), 462), (('i',), 399), (('alice',), 384)]\n",
            "Bigrams: [(('said', 'the'), 209), (('of', 'the'), 130), (('said', 'alice'), 115), (('in', 'a'), 96), (('and', 'the'), 80), (('in', 'the'), 78), (('it', 'was'), 74), (('to', 'the'), 69), (('the', 'queen'), 65), (('as', 'she'), 61)]\n",
            "Trigrams: [(('the', 'mock', 'turtle'), 51), (('the', 'march', 'hare'), 30), (('said', 'the', 'king'), 29), (('the', 'white', 'rabbit'), 21), (('said', 'the', 'hatter'), 21), (('said', 'to', 'herself'), 19), (('said', 'the', 'mock'), 19), (('said', 'the', 'caterpillar'), 18), (('she', 'went', 'on'), 17), (('she', 'said', 'to'), 17)]\n",
            "Fourgrams: [(('said', 'the', 'mock', 'turtle'), 19), (('she', 'said', 'to', 'herself'), 16), (('a', 'minute', 'or', 'two'), 11), (('said', 'the', 'march', 'hare'), 8), (('will', 'you', 'wont', 'you'), 8), (('said', 'alice', 'in', 'a'), 7), (('as', 'well', 'as', 'she'), 6), (('well', 'as', 'she', 'could'), 6), (('in', 'a', 'great', 'hurry'), 6), (('in', 'a', 'tone', 'of'), 6)]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-J7eH8lV1wOk",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Removing ngrams which contain all stopword elements\n",
        "\n",
        "ngrams_all_withoutStop = ngrams_all\n",
        "\n",
        "stopws = stopwords.words('english')     # gets and stores stopwords in the stopws variable\n",
        "\n",
        "for i in range(4):              # remove ngrams which contain only stopwords\n",
        "    for j, ngram in enumerate(ngrams_all_withoutStop[i + 1]):\n",
        "        word_l = len(ngram)\n",
        "        k = 0\n",
        "        for word in ngram:\n",
        "            if word in stopws:\n",
        "                k += 1\n",
        "        if k == word_l:\n",
        "            del (ngrams_all_withoutStop[i + 1])[j]"
      ],
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VzU2bJ6zE8b5",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 138
        },
        "outputId": "a9f406cc-cd38-4dc9-e2fd-25b7801e6a08"
      },
      "source": [
        "print(\"Top 10 ngrams with stopword removal, without smoothing, with their respective counts:\\n\")\n",
        "fdist = nltk.FreqDist(ngrams_all_withoutStop[1])\n",
        "print(\"Unigrams: \" + str(fdist.most_common(10)))\n",
        "fdist = nltk.FreqDist(ngrams_all_withoutStop[2])\n",
        "print(\"Bigrams: \" + str(fdist.most_common(10)))\n",
        "fdist = nltk.FreqDist(ngrams_all_withoutStop[3])\n",
        "print(\"Trigrams: \" + str(fdist.most_common(10)))\n",
        "fdist = nltk.FreqDist(ngrams_all_withoutStop[4])\n",
        "print(\"Fourgrams: \" + str(fdist.most_common(10)))"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Top 10 ngrams with stopword removal, without smoothing, with their respective counts:\n",
            "\n",
            "Unigrams: [(('said',), 462), (('alice',), 384), (('little',), 128), (('one',), 101), (('like',), 85), (('know',), 85), (('would',), 83), (('went',), 83), (('could',), 77), (('thought',), 74)]\n",
            "Bigrams: [(('said', 'the'), 209), (('said', 'alice'), 115), (('the', 'queen'), 65), (('the', 'king'), 60), (('a', 'little'), 59), (('mock', 'turtle'), 54), (('the', 'mock'), 53), (('the', 'gryphon'), 53), (('the', 'hatter'), 51), (('went', 'on'), 48)]\n",
            "Trigrams: [(('the', 'mock', 'turtle'), 51), (('the', 'march', 'hare'), 30), (('said', 'the', 'king'), 29), (('the', 'white', 'rabbit'), 21), (('said', 'the', 'hatter'), 21), (('said', 'to', 'herself'), 19), (('said', 'the', 'mock'), 19), (('said', 'the', 'caterpillar'), 18), (('she', 'went', 'on'), 17), (('she', 'said', 'to'), 17)]\n",
            "Fourgrams: [(('said', 'the', 'mock', 'turtle'), 19), (('she', 'said', 'to', 'herself'), 16), (('a', 'minute', 'or', 'two'), 11), (('said', 'the', 'march', 'hare'), 8), (('will', 'you', 'wont', 'you'), 8), (('said', 'alice', 'in', 'a'), 7), (('as', 'well', 'as', 'she'), 6), (('well', 'as', 'she', 'could'), 6), (('in', 'a', 'great', 'hurry'), 6), (('in', 'a', 'tone', 'of'), 6)]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "ioc1xNjmnim-"
      },
      "source": [
        "# Applying Smoothing\n",
        "\n",
        "\n",
        "Assume additional training data in which each possible N-gram occurs exactly once and adjust estimates.\n",
        "\n",
        "> ### $ Probability(ngram) = \\frac{Count(ngram)+1}{ N\\, +\\, V} $\n",
        "\n",
        "N: Total number of N-grams <br>\n",
        "V: Number of unique N-grams\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "grh4sO0Yns4V",
        "colab": {}
      },
      "source": [
        "# You are to perform Add-1 smoothing here:\n",
        "# write similar code for bigram, trigram and fourgrams\n",
        "\n",
        "ngrams_vocab = {1: set([]), 2: set([]), 3: set([]), 4: set([])}       # will hold unique ngrams -> 1: unigrams, 2: bigrams, 3: trigrams, 4: fourgrams\n",
        "\n",
        "for i in range(4):\n",
        "    for gram in ngrams_all[i + 1]:\n",
        "        if gram not in ngrams_vocab[i + 1]:\n",
        "            ngrams_vocab[i + 1].add(gram)\n",
        "            "
      ],
      "execution_count": 42,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BDRLjnzVQMSA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "total_ngrams = {1: -1, 2: -1, 3: -1, 4: -1}     # keeps count of total ngrams for all- uni, bi, tri, four grams\n",
        "total_vocab = {1: -1, 2: -1, 3: -1, 4: -1}      # keeps count of unique ngrams for all- uni, bi, tri, four grams\n",
        "for i in range(4):\n",
        "    total_ngrams[i + 1] = len(ngrams_all[i + 1])\n",
        "    total_vocab[i + 1] = len(ngrams_vocab[i + 1])"
      ],
      "execution_count": 43,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3Vi_L9n-MN02",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "ngrams_all_prob = {1: [], 2: [], 3: [], 4: []}      # will hold all types of ngrams, in descending order of probability, after smoothing\n",
        "\n",
        "for i in range(4):\n",
        "    for ngram in ngrams_vocab[i + 1]:\n",
        "        tmplist = [ngram]\n",
        "        tmplist.append( (ngrams_all[i + 1]).count(ngram) )\n",
        "        (ngrams_all_prob[i + 1]).append(tmplist)\n"
      ],
      "execution_count": 44,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cHZLHBDGPS0C",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "for i in range(4):              # applies smoothing- stores probability values using smoothing for all ngrams\n",
        "    for ngram in ngrams_all_prob[i + 1]:\n",
        "        ngram[-1] = (ngram[-1] + 1) / (total_ngrams[i + 1] + total_vocab[i + 1])"
      ],
      "execution_count": 45,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "O1nVZlZqWTDq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def Sort(sub_li):       # returns a list of ngrams sorted by their probability values after applying smoothing\n",
        "    return(sorted(sub_li, key = lambda x: x[1], reverse = True)) "
      ],
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fHzstFoVSG2j",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "for i in range(4):      # sorting according to probability values after smoothing\n",
        "    ngrams_all_prob[i + 1] = Sort(ngrams_all_prob[i + 1])"
      ],
      "execution_count": 47,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GKFj3shJUT01",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 138
        },
        "outputId": "17e35b87-7381-45c5-c0d8-9567115c4843"
      },
      "source": [
        "print(\"Top 10 ngrams without stopword removal, with smoothing, with their corresponding smoothing probability scores:\\n\")\n",
        "print(\"Unigrams: \" + str(ngrams_all_prob[1][:10]))\n",
        "print(\"Bigrams: \" + str(ngrams_all_prob[2][:10]))\n",
        "print(\"Trigrams: \" + str(ngrams_all_prob[3][:10]))\n",
        "print(\"Fourgrams: \" + str(ngrams_all_prob[4][:10]))"
      ],
      "execution_count": 50,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Top 10 ngrams without stopword removal, with smoothing, with their corresponding smoothing probability scores:\n",
            "\n",
            "Unigrams: [[('the',), 0.05599697313658721], [('and',), 0.028995975647508], [('to',), 0.024834038454923813], [('a',), 0.021532005640972723], [('she',), 0.018505142228184227], [('it',), 0.018126784301585663], [('of',), 0.01747325697382451], [('said',), 0.015925429092284938], [('i',), 0.013758470058129536], [('alice',), 0.01324252743094968]]\n",
            "Bigrams: [[('said', 'the'), 0.0053475935828877], [('of', 'the'), 0.0033358798064680416], [('said', 'alice'), 0.0029539088362617776], [('in', 'a'), 0.0024700789406671758], [('and', 'the'), 0.0020626432391138276], [('in', 'the'), 0.0020117137764196586], [('it', 'was'), 0.0019098548510313217], [('to', 'the'), 0.0017825311942959], [('the', 'queen'), 0.0016806722689075631], [('as', 'she'), 0.001578813343519226]]\n",
            "Trigrams: [[('the', 'mock', 'turtle'), 0.001143988560114399], [('the', 'march', 'hare'), 0.0006819931800681993], [('said', 'the', 'king'), 0.0006599934000659993], [('said', 'the', 'hatter'), 0.00048399516004839953], [('the', 'white', 'rabbit'), 0.00048399516004839953], [('said', 'to', 'herself'), 0.00043999560004399956], [('said', 'the', 'mock'), 0.00043999560004399956], [('said', 'the', 'caterpillar'), 0.0004179958200417996], [('she', 'said', 'to'), 0.0003959960400395996], [('said', 'the', 'gryphon'), 0.0003959960400395996]]\n",
            "Fourgrams: [[('said', 'the', 'mock', 'turtle'), 0.00043469755917320525], [('she', 'said', 'to', 'herself'), 0.00036949292529722444], [('a', 'minute', 'or', 'two'), 0.00026081853550392317], [('said', 'the', 'march', 'hare'), 0.00019561390162794236], [('will', 'you', 'wont', 'you'), 0.00019561390162794236], [('said', 'alice', 'in', 'a'), 0.0001738790236692821], [('you', 'wont', 'you', 'will'), 0.00015214414571062184], [('the', 'moral', 'of', 'that'), 0.00015214414571062184], [('as', 'well', 'as', 'she'), 0.00015214414571062184], [('in', 'a', 'tone', 'of'), 0.00015214414571062184]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "k0GL40mQmmt4"
      },
      "source": [
        "### Predict the next word using statistical language modelling\n",
        "\n",
        "Using the above bigram, trigram, and fourgram models that you just experimented with, **predict the next word(top 5 probable) given the previous n(=2, 3, 4)-grams** for the sentences below.\n",
        "\n",
        "For str1, str2, you are to predict the next  2 possible word sequences using your trained smoothed models. <br> \n",
        "For example, for the string 'He looked very' the answers can be as below: \n",
        ">     (1) 'He looked very' *anxiouxly* \n",
        ">     (2) 'He looked very' *uncomfortable* "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "MBWKo5_Fmnbg",
        "colab": {}
      },
      "source": [
        "str1 = 'after that alice said the'\n",
        "str2 = 'alice felt so desperate that she was'"
      ],
      "execution_count": 52,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IrHxZLqjGMvl",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        },
        "outputId": "42e982d0-c9e2-4b53-ad8e-f4f40ac2d967"
      },
      "source": [
        "tokens1 = word_tokenize(str1)   # word tokenize both strings\n",
        "tokens2 = word_tokenize(str2)\n",
        "\n",
        "ngrams1 = {1: [], 2: [], 3: []}     # will hold ngrams formed at the end of str1\n",
        "ngrams2 = {1: [], 2: [], 3: []}     # ^^ for str2\n",
        "for i in range(3):\n",
        "    ngrams1[i + 1] = list(ngrams(tokens1, i + 1))[-1]\n",
        "    ngrams2[i + 1] = list(ngrams(tokens2, i + 1))[-1]\n",
        "\n",
        "print(ngrams1, ngrams2, sep = '\\n')"
      ],
      "execution_count": 54,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{1: ('the',), 2: ('said', 'the'), 3: ('alice', 'said', 'the')}\n",
            "{1: ('was',), 2: ('she', 'was'), 3: ('that', 'she', 'was')}\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ck0HUWNO67ib",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "predictions1 = {1: [], 2: [], 3: []}    # will hold top 5 next-word predictions using the bigram, trigram and fourgram models for str1\n",
        "for i in range(3):                      # finds the first 5 bigrams, trigrams, and fourgrams in the sorted list of ngrams (in decreasing order of probability)\n",
        "    count = 0\n",
        "    for pred in ngrams_all_prob[i + 2]:\n",
        "        if pred[0][:-1] == ngrams1[i + 1]:\n",
        "            count += 1\n",
        "            (predictions1[i + 1]).append(pred[0][-1])\n",
        "            if count == 5:\n",
        "                break\n",
        "    if count < 5:                       # if 5 ngrams not found, fill up the remaining elements with NULL\n",
        "        while(count != 5):\n",
        "            (predictions1[i + 1]).append(\"NULL\")\n",
        "            count += 1"
      ],
      "execution_count": 56,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0jV__1g-Az3V",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "predictions2 = {1: [], 2: [], 3: []}    # will hold top 5 predictions for the next word using the bigram, trigram and fourgram models for str2\n",
        "for i in range(3):                      # finds the first 5 bigrams, trigrams, and fourgrams in the sorted list of ngrams (in decreasing order of probability)\n",
        "    count = 0\n",
        "    for pred in ngrams_all_prob[i + 2]:\n",
        "        if pred[0][:-1] == ngrams2[i + 1]:\n",
        "            count += 1\n",
        "            (predictions2[i + 1]).append(pred[0][-1])\n",
        "            if count == 5:\n",
        "                break\n",
        "    if count < 5:                        # if 5 ngrams not found, fill up the remaining elements with NULL\n",
        "        while(count != 5):\n",
        "            (predictions1[i + 1]).append(\"NULL\")\n",
        "            count += 1"
      ],
      "execution_count": 57,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "L3zsT4gJGM3S",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 202
        },
        "outputId": "c960d30c-b539-4139-f6b4-c4996719f5ca"
      },
      "source": [
        "print(\"Next-word predictions for the given strings using the bigram, trigram and fourgram models respectively, in decreasing order of probability are:\\n\")\n",
        "print(\"For string 1- \\\"after that alice said the\\\"\\nBigram: {}\\nTrigram: {}\\nFourgram: {}\".format(predictions1[1], predictions1[2], predictions1[3]))\n",
        "print(\"\\nFor string 2- \\\"alice felt so desperate that she was\\\"\\nBigram: {}\\nTrigram: {}\\nFourgram: {}\".format(predictions2[1], predictions2[2], predictions2[3]))"
      ],
      "execution_count": 60,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Next-word predictions for the given strings using the bigram, trigram and fourgram models respectively, in decreasing order of probability are:\n",
            "\n",
            "For string 1- \"after that alice said the\"\n",
            "Bigram: ['queen', 'king', 'mock', 'gryphon', 'hatter']\n",
            "Trigram: ['king', 'hatter', 'mock', 'caterpillar', 'gryphon']\n",
            "Fourgram: ['NULL', 'NULL', 'NULL', 'NULL', 'NULL']\n",
            "\n",
            "For string 2- \"alice felt so desperate that she was\"\n",
            "Bigram: ['a', 'the', 'not', 'that', 'going']\n",
            "Trigram: ['now', 'quite', 'a', 'looking', 'walking']\n",
            "Fourgram: ['now', 'in', 'quite', 'dozing', 'losing']\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}