Ngrams Model.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1423,
     "status": "ok",
     "timestamp": 1729436454987,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "WFoElMGbzrRj",
    "outputId": "ef713572-db61-4278-f33c-14b0911ec689"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Drive already mounted at /content/drive; to attempt to forcibly remount, call drive.mount(\"/content/drive\", force_remount=True).\n",
      "/content/drive/My Drive/CSC583\n"
     ]
    }
   ],
   "source": [
    "#Mount my Google Drive.\n",
    "#from google.colab import drive\n",
    "#drive.mount(\"/content/drive\")\n",
    "#import os\n",
    "#directory = '/content/drive/My Drive/CSC583'\n",
    "#os.chdir(directory)\n",
    "\n",
    "#Ensure the files are there (in the folder).\n",
    "#!pwd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "pDXA4ZTK0uv-"
   },
   "source": [
    "### **Some Important Import's**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "executionInfo": {
     "elapsed": 1728,
     "status": "ok",
     "timestamp": 1729436456711,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "rjJkX_WE0vKI"
   },
   "outputs": [],
   "source": [
    "#Token dictionary.\n",
    "import pandas as pd\n",
    "from collections import defaultdict\n",
    "\n",
    "#N-gram models.\n",
    "import nltk\n",
    "from nltk.probability import ConditionalFreqDist, FreqDist\n",
    "from nltk.util import ngrams\n",
    "\n",
    "#Perplexity.\n",
    "import math\n",
    "import itertools\n",
    "#Sentence generation.\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "59Ae44oCJRRb"
   },
   "source": [
    "#**Part I: N-gram Modeling and Perplexity**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Is2wcrIe04Hf"
   },
   "source": [
    "## **Load Datasets**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F9Pkugxc12CA"
   },
   "source": [
    "**Get both files:**\n",
    "\n",
    "urlTrain = \"https://condor.depaul.edu/ntomuro/courses/583/2024fall/assign/HW4/ngram/1b_benchmark.train.tokens\"\n",
    "\n",
    "file_nameTrain = \"1b_benchmark_train_tokens.txt\"  \n",
    "response = requests.get(urlTrain)\n",
    "\n",
    "with open(file_nameTrain, 'w', encoding='utf-8') as file:\n",
    "    file.write(response.text)\n",
    "print(f\"File saved as {file_nameTrain}\")\n",
    "\n",
    "urlTest = \"https://condor.depaul.edu/ntomuro/courses/583/2024fall/assign/HW4/ngram/1b_benchmark.test.tokens\"\n",
    "\n",
    "file_nameTest = \"1b_benchmark_test_tokens.txt\"  \n",
    "response = requests.get(urlTest)\n",
    "\n",
    "with open(file_nameTest, 'w', encoding='utf-8') as file:\n",
    "    file.write(response.text)\n",
    "print(f\"File saved as {file_nameTest}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "1hctu_Oxf6An"
   },
   "source": [
    "## **Pre-step: Build the Vocabulary**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "executionInfo": {
     "elapsed": 6,
     "status": "ok",
     "timestamp": 1729436456712,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "NkxhLbgo0xkt"
   },
   "outputs": [],
   "source": [
    "def loadData(fileName):\n",
    "  '''Reading the data from a text file, each line/sentence is an observation.'''\n",
    "  with open(fileName, 'r', encoding='utf-8') as inFile:\n",
    "    content = inFile.readlines()\n",
    "  data = pd.DataFrame(content, columns=['sentence'])\n",
    "  print(f'Number of (rows, columns): {data.shape}')\n",
    "  return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 98
    },
    "executionInfo": {
     "elapsed": 286,
     "status": "ok",
     "timestamp": 1729436456993,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "iijaw3fr1BSD",
    "outputId": "75de9a29-cdfa-43b6-9aaa-7187356f9b58"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of (rows, columns): (61530, 1)\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sentence</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Having a little flexibility on that issue woul...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                            sentence\n",
       "0  Having a little flexibility on that issue woul..."
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trainData = loadData(\"1b_benchmark_train_tokens.txt\")\n",
    "trainData.head(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "executionInfo": {
     "elapsed": 6,
     "status": "ok",
     "timestamp": 1729436456993,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "0TegeouXP0R3"
   },
   "outputs": [],
   "source": [
    "def vocabDict(data):\n",
    "  '''Generate vocab dictionary of the data. Take input as a pandas dataframe.\n",
    "  Note: Tokens that occurred (strictly) < 3 times into a special symbol '<unk>'.\n",
    "        Add a symbol '<STOP>' to finalize the vocabulary.'''\n",
    "\n",
    "  vocabDict = defaultdict(int)\n",
    "  #Tokenize each sentence and count the token occurrences.\n",
    "  for sentence in data['sentence']:\n",
    "    tokens = sentence.split()\n",
    "    #Vocabulary only with <STOP>.\n",
    "    for token in tokens:\n",
    "      vocabDict[token] += 1\n",
    "    vocabDict['<STOP>'] += 1\n",
    "\n",
    "  #Replace tokens with less than 3 occurrences with <unk>.\n",
    "  final_vocabDict = {token: count for token, count in vocabDict.items() if count >= 3}\n",
    "  final_vocabDict['<unk>'] = sum(count for count in vocabDict.values() if count < 3)\n",
    "\n",
    "  return final_vocabDict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 750,
     "status": "ok",
     "timestamp": 1729436457738,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "lR7QrZe6klqk",
    "outputId": "4e48aff5-ecdd-44f0-c752-d3c7f39499ef"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of unique tokens - without '<START>': 26602\n",
      "----First five tokens----\n",
      "Having: 47\n",
      "a: 31455\n",
      "little: 463\n",
      "flexibility: 16\n",
      "on: 11543\n"
     ]
    }
   ],
   "source": [
    "vocabDict_train = vocabDict(trainData)\n",
    "print(f\"Number of unique tokens - without '<START>': {len(vocabDict_train)}\")\n",
    "print('----First five tokens----')\n",
    "for token, count in list(vocabDict_train.items())[:5]:\n",
    "    print(f\"{token}: {count}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "SenAt23smBij"
   },
   "source": [
    "## **Create N-gram models -- using NLTK**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "24FQ73OCnVxC"
   },
   "source": [
    "*   From a line in the training data, create a list of tokens by first splitting tokens by white spaces, then converting tokens to those in the vocabulary.\n",
    "*   Pass the list of tokens to the NLTK's library function nltk.ngrams(list_of_tokens, n) to obtain ngrams for a given n (2 for bigram and 3 for trigram). The function returns a list of all ngrams made the list of tokens."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1729436457738,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "0G-a2wXqlqpj"
   },
   "outputs": [],
   "source": [
    "def gen_ngramsList(data, vocabDict):\n",
    "  '''Obtain ngrams list for a given n. Create columns in pandas data frame.\n",
    "  Return: List of all ngrams.'''\n",
    "  unigramList = []\n",
    "  bigramList = []\n",
    "  trigramList = []\n",
    "\n",
    "  for sentence in data['sentence']:\n",
    "    tokens = sentence.split()\n",
    "    #Tokenize a sentence. If words don't exist in vocabDict, treat as <unk>.\n",
    "    tokens = [token if token in vocabDict else '<unk>' for token in tokens]\n",
    "\n",
    "    #Unigrams | No <START> token.\n",
    "    unigrams = list(nltk.ngrams(tokens + ['<STOP>'], 1))\n",
    "    unigramList.append(unigrams)\n",
    "\n",
    "    #Bigrams | One <START> token.\n",
    "    bigrams = list(nltk.ngrams(['<START>'] + tokens + ['<STOP>'], 2))\n",
    "    bigramList.append(bigrams)\n",
    "\n",
    "    #Trigrams | Two <START> tokens.\n",
    "    trigrams = list(nltk.ngrams(['<START>', '<START>'] + tokens + ['<STOP>'], 3))\n",
    "    trigramList.append(trigrams)\n",
    "\n",
    "  data['unigrams'] = unigramList\n",
    "  data['bigrams'] = bigramList\n",
    "  data['trigrams'] = trigramList\n",
    "\n",
    "  return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 81
    },
    "executionInfo": {
     "elapsed": 3822,
     "status": "ok",
     "timestamp": 1729436461557,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "kTnOh2h2sUGI",
    "outputId": "53cc0fe0-e53d-4e97-c4a5-80a1c79a0887"
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sentence</th>\n",
       "      <th>unigrams</th>\n",
       "      <th>bigrams</th>\n",
       "      <th>trigrams</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Having a little flexibility on that issue woul...</td>\n",
       "      <td>[(Having,), (a,), (little,), (flexibility,), (...</td>\n",
       "      <td>[(&lt;START&gt;, Having), (Having, a), (a, little), ...</td>\n",
       "      <td>[(&lt;START&gt;, &lt;START&gt;, Having), (&lt;START&gt;, Having,...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                            sentence  \\\n",
       "0  Having a little flexibility on that issue woul...   \n",
       "\n",
       "                                            unigrams  \\\n",
       "0  [(Having,), (a,), (little,), (flexibility,), (...   \n",
       "\n",
       "                                             bigrams  \\\n",
       "0  [(<START>, Having), (Having, a), (a, little), ...   \n",
       "\n",
       "                                            trigrams  \n",
       "0  [(<START>, <START>, Having), (<START>, Having,...  "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trainData = gen_ngramsList(trainData, vocabDict_train)\n",
    "trainData.head(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Gz6hlDWcvhcx"
   },
   "source": [
    "### **Applicable for bigram and trigram only --> Creates a conditional frequency distribution**\n",
    "*   For each n (bigram/trigram), pass the list of ngrams to the nltk.ConditionalFreqDist(list_of_ngrams) function. This function receives a list of 2-tuples/pairs, and returns a nested dictionary where keys are the first element of the pairs and the values are the frequency distribution dictionary (nltk.FreqDist() dictionary) of the second element of the pairs.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1729436461557,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "mgdWL6Ezvg_R"
   },
   "outputs": [],
   "source": [
    "def gen_ConditionalFreqDist(data, columnName):\n",
    "  '''Generate conditional frequency distribution for the entire corpus\n",
    "  based on the n-1 leading words within a tuple.'''\n",
    "\n",
    "  freqDist = ConditionalFreqDist()\n",
    "  for ngrams in data[columnName]:\n",
    "    for ngram in ngrams:\n",
    "      #Key: All tokens except for last one -- within a tuple.\n",
    "      firstElement = ngram[:-1]\n",
    "      #Last token -- within a tuple.\n",
    "      secondElement = ngram[-1]\n",
    "      freqDist[firstElement][secondElement] += 1\n",
    "\n",
    "  return freqDist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 2723,
     "status": "ok",
     "timestamp": 1729436464277,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "KHQrx3vtsmGW",
    "outputId": "4e1bfb2c-b89b-4d23-b542-dabc23c61dc6"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bigram ('Clinton', 'leading') frequency: 1\n"
     ]
    }
   ],
   "source": [
    "bigram_freqDist = gen_ConditionalFreqDist(trainData, 'bigrams')\n",
    "print(\"Bigram ('Clinton', 'leading') frequency:\", bigram_freqDist[('Clinton',)]['leading'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 6085,
     "status": "ok",
     "timestamp": 1729436470359,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "tu7WO_9SrHbR",
    "outputId": "72d84895-509d-409d-cb2f-6b2026b1e59b"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trigram ('I', 'believe', 'he') frequency: 1\n"
     ]
    }
   ],
   "source": [
    "trigram_freqDist = gen_ConditionalFreqDist(trainData, 'trigrams')\n",
    "print(\"Trigram ('I', 'believe', 'he') frequency:\", trigram_freqDist[('I', 'believe')]['he'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "lFmNAqK419gG"
   },
   "source": [
    "### **Finally, creating Ngram language models.**\n",
    "*   Simply Ngram probability models. Simply access the ConditonalFreqDist (for each n (bigram/trigram) by calling freq() in NLTK."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "CqlZJzzOCCwa"
   },
   "source": [
    "### **Unigram models.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1126,
     "status": "ok",
     "timestamp": 1729436471480,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "JHPCou737Zhs",
    "outputId": "7f9d2e79-f186-4bf8-e114-72031cc1f2cc"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total number of token post manipulation: 1622907\n",
      "'Reihana' occcurs 3 times.\n"
     ]
    }
   ],
   "source": [
    "#Let's look at total number of tokens, which will be the denominator.\n",
    "#NOT using RAW token count.\n",
    "#Use count after vocabulary manipulation which including tokens <UNK>, <STOP>.\n",
    "\n",
    "#Also, spot check word count.\n",
    "denominator  = []\n",
    "word = 'Reihana'\n",
    "count = 0\n",
    "for sent in trainData['sentence']:\n",
    "  tokens = sent.split()\n",
    "  tokens = [token if token in vocabDict_train else '<unk>' for token in tokens]\n",
    "  for t in tokens:\n",
    "    if t == word:\n",
    "      count += 1\n",
    "  unigrams = list(nltk.ngrams(tokens + ['<STOP>'], 1))\n",
    "  denominator.extend(unigrams)\n",
    "print(f'Total number of token post manipulation: {len(denominator)}')\n",
    "print(f\"'{word}' occcurs {count} times.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "executionInfo": {
     "elapsed": 3,
     "status": "ok",
     "timestamp": 1729436471480,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "714n9JpM6ad9"
   },
   "outputs": [],
   "source": [
    "def unigram(data):\n",
    "  '''Calculate unigram probabilities for non-smoothing and Laplace smoothing.\n",
    "  Return: Two dictionaries.'''\n",
    "  unigramModel = FreqDist()\n",
    "\n",
    "  #Using unigram column.\n",
    "  for unigrams in data['unigrams']:\n",
    "    #Iterate through each token, get count.\n",
    "    for unigram in unigrams:\n",
    "      unigramModel[unigram[0]] += 1\n",
    "\n",
    "  #Total token count, include repetitons.\n",
    "  tokenCount = unigramModel.N()\n",
    "  unigramProb = {word: unigramModel[word] / tokenCount for word in unigramModel}\n",
    "\n",
    "  #Laplace smoothing.\n",
    "  vocabSize = len(unigramModel)\n",
    "  laplace_unigramProb = {word: (unigramModel[word] + 1) / (tokenCount + vocabSize) for word in unigramModel}\n",
    "  return unigramProb, laplace_unigramProb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 2609,
     "status": "ok",
     "timestamp": 1729436474086,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "5BHLyct068aR",
    "outputId": "afb5072a-cc8a-4044-a532-52353a651f53"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unigram probability | non-smoothing for 'Reihana': 1.8485347589233394e-06\n",
      "Unigram probability | Laplace smoothing for 'Reihana': 2.4249640347521596e-06\n"
     ]
    }
   ],
   "source": [
    "unigramProb, laplace_unigramProb = unigram(trainData)\n",
    "#Since 'Reihana' occurs 3 times in the train corpus --> Let's deemed as a rare word.\n",
    "#Laplace smoothing basically boosts occurrences of rare/unseen words.\n",
    "#Hence resulting higher probability for 'Reihana'.\n",
    "print(\"Unigram probability | non-smoothing for 'Reihana':\", unigramProb.get('Reihana', 0))\n",
    "print(\"Unigram probability | Laplace smoothing for 'Reihana':\", laplace_unigramProb.get('Reihana', 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1856,
     "status": "ok",
     "timestamp": 1729436475940,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "vA4-xh3RIk_g",
    "outputId": "01c80f8f-b103-48c5-c6ba-5c03a42c56de"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.8485347589233394e-06\n"
     ]
    }
   ],
   "source": [
    "#-----Let's test my code with sample Ngrams -- Example Scratch code.-----\n",
    "sentences = [[token if token in vocabDict_train else '<unk>' for token in s.split()] for s in trainData['sentence']]\n",
    "for sent in sentences:\n",
    "    sent.append('<STOP>')\n",
    "\n",
    "def flatten(sents):\n",
    "  '''Un-nest master list.'''\n",
    "  return [token for sent in sents for token in sent]\n",
    "newlist = flatten(sentences)\n",
    "\n",
    "#Unigram.\n",
    "fdist1 = nltk.probability.FreqDist(newlist)\n",
    "print(fdist1.freq('Reihana'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "H1gmtSRRCE9n"
   },
   "source": [
    "### **Bigram models.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "executionInfo": {
     "elapsed": 5,
     "status": "ok",
     "timestamp": 1729436475941,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "3b9gAIRd4fGY"
   },
   "outputs": [],
   "source": [
    "def bigram(bigram_freqDist, vocabDict, sentenceCount):\n",
    "  '''Calculate bigram probabilities for non-smoothing and Laplace smoothing.\n",
    "  Return: Two dictionaries.\n",
    "  Note: Only calculate Laplace smoothing probability for existing/seen bigrams.'''\n",
    "\n",
    "  bigramProb = {}\n",
    "  laplace_bigramProb = {}\n",
    "  vocabSize = len(vocabDict)\n",
    "\n",
    "  #Iterate through each word with respect to first element.\n",
    "  for firstEle in bigram_freqDist:\n",
    "    #Since '<START>' does not exist in vocab dictionary.\n",
    "    #If '<START>' found, its count = Number of sentences in train data.\n",
    "    #Otherwiuse, get count of the first word (context). If cannot be found, treat as 0.\n",
    "    first_wordCount = sentenceCount if firstEle[0] == '<START>' else vocabDict.get(firstEle[0], 0)\n",
    "\n",
    "    for word in bigram_freqDist[firstEle]:\n",
    "      #Non-smoothed.\n",
    "      prob = bigram_freqDist[firstEle].freq(word)\n",
    "      bigramProb[(firstEle[0], word)] = prob\n",
    "\n",
    "      #Laplace smoothing.\n",
    "      bigramCount = bigram_freqDist[firstEle][word]\n",
    "      laplaceProb = (bigramCount + 1) / (first_wordCount + vocabSize)\n",
    "      laplace_bigramProb[(firstEle[0], word)] = laplaceProb\n",
    "\n",
    "  return bigramProb, laplace_bigramProb\n",
    "\n",
    "def unseenBigram(firstW, secondW, laplace_bigramProb, vocabDict, sentenceCount):\n",
    "  '''Calculate on the fly unseen bigram probabilities for Laplace smoothing.'''\n",
    "\n",
    "  vocabSize=len(vocabDict)\n",
    "  first_wordCount = sentenceCount if firstW == '<START>' else vocabDict.get(firstW, 0)\n",
    "  laplaceProb = 1 / (first_wordCount + vocabSize)\n",
    "\n",
    "  return laplaceProb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1757,
     "status": "ok",
     "timestamp": 1729436477694,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "gIXHlLdeITCF",
    "outputId": "db312df9-6ce2-406e-f6ec-ccb55d704db6"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bigram probability | non-smoothing for ('a', 'little'): 0.005245588936576061\n",
      "Bigram probability | Laplace smoothing for ('a', 'little'): 0.002859259004082195\n"
     ]
    }
   ],
   "source": [
    "bigramProb, laplace_bigramProb = bigram(bigram_freqDist, vocabDict_train, trainData.shape[0])\n",
    "print(\"Bigram probability | non-smoothing for ('a', 'little'):\", bigramProb.get(('a', 'little'), 0))\n",
    "print(\"Bigram probability | Laplace smoothing for ('a', 'little'):\", laplace_bigramProb.get(('a', 'little'), 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 4118,
     "status": "ok",
     "timestamp": 1729436481809,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "IP9M5sbrIqbn",
    "outputId": "cfedd7a3-b212-4c04-bebd-17376ba0df8d"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.005245588936576061\n"
     ]
    }
   ],
   "source": [
    "#Let's test my code with sample Ngrams -- Example Scratch code.\n",
    "sentences = [[token if token in vocabDict_train else '<unk>' for token in s.split()] for s in trainData['sentence']]\n",
    "for sent in sentences:\n",
    "    sent.append('<STOP>')\n",
    "bigram_list = [list(ngrams(sentence, 2, pad_left=True, left_pad_symbol='<START>')) for sentence in sentences]\n",
    "cfd = nltk.ConditionalFreqDist(flatten(bigram_list))\n",
    "print (cfd['a'].freq('little'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "7Kigb3zeSjAW"
   },
   "source": [
    "### **Trigram models.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1729436481810,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "3TqDndmTluI9"
   },
   "outputs": [],
   "source": [
    "def trigram(trigram_freqDist, bigram_freqDist, vocabDict, sentenceCount):\n",
    "  '''Calculate trigram probabilities for non-smoothing and Laplace smoothing.\n",
    "  Return: Two dictionaries - non-smoothed trigram probabilities and Laplace-smoothed trigram probabilities.'''\n",
    "\n",
    "  trigramProb = {}\n",
    "  laplace_trigramProb = {}\n",
    "  vocabSize = len(vocabDict)\n",
    "\n",
    "  for first_twoWords in trigram_freqDist:\n",
    "    #Since ('<START>','<START>') does not exist in bigram conditional frequency.\n",
    "    if first_twoWords == ('<START>','<START>'):\n",
    "      #Its count = Number of sentences in train data.\n",
    "      first_two_wordCount = sentenceCount\n",
    "    else:\n",
    "      #Count of the first two words (context). If cannot retrieve, treat as 0.\n",
    "      first_two_wordCount = bigram_freqDist.get((first_twoWords[0],), {}).get(first_twoWords[1], 0)\n",
    "\n",
    "    for thirdW in trigram_freqDist[first_twoWords]:\n",
    "      #Non-smoothed.\n",
    "      prob = trigram_freqDist[first_twoWords].freq(thirdW)\n",
    "      trigramProb[(first_twoWords[0], first_twoWords[1], thirdW)] = prob\n",
    "\n",
    "      #Laplace smoothing.\n",
    "      trigramCount = trigram_freqDist[first_twoWords][thirdW]\n",
    "      laplaceProb = (trigramCount + 1) / (first_two_wordCount + vocabSize)\n",
    "      laplace_trigramProb[(first_twoWords[0], first_twoWords[1], thirdW)] = laplaceProb\n",
    "\n",
    "  return trigramProb, laplace_trigramProb\n",
    "\n",
    "def unseenTrigram(firstW, secondW, thirdW, laplace_trigramProb, bigram_freqDist, vocabDict, sentenceCount):\n",
    "  '''Calculate on the fly unseen bigram probabilities for Laplace smoothing.'''\n",
    "\n",
    "  vocabSize = len(vocabDict)\n",
    "  if firstW == '<START>' and secondW == '<START>':\n",
    "    first_two_wordCount = sentenceCount\n",
    "  else:\n",
    "    first_two_wordCount = bigram_freqDist.get((firstW,), {}).get(secondW, 0)\n",
    "  laplaceProb = 1 / (first_two_wordCount + vocabSize)\n",
    "\n",
    "  return laplaceProb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 5202,
     "status": "ok",
     "timestamp": 1729436487008,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "DKf9cheHTaeT",
    "outputId": "59722596-a874-4d44-c5f7-ee3912ff4662"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trigram probability | non-smoothing for ('a', 'union', 'leader'): 0.16666666666666666\n",
      "Trigram probability | Laplace smoothing for ('a', 'union', 'leader'): 7.51653638003608e-05\n"
     ]
    }
   ],
   "source": [
    "trigramProb, laplace_trigramProb = trigram(trigram_freqDist, bigram_freqDist, vocabDict_train, trainData.shape[0])\n",
    "print(\"Trigram probability | non-smoothing for ('a', 'union', 'leader'):\", trigramProb.get(('a', 'union', 'leader'), 0))\n",
    "print(\"Trigram probability | Laplace smoothing for ('a', 'union', 'leader'):\", laplace_trigramProb.get(('a', 'union', 'leader'), 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 8634,
     "status": "ok",
     "timestamp": 1729436495639,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "v_8KVkfXQJ4H",
    "outputId": "8510765c-b71c-49c6-b48e-8907a69e83f3"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.16666666666666666\n"
     ]
    }
   ],
   "source": [
    "#Let's test my code with sample Ngrams -- Example Scratch code.\n",
    "sentences = [[token if token in vocabDict_train else '<unk>' for token in s.split()] for s in trainData['sentence']]\n",
    "for sent in sentences:\n",
    "    sent.append('<STOP>')\n",
    "trigram_list = [list(ngrams(sentence, 3, pad_left=True, left_pad_symbol='<START>')) for sentence in sentences]\n",
    "trigrams = flatten(trigram_list)\n",
    "tupled3 = [(tri[:-1], tri[-1]) for tri in trigrams]\n",
    "cfd3 = nltk.ConditionalFreqDist(tupled3)\n",
    "print (cfd3[('a', 'union')].freq('leader'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "NeV9d-OtVK6l"
   },
   "source": [
    "## **Load Test Data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 115
    },
    "executionInfo": {
     "elapsed": 815,
     "status": "ok",
     "timestamp": 1729436496451,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "ENbjAsGfZ0ZA",
    "outputId": "6a5a0422-5fae-4f77-eca7-398005e74cf5"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of (rows, columns): (12105, 1)\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sentence</th>\n",
       "      <th>unigrams</th>\n",
       "      <th>bigrams</th>\n",
       "      <th>trigrams</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>BAGHDAD -- An Iraqi military commander on Mond...</td>\n",
       "      <td>[(BAGHDAD,), (--,), (An,), (Iraqi,), (military...</td>\n",
       "      <td>[(&lt;START&gt;, BAGHDAD), (BAGHDAD, --), (--, An), ...</td>\n",
       "      <td>[(&lt;START&gt;, &lt;START&gt;, BAGHDAD), (&lt;START&gt;, BAGHDA...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                            sentence  \\\n",
       "0  BAGHDAD -- An Iraqi military commander on Mond...   \n",
       "\n",
       "                                            unigrams  \\\n",
       "0  [(BAGHDAD,), (--,), (An,), (Iraqi,), (military...   \n",
       "\n",
       "                                             bigrams  \\\n",
       "0  [(<START>, BAGHDAD), (BAGHDAD, --), (--, An), ...   \n",
       "\n",
       "                                            trigrams  \n",
       "0  [(<START>, <START>, BAGHDAD), (<START>, BAGHDA...  "
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "testData = loadData(\"1b_benchmark_test_tokens.txt\")\n",
    "testData = gen_ngramsList(testData, vocabDict_train)\n",
    "testData.head(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "RwsKIsufCFbt"
   },
   "source": [
    "## **Implement two versions of the perplexity function.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "q2sJoMkvCPkm"
   },
   "source": [
    "### **(1) Without any smoothing technique**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ko41AKPMTCJ5"
   },
   "source": [
    "### **Unigram Perplexity - Non-smoothing**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "executionInfo": {
     "elapsed": 5,
     "status": "ok",
     "timestamp": 1729436496451,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "94AJnMquesDx"
   },
   "outputs": [],
   "source": [
    "def unigramPerplexity(data, unigramProb):\n",
    "  '''Calculate perplexity for the unigram model on sentence level.'''\n",
    "\n",
    "  #Store perplexity score of each sentence.\n",
    "  sentence_perplexityList = []\n",
    "  for index, row in data.iterrows():\n",
    "    #Unigrams from the 'unigrams' column.\n",
    "    unigrams = row['unigrams']\n",
    "\n",
    "    #Accumulator for sum(log(prob)).\n",
    "    sum_logProb = 0\n",
    "    #Total number of tokens/ngrams per sentence.\n",
    "    n = 0\n",
    "\n",
    "    for unigram in unigrams:\n",
    "      #Extract context word.\n",
    "      word = unigram[0]\n",
    "      #Retrieve the probability of the token/ngram from the unigramProb dictionary.\n",
    "      prob = unigramProb.get(word)\n",
    "      #Take natural log then add to sum_logProb accumulator.\n",
    "      sum_logProb += math.log(prob)\n",
    "      #Count ngrams within the sentence.\n",
    "      n += 1\n",
    "\n",
    "    #Average negative log-likelihood for the sentence aka. multiply with (-1/n).\n",
    "    sentenceLikelihood = -sum_logProb / n\n",
    "    #Inverse multiplication in logarithmic space.\n",
    "    sentencePerplexity = math.exp(sentenceLikelihood)\n",
    "    sentence_perplexityList.append(sentencePerplexity)\n",
    "\n",
    "  #Average of the entire test corpus.\n",
    "  overallPerplexity = sum(sentence_perplexityList) / len(sentence_perplexityList)\n",
    "\n",
    "  return overallPerplexity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 4036,
     "status": "ok",
     "timestamp": 1729436500483,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "OkCQ4nPOogr1",
    "outputId": "8c3cb8ff-25d9-4fba-d638-be2e94987ba3"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train corpus Unigram Perplexity - without smoothing: 1080.3611555581683\n"
     ]
    }
   ],
   "source": [
    "unigramPerplexity_nonSmoothing_train = unigramPerplexity(trainData, unigramProb)\n",
    "print(f\"Train corpus Unigram Perplexity - without smoothing: {unigramPerplexity_nonSmoothing_train}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1286,
     "status": "ok",
     "timestamp": 1729436501766,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "F_N1cxLW2Auc",
    "outputId": "7906b60a-999e-420b-ea8b-df9d5eb40d3e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test corpus Unigram Perplexity - without smoothing: 998.7255840250589\n"
     ]
    }
   ],
   "source": [
    "unigramPerplexity_nonSmoothing_test = unigramPerplexity(testData, unigramProb)\n",
    "print(f\"Test corpus Unigram Perplexity - without smoothing: {unigramPerplexity_nonSmoothing_test}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "UHEhFBnlTJyC"
   },
   "source": [
    "### **Bigram Perplexity - Non-smoothing**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1729436501767,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "mnS5ltrtSYoM"
   },
   "outputs": [],
   "source": [
    "def bigramPerplexity(data, bigramProb, sentenceCount = None, vocabDict = None):\n",
    "  '''Calculate perplexity for the bigram model on sentence level.\n",
    "  Note: If vocabDict is provided, apply Laplace smoothing to calculate unseen bigrams probability.'''\n",
    "\n",
    "  #Store perplexity score of each sentence.\n",
    "  sentence_perplexityList = []\n",
    "\n",
    "  for index, row in data.iterrows():\n",
    "    #Bigrams from the 'bigrams' column.\n",
    "    bigrams = row['bigrams']\n",
    "\n",
    "    #Accumulator for sum(log(prob)).\n",
    "    sum_logProb = 0\n",
    "    #Total number of tokens/ngrams per sentence.\n",
    "    n = 0\n",
    "\n",
    "    for bigram in bigrams:\n",
    "      firstW, secondW = bigram\n",
    "      #Retrieve the probability of the token/ngram from the bigramProb dictionary.\n",
    "      prob = bigramProb.get((firstW, secondW))\n",
    "      #If probability cannot be retrieved + vocabDict is provided.\n",
    "      if prob is None and vocabDict:\n",
    "        #Calculate Laplace smoothing for unseen bigrams.\n",
    "        prob = unseenBigram(firstW, secondW, bigramProb, vocabDict, sentenceCount)\n",
    "\n",
    "      #If the bigram is found, calculate natural log as usual.\n",
    "      #Otherwise, set logProb to a very small number near 0.0\n",
    "      logProb = math.log(prob) if prob and prob > 0 else 1e-10\n",
    "\n",
    "      #Add to sum_logProb accumulator.\n",
    "      sum_logProb += logProb\n",
    "      #Count ngrams within the sentence.\n",
    "      n += 1\n",
    "\n",
    "    #Average negative log-likelihood for the sentence aka. multiply with (-1/n).\n",
    "    sentenceLikelihood = -sum_logProb / n\n",
    "    #Inverse multiplication in logarithmic space.\n",
    "    sentencePerplexity = math.exp(sentenceLikelihood)\n",
    "    sentence_perplexityList.append(sentencePerplexity)\n",
    "\n",
    "  #Average of the entire test corpus.\n",
    "  overallPerplexity = sum(sentence_perplexityList) / len(sentence_perplexityList)\n",
    "\n",
    "  return overallPerplexity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 6256,
     "status": "ok",
     "timestamp": 1729436508020,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "otSTk7CYo9QQ",
    "outputId": "7756f4e2-62d8-4b2c-99a6-66fad6329a7b"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train corpus Bigram Perplexity - without smoothing: 77.98881234050911\n"
     ]
    }
   ],
   "source": [
    "bigramPerplexity_nonSmoothing_train = bigramPerplexity(trainData, bigramProb)\n",
    "print(f\"Train corpus Bigram Perplexity - without smoothing: {bigramPerplexity_nonSmoothing_train}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1096,
     "status": "ok",
     "timestamp": 1729436509114,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "aQtvoPg68DKP",
    "outputId": "58617673-61a6-41a6-cbde-d6f6aa33dd28"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test corpus Bigram Perplexity - without smoothing: 31.565190424964392\n"
     ]
    }
   ],
   "source": [
    "bigramPerplexity_nonSmoothing_test = bigramPerplexity(testData, bigramProb)\n",
    "print(f\"Test corpus Bigram Perplexity - without smoothing: {bigramPerplexity_nonSmoothing_test}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "rhavpR8lTNJY"
   },
   "source": [
    "### **Trigram Perplexity - Non-smoothing**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1729436509114,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "c38MFjZvDffN"
   },
   "outputs": [],
   "source": [
    "def trigramPerplexity(data, trigramProb, sentenceCount = None, bigram_freqDist=None, vocabDict = None):\n",
    "  '''Calculate perplexity for the trigram model on sentence level.\n",
    "  Note: If vocabDict is provided, apply Laplace smoothing to calculate unseen bigrams probability.'''\n",
    "\n",
    "  #Store perplexity score of each sentence.\n",
    "  sentence_perplexityList = []\n",
    "  for index, row in data.iterrows():\n",
    "    #Unigrams from the 'unigrams' column.\n",
    "    trigrams = row['trigrams']\n",
    "    sum_logProb = 0\n",
    "    n = 0\n",
    "\n",
    "    for trigram in trigrams:\n",
    "      firstW, secondW, thirdW = trigram\n",
    "      #Retrieve the probability of the token/ngram from the unigramProb dictionary.\n",
    "      prob = trigramProb.get((firstW, secondW, thirdW))\n",
    "      #If the tuple cannot be found, set logProb to a very small number near 0.0\n",
    "      if prob is None and vocabDict and bigram_freqDist:\n",
    "        prob = unseenTrigram(firstW, secondW, thirdW, laplace_trigramProb, bigram_freqDist, vocabDict, sentenceCount)\n",
    "\n",
    "      #If the bigram is found, calculate natural log as usual.\n",
    "      #Otherwise, set logProb to a very small number near 0.0\n",
    "      logProb = math.log(prob) if prob and prob > 0 else 1e-10\n",
    "\n",
    "      #Take natural log then add to sum_logProb accumulator.\n",
    "      sum_logProb += logProb\n",
    "      #Count ngrams within the sentence.\n",
    "      n += 1\n",
    "\n",
    "    #Average negative log-likelihood for the sentence aka. multiply with (-1/n).\n",
    "    sentenceLikelihood = -sum_logProb / n\n",
    "    #Inverse multiplication in logarithmic space.\n",
    "    sentencePerplexity = math.exp(sentenceLikelihood)\n",
    "    sentence_perplexityList.append(sentencePerplexity)\n",
    "\n",
    "  #Average of the entire test corpus.\n",
    "  overallPerplexity = sum(sentence_perplexityList) / len(sentence_perplexityList)\n",
    "\n",
    "  return overallPerplexity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 5865,
     "status": "ok",
     "timestamp": 1729436514976,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "lQLqsddsp_lQ",
    "outputId": "fe5bb2af-a61c-46a3-932f-028a51aecfca"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train corpus Trigram Perplexity - without smoothing: 8.548195941609501\n"
     ]
    }
   ],
   "source": [
    "trigramPerplexity_nonSmoothing_train = trigramPerplexity(trainData, trigramProb)\n",
    "print(f\"Train corpus Trigram Perplexity - without smoothing: {trigramPerplexity_nonSmoothing_train}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1421,
     "status": "ok",
     "timestamp": 1729436516395,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "i2gKMaKnDgwu",
    "outputId": "ab056b0f-3af1-4ca8-e4c5-e93bf435cce9"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test corpus Trigram Perplexity - without smoothing: 3.4849884922982457\n"
     ]
    }
   ],
   "source": [
    "trigramPerplexity_nonSmoothing_test = trigramPerplexity(testData, trigramProb)\n",
    "print(f\"Test corpus Trigram Perplexity - without smoothing: {trigramPerplexity_nonSmoothing_test}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "iVRuSeSRT72O"
   },
   "source": [
    "### **(2) Perplexity laplace() with the Laplace smoothing**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "r5bnJI3m0Xsq"
   },
   "source": [
    "Note: Apply Laplace smoothing on training data --> Specifically on dictionaries to store frequency aka. probability **--> Update made on functions unigram(), bigram(), and trigram().**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "bxI27of8Ui3v"
   },
   "source": [
    "### **Unigram Perplexity - Laplace smoothing**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 4870,
     "status": "ok",
     "timestamp": 1729436521263,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "k1h3oYeEqPj3",
    "outputId": "39f90c7a-ea71-4e16-ab0d-5e6ca9cade24"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train corpus Unigram Perplexity - Laplace smoothing: 1077.9944246016585\n"
     ]
    }
   ],
   "source": [
    "unigramPerplexity_Smoothing_train = unigramPerplexity(trainData, laplace_unigramProb)\n",
    "print(f\"Train corpus Unigram Perplexity - Laplace smoothing: {unigramPerplexity_Smoothing_train}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 936,
     "status": "ok",
     "timestamp": 1729436522197,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "C6zmLyIjgxem",
    "outputId": "536894ba-7a12-4765-f16f-02f53cee331a"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test corpus Unigram Perplexity - Laplace smoothing: 998.2470901836243\n"
     ]
    }
   ],
   "source": [
    "unigramPerplexity_Smoothing_test = unigramPerplexity(testData, laplace_unigramProb)\n",
    "print(f\"Test corpus Unigram Perplexity - Laplace smoothing: {unigramPerplexity_Smoothing_test}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "MIDV1NSKqa6t"
   },
   "source": [
    "### **Bigram Perplexity - Laplace smoothing**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 5461,
     "status": "ok",
     "timestamp": 1729436527656,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "Epwa69nSqdvQ",
    "outputId": "30d51107-7205-4fc3-ce8a-dd14adc47fad"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train corpus Bigram Perplexity - Laplace smoothing: 1557.067020566824\n"
     ]
    }
   ],
   "source": [
    "bigramPerplexity_Smoothing_train = bigramPerplexity(trainData, laplace_bigramProb, trainData.shape[0], vocabDict_train)\n",
    "print(f\"Train corpus Bigram Perplexity - Laplace smoothing: {bigramPerplexity_Smoothing_train}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1391,
     "status": "ok",
     "timestamp": 1729436529044,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "-Pb_zrqkJYm4",
    "outputId": "d6327c73-76bd-4566-dfd5-d2988f6c7a76"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test corpus Bigram Perplexity - Laplace smoothing: 1864.0722543564689\n"
     ]
    }
   ],
   "source": [
    "bigramPerplexity_Smoothing_test = bigramPerplexity(testData, laplace_bigramProb, trainData.shape[0], vocabDict_train)\n",
    "print(f\"Test corpus Bigram Perplexity - Laplace smoothing: {bigramPerplexity_Smoothing_test}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "5u_fw_7qrJpP"
   },
   "source": [
    "### **Trigram Perplexity - Laplace smoothing**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 6724,
     "status": "ok",
     "timestamp": 1729436535766,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "zEUSLYmZrLrj",
    "outputId": "71072e3c-c2ff-4f8d-fd05-a99486fc486e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train corpus Trigram Perplexity - Laplace smoothing: 6420.969049255399\n"
     ]
    }
   ],
   "source": [
    "trigramPerplexity_Smoothing_train = trigramPerplexity(trainData, laplace_trigramProb, trainData.shape[0], bigram_freqDist, vocabDict_train)\n",
    "print(f\"Train corpus Trigram Perplexity - Laplace smoothing: {trigramPerplexity_Smoothing_train}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1385,
     "status": "ok",
     "timestamp": 1729436537148,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "3Sh0M0gIWeTm",
    "outputId": "19a54495-f768-45fc-9f94-79648915ae7f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test corpus Trigram Perplexity - Laplace smoothing: 10160.796925518838\n"
     ]
    }
   ],
   "source": [
    "trigramPerplexity_Smoothing_test = trigramPerplexity(testData, laplace_trigramProb, trainData.shape[0], bigram_freqDist, vocabDict_train)\n",
    "print(f\"Test corpus Trigram Perplexity - Laplace smoothing: {trigramPerplexity_Smoothing_test}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "7uPq4qGJqnQ8"
   },
   "source": [
    "### **Display outputs**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 238
    },
    "executionInfo": {
     "elapsed": 9,
     "status": "ok",
     "timestamp": 1729436537148,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "L5xiF2_fpFHd",
    "outputId": "3511880e-39d9-4b6c-bab0-72ec3ee1533b"
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Model</th>\n",
       "      <th>Smoothing</th>\n",
       "      <th>Dataset</th>\n",
       "      <th>Perplexity</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Unigram</td>\n",
       "      <td>Non-smoothing</td>\n",
       "      <td>Train</td>\n",
       "      <td>1080.361156</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Bigram</td>\n",
       "      <td>Non-smoothing</td>\n",
       "      <td>Train</td>\n",
       "      <td>77.988812</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Trigram</td>\n",
       "      <td>Non-smoothing</td>\n",
       "      <td>Train</td>\n",
       "      <td>8.548196</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Unigram</td>\n",
       "      <td>Laplace</td>\n",
       "      <td>Train</td>\n",
       "      <td>1077.994425</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Bigram</td>\n",
       "      <td>Laplace</td>\n",
       "      <td>Train</td>\n",
       "      <td>1557.067021</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>Trigram</td>\n",
       "      <td>Laplace</td>\n",
       "      <td>Train</td>\n",
       "      <td>6420.969049</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     Model      Smoothing Dataset   Perplexity\n",
       "0  Unigram  Non-smoothing   Train  1080.361156\n",
       "1   Bigram  Non-smoothing   Train    77.988812\n",
       "2  Trigram  Non-smoothing   Train     8.548196\n",
       "3  Unigram        Laplace   Train  1077.994425\n",
       "4   Bigram        Laplace   Train  1557.067021\n",
       "5  Trigram        Laplace   Train  6420.969049"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "perplexityRes_train = {'Model': ['Unigram', 'Bigram', 'Trigram', 'Unigram', 'Bigram', 'Trigram'],\n",
    "                       'Smoothing': ['Non-smoothing', 'Non-smoothing', 'Non-smoothing', 'Laplace', 'Laplace', 'Laplace'],\n",
    "                       'Dataset': ['Train', 'Train', 'Train', 'Train', 'Train', 'Train'],\n",
    "                       'Perplexity': [unigramPerplexity_nonSmoothing_train,\n",
    "                                      bigramPerplexity_nonSmoothing_train,\n",
    "                                      trigramPerplexity_nonSmoothing_train,\n",
    "                                      unigramPerplexity_Smoothing_train,\n",
    "                                      bigramPerplexity_Smoothing_train,\n",
    "                                      trigramPerplexity_Smoothing_train]}\n",
    "perplexityData_train = pd.DataFrame(perplexityRes_train)\n",
    "perplexityData_train"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 238
    },
    "executionInfo": {
     "elapsed": 9,
     "status": "ok",
     "timestamp": 1729436537149,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "t24fa1GxWZd3",
    "outputId": "dc4d6425-9db6-451b-ff35-3d368127629d"
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Model</th>\n",
       "      <th>Smoothing</th>\n",
       "      <th>Dataset</th>\n",
       "      <th>Perplexity</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Unigram</td>\n",
       "      <td>Non-smoothing</td>\n",
       "      <td>Test</td>\n",
       "      <td>998.725584</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Bigram</td>\n",
       "      <td>Non-smoothing</td>\n",
       "      <td>Test</td>\n",
       "      <td>31.565190</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Trigram</td>\n",
       "      <td>Non-smoothing</td>\n",
       "      <td>Test</td>\n",
       "      <td>3.484988</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Unigram</td>\n",
       "      <td>Laplace</td>\n",
       "      <td>Test</td>\n",
       "      <td>998.247090</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Bigram</td>\n",
       "      <td>Laplace</td>\n",
       "      <td>Test</td>\n",
       "      <td>1864.072254</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>Trigram</td>\n",
       "      <td>Laplace</td>\n",
       "      <td>Test</td>\n",
       "      <td>10160.796926</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     Model      Smoothing Dataset    Perplexity\n",
       "0  Unigram  Non-smoothing    Test    998.725584\n",
       "1   Bigram  Non-smoothing    Test     31.565190\n",
       "2  Trigram  Non-smoothing    Test      3.484988\n",
       "3  Unigram        Laplace    Test    998.247090\n",
       "4   Bigram        Laplace    Test   1864.072254\n",
       "5  Trigram        Laplace    Test  10160.796926"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "perplexityRes_test = {'Model': ['Unigram', 'Bigram', 'Trigram', 'Unigram', 'Bigram', 'Trigram'],\n",
    "                      'Smoothing': ['Non-smoothing', 'Non-smoothing', 'Non-smoothing', 'Laplace', 'Laplace', 'Laplace'],\n",
    "                      'Dataset': ['Test', 'Test', 'Test', 'Test', 'Test', 'Test'],\n",
    "                      'Perplexity': [unigramPerplexity_nonSmoothing_test,\n",
    "                                     bigramPerplexity_nonSmoothing_test,\n",
    "                                     trigramPerplexity_nonSmoothing_test,\n",
    "                                     unigramPerplexity_Smoothing_test,\n",
    "                                     bigramPerplexity_Smoothing_test,\n",
    "                                     trigramPerplexity_Smoothing_test]}\n",
    "perplexityData_test = pd.DataFrame(perplexityRes_test)\n",
    "perplexityData_test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "X4obU8L2JYWy"
   },
   "source": [
    "#**Text Generation from Ngram Language Models**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "4czvUjJyMNcH"
   },
   "source": [
    "### **Load and Merge of the data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 133
    },
    "executionInfo": {
     "elapsed": 242,
     "status": "ok",
     "timestamp": 1729436537383,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "9MpwdeXlKHDP",
    "outputId": "1a1f612e-186c-4815-b648-2bf209520cf5"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of (rows, columns): (61530, 1)\n",
      "Number of (rows, columns): (12105, 1)\n",
      "Number of (rows, columns): (73635, 1)\n"
     ]
    },
    {
     "data": {
      "application/vnd.google.colaboratory.intrinsic+json": {
       "summary": "{\n  \"name\": \"mergedData\",\n  \"rows\": 73635,\n  \"fields\": [\n    {\n      \"column\": \"sentence\",\n      \"properties\": {\n        \"dtype\": \"string\",\n        \"num_unique_values\": 73635,\n        \"samples\": [\n          \"We loaded gear onto plastic toboggans and crossed the small lake in waning daylight to a log cabin on a rocky point .\\n\",\n          \"And the couple -- who both work in the entertainment business -- feel that they are winning , although they are paying a financial as well as an emotional price ; the treatment has so far cost them in excess of \\u00c2\\u00a3 100,000 .\\n\",\n          \"It relies on more than 20,000 \\\" contractors \\\" ( they 're not officially employees ) working out of their homes .\\n\"\n        ],\n        \"semantic_type\": \"\",\n        \"description\": \"\"\n      }\n    }\n  ]\n}",
       "type": "dataframe",
       "variable_name": "mergedData"
      },
      "text/html": [
       "\n",
       "  <div id=\"df-7edd2c1b-6b07-4144-9c28-e0046734438d\" class=\"colab-df-container\">\n",
       "    <div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sentence</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Having a little flexibility on that issue woul...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>\n",
       "    <div class=\"colab-df-buttons\">\n",
       "\n",
       "  <div class=\"colab-df-container\">\n",
       "    <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-7edd2c1b-6b07-4144-9c28-e0046734438d')\"\n",
       "            title=\"Convert this dataframe to an interactive table.\"\n",
       "            style=\"display:none;\">\n",
       "\n",
       "  <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\" viewBox=\"0 -960 960 960\">\n",
       "    <path d=\"M120-120v-720h720v720H120Zm60-500h600v-160H180v160Zm220 220h160v-160H400v160Zm0 220h160v-160H400v160ZM180-400h160v-160H180v160Zm440 0h160v-160H620v160ZM180-180h160v-160H180v160Zm440 0h160v-160H620v160Z\"/>\n",
       "  </svg>\n",
       "    </button>\n",
       "\n",
       "  <style>\n",
       "    .colab-df-container {\n",
       "      display:flex;\n",
       "      gap: 12px;\n",
       "    }\n",
       "\n",
       "    .colab-df-convert {\n",
       "      background-color: #E8F0FE;\n",
       "      border: none;\n",
       "      border-radius: 50%;\n",
       "      cursor: pointer;\n",
       "      display: none;\n",
       "      fill: #1967D2;\n",
       "      height: 32px;\n",
       "      padding: 0 0 0 0;\n",
       "      width: 32px;\n",
       "    }\n",
       "\n",
       "    .colab-df-convert:hover {\n",
       "      background-color: #E2EBFA;\n",
       "      box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
       "      fill: #174EA6;\n",
       "    }\n",
       "\n",
       "    .colab-df-buttons div {\n",
       "      margin-bottom: 4px;\n",
       "    }\n",
       "\n",
       "    [theme=dark] .colab-df-convert {\n",
       "      background-color: #3B4455;\n",
       "      fill: #D2E3FC;\n",
       "    }\n",
       "\n",
       "    [theme=dark] .colab-df-convert:hover {\n",
       "      background-color: #434B5C;\n",
       "      box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
       "      filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
       "      fill: #FFFFFF;\n",
       "    }\n",
       "  </style>\n",
       "\n",
       "    <script>\n",
       "      const buttonEl =\n",
       "        document.querySelector('#df-7edd2c1b-6b07-4144-9c28-e0046734438d button.colab-df-convert');\n",
       "      buttonEl.style.display =\n",
       "        google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
       "\n",
       "      async function convertToInteractive(key) {\n",
       "        const element = document.querySelector('#df-7edd2c1b-6b07-4144-9c28-e0046734438d');\n",
       "        const dataTable =\n",
       "          await google.colab.kernel.invokeFunction('convertToInteractive',\n",
       "                                                    [key], {});\n",
       "        if (!dataTable) return;\n",
       "\n",
       "        const docLinkHtml = 'Like what you see? Visit the ' +\n",
       "          '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
       "          + ' to learn more about interactive tables.';\n",
       "        element.innerHTML = '';\n",
       "        dataTable['output_type'] = 'display_data';\n",
       "        await google.colab.output.renderOutput(dataTable, element);\n",
       "        const docLink = document.createElement('div');\n",
       "        docLink.innerHTML = docLinkHtml;\n",
       "        element.appendChild(docLink);\n",
       "      }\n",
       "    </script>\n",
       "  </div>\n",
       "\n",
       "\n",
       "    </div>\n",
       "  </div>\n"
      ],
      "text/plain": [
       "                                            sentence\n",
       "0  Having a little flexibility on that issue woul..."
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trainData2 = loadData(\"1b_benchmark_train_tokens.txt\")\n",
    "testData2 = loadData(\"1b_benchmark_test_tokens.txt\")\n",
    "mergedData = pd.concat([trainData2, testData2], ignore_index=True)\n",
    "print(f'Number of (rows, columns): {mergedData.shape}')\n",
    "mergedData.head(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "0RJUtuRkMQmU"
   },
   "source": [
    "### **Get merged vocabulary dictionary**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 647,
     "status": "ok",
     "timestamp": 1729436538025,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "aSyxdRXiJJuG",
    "outputId": "bd71285f-f554-4afb-ae62-db2b32e335fa"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of unique tokens - without '<START>': 29479\n",
      "----First five tokens----\n",
      "Having: 56\n",
      "a: 37496\n",
      "little: 549\n",
      "flexibility: 17\n",
      "on: 13744\n"
     ]
    }
   ],
   "source": [
    "vocabDict_merge = vocabDict(mergedData)\n",
    "print(f\"Number of unique tokens - without '<START>': {len(vocabDict_merge)}\")\n",
    "print('----First five tokens----')\n",
    "for token, count in list(vocabDict_merge.items())[:5]:\n",
    "    print(f\"{token}: {count}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "HcYa8BbTPFRH"
   },
   "source": [
    "### **Create ngrams**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 81
    },
    "executionInfo": {
     "elapsed": 3630,
     "status": "ok",
     "timestamp": 1729436541652,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "M5b1YujIPIZp",
    "outputId": "571522a6-38aa-4e9e-c905-a3dd9f83817e"
   },
   "outputs": [
    {
     "data": {
      "application/vnd.google.colaboratory.intrinsic+json": {
       "summary": "{\n  \"name\": \"mergedData\",\n  \"rows\": 73635,\n  \"fields\": [\n    {\n      \"column\": \"sentence\",\n      \"properties\": {\n        \"dtype\": \"string\",\n        \"num_unique_values\": 73635,\n        \"samples\": [\n          \"We loaded gear onto plastic toboggans and crossed the small lake in waning daylight to a log cabin on a rocky point .\\n\",\n          \"And the couple -- who both work in the entertainment business -- feel that they are winning , although they are paying a financial as well as an emotional price ; the treatment has so far cost them in excess of \\u00c2\\u00a3 100,000 .\\n\",\n          \"It relies on more than 20,000 \\\" contractors \\\" ( they 're not officially employees ) working out of their homes .\\n\"\n        ],\n        \"semantic_type\": \"\",\n        \"description\": \"\"\n      }\n    },\n    {\n      \"column\": \"unigrams\",\n      \"properties\": {\n        \"dtype\": \"object\",\n        \"semantic_type\": \"\",\n        \"description\": \"\"\n      }\n    },\n    {\n      \"column\": \"bigrams\",\n      \"properties\": {\n        \"dtype\": \"object\",\n        \"semantic_type\": \"\",\n        \"description\": \"\"\n      }\n    },\n    {\n      \"column\": \"trigrams\",\n      \"properties\": {\n        \"dtype\": \"object\",\n        \"semantic_type\": \"\",\n        \"description\": \"\"\n      }\n    }\n  ]\n}",
       "type": "dataframe",
       "variable_name": "mergedData"
      },
      "text/html": [
       "\n",
       "  <div id=\"df-a5214cdb-7dc8-4bd2-8ad3-319db0a2e106\" class=\"colab-df-container\">\n",
       "    <div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sentence</th>\n",
       "      <th>unigrams</th>\n",
       "      <th>bigrams</th>\n",
       "      <th>trigrams</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Having a little flexibility on that issue woul...</td>\n",
       "      <td>[(Having,), (a,), (little,), (flexibility,), (...</td>\n",
       "      <td>[(&lt;START&gt;, Having), (Having, a), (a, little), ...</td>\n",
       "      <td>[(&lt;START&gt;, &lt;START&gt;, Having), (&lt;START&gt;, Having,...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>\n",
       "    <div class=\"colab-df-buttons\">\n",
       "\n",
       "  <div class=\"colab-df-container\">\n",
       "    <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-a5214cdb-7dc8-4bd2-8ad3-319db0a2e106')\"\n",
       "            title=\"Convert this dataframe to an interactive table.\"\n",
       "            style=\"display:none;\">\n",
       "\n",
       "  <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\" viewBox=\"0 -960 960 960\">\n",
       "    <path d=\"M120-120v-720h720v720H120Zm60-500h600v-160H180v160Zm220 220h160v-160H400v160Zm0 220h160v-160H400v160ZM180-400h160v-160H180v160Zm440 0h160v-160H620v160ZM180-180h160v-160H180v160Zm440 0h160v-160H620v160Z\"/>\n",
       "  </svg>\n",
       "    </button>\n",
       "\n",
       "  <style>\n",
       "    .colab-df-container {\n",
       "      display:flex;\n",
       "      gap: 12px;\n",
       "    }\n",
       "\n",
       "    .colab-df-convert {\n",
       "      background-color: #E8F0FE;\n",
       "      border: none;\n",
       "      border-radius: 50%;\n",
       "      cursor: pointer;\n",
       "      display: none;\n",
       "      fill: #1967D2;\n",
       "      height: 32px;\n",
       "      padding: 0 0 0 0;\n",
       "      width: 32px;\n",
       "    }\n",
       "\n",
       "    .colab-df-convert:hover {\n",
       "      background-color: #E2EBFA;\n",
       "      box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
       "      fill: #174EA6;\n",
       "    }\n",
       "\n",
       "    .colab-df-buttons div {\n",
       "      margin-bottom: 4px;\n",
       "    }\n",
       "\n",
       "    [theme=dark] .colab-df-convert {\n",
       "      background-color: #3B4455;\n",
       "      fill: #D2E3FC;\n",
       "    }\n",
       "\n",
       "    [theme=dark] .colab-df-convert:hover {\n",
       "      background-color: #434B5C;\n",
       "      box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
       "      filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
       "      fill: #FFFFFF;\n",
       "    }\n",
       "  </style>\n",
       "\n",
       "    <script>\n",
       "      const buttonEl =\n",
       "        document.querySelector('#df-a5214cdb-7dc8-4bd2-8ad3-319db0a2e106 button.colab-df-convert');\n",
       "      buttonEl.style.display =\n",
       "        google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
       "\n",
       "      async function convertToInteractive(key) {\n",
       "        const element = document.querySelector('#df-a5214cdb-7dc8-4bd2-8ad3-319db0a2e106');\n",
       "        const dataTable =\n",
       "          await google.colab.kernel.invokeFunction('convertToInteractive',\n",
       "                                                    [key], {});\n",
       "        if (!dataTable) return;\n",
       "\n",
       "        const docLinkHtml = 'Like what you see? Visit the ' +\n",
       "          '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
       "          + ' to learn more about interactive tables.';\n",
       "        element.innerHTML = '';\n",
       "        dataTable['output_type'] = 'display_data';\n",
       "        await google.colab.output.renderOutput(dataTable, element);\n",
       "        const docLink = document.createElement('div');\n",
       "        docLink.innerHTML = docLinkHtml;\n",
       "        element.appendChild(docLink);\n",
       "      }\n",
       "    </script>\n",
       "  </div>\n",
       "\n",
       "\n",
       "    </div>\n",
       "  </div>\n"
      ],
      "text/plain": [
       "                                            sentence  \\\n",
       "0  Having a little flexibility on that issue woul...   \n",
       "\n",
       "                                            unigrams  \\\n",
       "0  [(Having,), (a,), (little,), (flexibility,), (...   \n",
       "\n",
       "                                             bigrams  \\\n",
       "0  [(<START>, Having), (Having, a), (a, little), ...   \n",
       "\n",
       "                                            trigrams  \n",
       "0  [(<START>, <START>, Having), (<START>, Having,...  "
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mergedData = gen_ngramsList(mergedData, vocabDict_merge)\n",
    "mergedData.head(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Sy3P-ZU-MwX0"
   },
   "source": [
    "### **Creates a conditional frequency distribution**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 4634,
     "status": "ok",
     "timestamp": 1729436546282,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "5OUwI21-MG6X",
    "outputId": "873b9bdc-9c0f-4119-8274-54cf22fcbd28"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bigram ('Clinton', 'leading') frequency: 1\n"
     ]
    }
   ],
   "source": [
    "bigram_freqDist_merge = gen_ConditionalFreqDist(mergedData, 'bigrams')\n",
    "print(\"Bigram ('Clinton', 'leading') frequency:\", bigram_freqDist_merge[('Clinton',)]['leading'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 6241,
     "status": "ok",
     "timestamp": 1729436552520,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "-aKffC4CNOnG",
    "outputId": "e8cc827d-e591-407e-9f71-93e01372aebd"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trigram ('I', 'believe', 'he') frequency: 1\n"
     ]
    }
   ],
   "source": [
    "trigram_freqDist_merge = gen_ConditionalFreqDist(mergedData, 'trigrams')\n",
    "print(\"Trigram ('I', 'believe', 'he') frequency:\", trigram_freqDist_merge[('I', 'believe')]['he'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "aV_mCoyaN0I2"
   },
   "source": [
    "### **Unigram model**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1619,
     "status": "ok",
     "timestamp": 1729436554136,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "MU4V08FfN3KQ",
    "outputId": "7bb5bb08-7588-4784-cd21-f08564c777de"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unigram probability | non-smoothing for 'Reihana': 1.5454413857869878e-06\n",
      "Unigram probability | Laplace smoothing for 'Reihana': 2.02976446613135e-06\n"
     ]
    }
   ],
   "source": [
    "unigramProb_merge, laplace_unigramProb_merge = unigram(mergedData)\n",
    "print(\"Unigram probability | non-smoothing for 'Reihana':\", unigramProb_merge.get('Reihana', 0))\n",
    "print(\"Unigram probability | Laplace smoothing for 'Reihana':\", laplace_unigramProb_merge.get('Reihana', 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "n_s4lHlFQVeK"
   },
   "source": [
    "### **Bigram model**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1412,
     "status": "ok",
     "timestamp": 1729436555545,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "o0EuLDIPQTEa",
    "outputId": "6d5725d3-d4cb-4e91-e2fc-703339877f9f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bigram probability | non-smoothing for ('a', 'little'): 0.005280563260081075\n",
      "Bigram probability | Laplace smoothing for ('a', 'little'): 0.002971257932064203\n"
     ]
    }
   ],
   "source": [
    "bigramProb_merge, laplace_bigramProb_merge = bigram(bigram_freqDist_merge, vocabDict_merge, mergedData.shape[0])\n",
    "print(\"Bigram probability | non-smoothing for ('a', 'little'):\", bigramProb_merge.get(('a', 'little'), 0))\n",
    "print(\"Bigram probability | Laplace smoothing for ('a', 'little'):\", laplace_bigramProb_merge.get(('a', 'little'), 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "v_wbn5Z_Qlm4"
   },
   "source": [
    "### **Trigram model**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 6692,
     "status": "ok",
     "timestamp": 1729436562234,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "jx42zSZbQk1A",
    "outputId": "e3fa6a01-9aaa-4292-a032-aac501900475"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trigram probability | non-smoothing for ('a', 'union', 'leader'): 0.14285714285714285\n",
      "Trigram probability | Laplace smoothing for ('a', 'union', 'leader'): 6.782880010852608e-05\n"
     ]
    }
   ],
   "source": [
    "trigramProb_merge, laplace_trigramProb_merge = trigram(trigram_freqDist_merge, bigram_freqDist_merge, vocabDict_merge, mergedData.shape[0])\n",
    "print(\"Trigram probability | non-smoothing for ('a', 'union', 'leader'):\", trigramProb_merge.get(('a', 'union', 'leader'), 0))\n",
    "print(\"Trigram probability | Laplace smoothing for ('a', 'union', 'leader'):\", laplace_trigramProb_merge.get(('a', 'union', 'leader'), 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "gICeZbuFUC8h"
   },
   "source": [
    "### **Speedy Choice**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1729436562234,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "aai_rMPWbMaP"
   },
   "outputs": [],
   "source": [
    "def gen_greedyChoice(probDict, ngram='unigram', wordCount=100):\n",
    "  '''Generate a sentence using the ngram model output.\n",
    "  Logic: Greedy choice, next word is selected based on maximum probability with context word.\n",
    "  Params: probDict: Dictionary containing ngram probabilities (unigram, bigram, or trigram).\n",
    "          ngram: Type of ngram model - unigram, bigram, trigram.\n",
    "          wordCount: Maximum word to generate.\n",
    "  Note: probDict are result from Ngrams models.'''\n",
    "\n",
    "  if ngram == 'unigram':\n",
    "    text = []\n",
    "  elif ngram == 'bigram':\n",
    "    text = ['<START>']\n",
    "  elif ngram == 'trigram':\n",
    "    text = ['<START>', '<START>']\n",
    "\n",
    "  while len(text) < wordCount:\n",
    "    if ngram == 'unigram':\n",
    "      #Note: unigramProb = {word1: prob}\n",
    "      #Choose next word based on highest probability.\n",
    "      nextWord = max(probDict, key=probDict.get)\n",
    "      text.append(nextWord)\n",
    "\n",
    "    elif ngram == 'bigram':\n",
    "      #Note: bigramProb = {(word1, word2): prob}\n",
    "      currentWord = text[-1]\n",
    "      #Find the tuple with the maximum probability.\n",
    "      nextWord = max(((secondW, prob) for (firstW, secondW), prob in probDict.items() if firstW == currentWord),\n",
    "                 key=lambda x: x[1], default=(None, 0))[0]\n",
    "      text.append(nextWord)\n",
    "\n",
    "    elif ngram == 'trigram':\n",
    "      #Note: trigramProb = {(word1, word2, word3): prob}\n",
    "      firstW, secondW = text[-2], text[-1]\n",
    "      #Find the tuple with the maximum probability.\n",
    "      nextWord = max(((third, prob) for (first, second, third), prob in probDict.items() if first == firstW and second == secondW),\n",
    "                 key=lambda x: x[1], default=(None, 0))[0]\n",
    "      text.append(nextWord)\n",
    "\n",
    "  return ' '.join(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 47383,
     "status": "ok",
     "timestamp": 1729436609614,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "kvBkO99qQ0iL",
    "outputId": "ddbdb6d1-e25e-4c05-ab10-4db6768c050f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unigram Greedy Choice Sentence:\n",
      "the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the\n",
      "Bigram Greedy Choice Sentence:\n",
      "<START> The <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> , the <unk> ,\n",
      "Trigram Greedy choice Sentence:\n",
      "<START> <START> The <unk> <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> , <unk> ,\n"
     ]
    }
   ],
   "source": [
    "unigramSentence_greedyChoice = gen_greedyChoice(unigramProb_merge, ngram='unigram')\n",
    "bigramSentence_greedyChoice = gen_greedyChoice(bigramProb_merge, ngram='bigram')\n",
    "trigramSentence_greedyChoice = gen_greedyChoice(trigramProb_merge, ngram='trigram')\n",
    "\n",
    "print('Unigram Greedy Choice Sentence:')\n",
    "print(f'{unigramSentence_greedyChoice}')\n",
    "print('Bigram Greedy Choice Sentence:')\n",
    "print(f'{bigramSentence_greedyChoice}')\n",
    "print('Trigram Greedy choice Sentence:')\n",
    "print(f'{trigramSentence_greedyChoice}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "mWlVBhG9jWEJ"
   },
   "source": [
    "### **Random Sampling**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1729436609614,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "JlHI-eWijVgr"
   },
   "outputs": [],
   "source": [
    "def gen_randomSampling(probDict, ngram='unigram', wordCount=100):\n",
    "  '''Generate a sentence using the ngram model output.\n",
    "  Logic: Random sampling, next word is randomly selected based on context word.\n",
    "  Params: probDict: Dictionary containing ngram probabilities (unigram, bigram, or trigram).\n",
    "          ngram: Type of ngram model - unigram, bigram, trigram.\n",
    "          wordCount: Maximum word to generate.\n",
    "  Note: probDict are result from Ngrams models.\n",
    "        Early stopping apply, end sentence with <STOP>'''\n",
    "\n",
    "  if ngram == 'unigram':\n",
    "    text = []\n",
    "  elif ngram == 'bigram':\n",
    "    text = ['<START>']\n",
    "  elif ngram == 'trigram':\n",
    "    text = ['<START>', '<START>']\n",
    "\n",
    "  while len(text) < wordCount:\n",
    "    if ngram == 'unigram':\n",
    "      #Create two tuples, one for word, one for corresponding probability.\n",
    "      words, probs = zip(*probDict.items())\n",
    "      #Select a random word.\n",
    "      nextWord = random.choices(words, probs)[0]\n",
    "      #Early stopping.\n",
    "      if nextWord == '<STOP>':\n",
    "        text.append(nextWord)\n",
    "        break\n",
    "      text.append(nextWord)\n",
    "\n",
    "    elif ngram == 'bigram':\n",
    "      currentWord = text[-1]\n",
    "      #List of next words based on previous context word.\n",
    "      next_wordList = [(pair[1], prob) for pair, prob in probDict.items() if pair[0] == currentWord]\n",
    "      #If there is no word associated with context word.\n",
    "      if not next_wordList:\n",
    "        text.append('<STOP>')\n",
    "        break\n",
    "      #Select a random word.\n",
    "      words, probs = zip(*next_wordList)\n",
    "      nextWord = random.choices(words, probs)[0]\n",
    "      if nextWord == '<STOP>':\n",
    "        text.append(nextWord)\n",
    "        break\n",
    "      text.append(nextWord)\n",
    "\n",
    "    elif ngram == 'trigram':\n",
    "      firstW, secondW = text[-2], text[-1]\n",
    "      #List of next words based on previous context words.\n",
    "      next_wordList = [(pair[2], prob) for pair, prob in probDict.items() if pair[0] == firstW and pair[1] == secondW]\n",
    "      #If there is no word associated with context words.\n",
    "      if not next_wordList:\n",
    "        text.append('<STOP>')\n",
    "        break\n",
    "      #Select a random word.\n",
    "      words, probs = zip(*next_wordList)\n",
    "      nextWord = random.choices(words, probs)[0]\n",
    "      if nextWord == '<STOP>':\n",
    "        text.append(nextWord)\n",
    "        break\n",
    "      text.append(nextWord)\n",
    "\n",
    "  return ' '.join(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 11991,
     "status": "ok",
     "timestamp": 1729436621601,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "Y7ol9XymwuXb",
    "outputId": "d120d7d6-ebc9-4551-cf7b-a6701d1fa845"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unigram Random Sampling Sentence:\n",
      "be she Saturday . Web night ) , of -- he fourth at or surveys in him field Berlusconi the groups pillows top dark revised at continue the a starts a base ? arrested fortune the house the have wrong Katherine below Republicans No-one \" 's , thrown with 've paint a Yeah to . him be would been he dozen - the 2010 <STOP>\n",
      "Bigram Random Sampling Sentence:\n",
      "<START> The Italian Sara <unk> to bubble , the real estate built on suspension of her late Wednesday in income countries . <STOP>\n",
      "Trigram Random Sampling Sentence:\n",
      "<START> <START> more alarm capacity than ever before to the black and Asian equity derivatives businesses ; and Western nations to decide , the two men met in <unk> Services as it was like before the start . <STOP>\n"
     ]
    }
   ],
   "source": [
    "unigramSentence_randomSampling = gen_randomSampling(unigramProb_merge, ngram='unigram')\n",
    "bigramSentence_randomSampling = gen_randomSampling(bigramProb_merge, ngram='bigram')\n",
    "trigramSentence_randomSampling = gen_randomSampling(trigramProb_merge, ngram='trigram')\n",
    "print('Unigram Random Sampling Sentence:')\n",
    "print(f'{unigramSentence_randomSampling}')\n",
    "print('Bigram Random Sampling Sentence:')\n",
    "print(f'{bigramSentence_randomSampling}')\n",
    "print('Trigram Random Sampling Sentence:')\n",
    "print(f'{trigramSentence_randomSampling}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "XsXWT574w_Gd"
   },
   "source": [
    "### **Top-p nucleus sampling -- experiment with  different p**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "executionInfo": {
     "elapsed": 4,
     "status": "ok",
     "timestamp": 1729436621601,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "HXG9MEuuYbkA"
   },
   "outputs": [],
   "source": [
    "def gen_topP_sampling(probDict, p=0.4, ngram='unigram', wordCount=100):\n",
    "  '''Generate a sentence using the ngram model output.\n",
    "  Logic: Top-p nucleus sampling, next word is randomly selected based on context word.\n",
    "         Where next word pool is based on sum of their probabilities atlest equals to p.\n",
    "  Params: probDict: Dictionary containing ngram probabilities (unigram, bigram, or trigram).\n",
    "          p: Cumulative probability threshold for nucleus sampling.\n",
    "          ngram: Type of ngram model - unigram, bigram, trigram.\n",
    "          wordCount: Maximum word to generate.\n",
    "  Note: probDict are result from Ngrams models.\n",
    "        Early stopping apply, end sentence with <STOP>'''\n",
    "\n",
    "  if ngram == 'unigram':\n",
    "    text = []\n",
    "  elif ngram == 'bigram':\n",
    "    text = ['<START>']\n",
    "  elif ngram == 'trigram':\n",
    "    text = ['<START>', '<START>']\n",
    "\n",
    "  while len(text) < wordCount:\n",
    "    if ngram == 'unigram':\n",
    "      #Sort by probability in descending order.\n",
    "      sorted_probDict = sorted(probDict.items(), key=lambda x: x[1], reverse=True)\n",
    "\n",
    "      #Get top tokens.\n",
    "      cumulativeProb = 0\n",
    "      next_wordList = []\n",
    "      for word, prob in sorted_probDict:\n",
    "        next_wordList.append((word, prob))\n",
    "        cumulativeProb += prob\n",
    "        if cumulativeProb >= p:\n",
    "          break\n",
    "      #Select a random word.\n",
    "      words, probs = zip(*next_wordList)\n",
    "      nextWord = random.choices(words, probs)[0]\n",
    "      if nextWord == '<STOP>':\n",
    "        text.append(nextWord)\n",
    "        break\n",
    "      text.append(nextWord)\n",
    "\n",
    "    elif ngram == 'bigram':\n",
    "      currentWord = text[-1]\n",
    "      #List of all (next words, probability) based on context.\n",
    "      next_wordList = [(pair[1], prob) for pair, prob in probDict.items() if pair[0] == currentWord]\n",
    "      if not next_wordList:\n",
    "        text.append('<STOP>')\n",
    "        break\n",
    "      #Sort by probability in descending order and get top tokens.\n",
    "      next_wordList.sort(key=lambda x: x[1], reverse=True)\n",
    "      cumulativeProb = 0\n",
    "      final_next_wordList = []\n",
    "      for word, prob in next_wordList:\n",
    "        final_next_wordList.append((word, prob))\n",
    "        cumulativeProb += prob\n",
    "        if cumulativeProb >= p:\n",
    "          break\n",
    "      #Select a random word.\n",
    "      words, probs = zip(*final_next_wordList)\n",
    "      nextWord = random.choices(words, probs)[0]\n",
    "      if nextWord == '<STOP>':\n",
    "        text.append(nextWord)\n",
    "        break\n",
    "      text.append(nextWord)\n",
    "\n",
    "    elif ngram == 'trigram':\n",
    "      firstW, secondW = text[-2], text[-1]\n",
    "      #List of all (next words, probability) based on context.\n",
    "      next_wordList = [(pair[2], prob) for pair, prob in probDict.items() if pair[0] == firstW and pair[1] == secondW]\n",
    "      if not next_wordList:\n",
    "        text.append('<STOP>')\n",
    "        break\n",
    "      #Sort by probability in descending order and get top tokens.\n",
    "      next_wordList.sort(key=lambda x: x[1], reverse=True)\n",
    "      cumulativeProb = 0\n",
    "      final_next_wordList = []\n",
    "      for word, prob in next_wordList:\n",
    "        final_next_wordList.append((word, prob))\n",
    "        cumulativeProb += prob\n",
    "        if cumulativeProb >= p:\n",
    "          break\n",
    "      #Select a random word.\n",
    "      words, probs = zip(*final_next_wordList)\n",
    "      nextWord = random.choices(words, probs)[0]\n",
    "      if nextWord == '<STOP>':\n",
    "        text.append(nextWord)\n",
    "        break\n",
    "      text.append(nextWord)\n",
    "\n",
    "  return ' '.join(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 13044,
     "status": "ok",
     "timestamp": 1729436634642,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "GGlaiBGCUa-G",
    "outputId": "89184488-8285-4736-be28-6f597ea91d1e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Unigram Top-p Sampling Sentence:\n",
      "technology 17 response <unk> of the for <unk> . tour problem property to Democratic . would lost other . the London Texas , in to the I from to unemployment . including last of air up is , new won about than . <unk> the talking not night who base \" a ' given to , statement for girls his , has <STOP>\n",
      "Bigram Top-p Sampling Sentence:\n",
      "<START> ( US Open in their long-running pay for five points out of his brother in Afghanistan and learn what has approved by letter of the busy . <STOP>\n",
      "Trigram Top-p Sampling Sentence:\n",
      "<START> <START> City may have <unk> the sites for <unk> <unk> has said that for women self-confidence and weight were closely connected to the United States ' 2008 presidential campaign and asked for extra features , but don 't know how long a turkey shoot on Valentine 's Day , 2004 , he saw short track for a skinny girl to share it with a <unk> , a role model , with the gas prices . <STOP>\n"
     ]
    }
   ],
   "source": [
    "unigramSentence_topP_sampling = gen_topP_sampling(unigramProb_merge, p=0.8, ngram='unigram')\n",
    "bigramSentence_topP_sampling = gen_topP_sampling(bigramProb_merge, p=0.8, ngram='bigram')\n",
    "trigramSentence_topP_sampling = gen_topP_sampling(trigramProb_merge, p=0.8, ngram='trigram')\n",
    "print('Unigram Top-p Sampling Sentence:')\n",
    "print(f'{unigramSentence_topP_sampling}')\n",
    "print('Bigram Top-p Sampling Sentence:')\n",
    "print(f'{bigramSentence_topP_sampling}')\n",
    "print('Trigram Top-p Sampling Sentence:')\n",
    "print(f'{trigramSentence_topP_sampling}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "executionInfo": {
     "elapsed": 20576,
     "status": "ok",
     "timestamp": 1729437652220,
     "user": {
      "displayName": "Mai Ngo",
      "userId": "00292170341618798690"
     },
     "user_tz": 300
    },
    "id": "TgCazh7XB89d"
   },
   "outputs": [],
   "source": [
    "!apt-get -qq install -y pandoc > /dev/null 2>&1\n",
    "!apt-get install texlive-xetex texlive-fonts-recommended texlive-plain-generic > /dev/null 2>&1\n",
    "!jupyter nbconvert --to pdf \"/content/drive/MyDrive/CSC583/CSC583 - Assignment 4.ipynb\" > /dev/null 2>&1"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyM8KtP4d7NI7TvvfhU/YF3K",
   "provenance": [
    {
     "file_id": "1RbzYrq8MWfHeLFmy1JXMKBvZDJ_Z0Rxd",
     "timestamp": 1729434723944
    }
   ]
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}