Auto_Completion_using_NGrams.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Auto Completion  using NGrams",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-iogp6gfZvrT"
      },
      "source": [
        "**Auto Complete using N-Grams\n**",
        "<br><br>\n",
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "v5iCWMtKZ5sl"
      },
      "source": [
        "#Initial imports done\n",
        "\n",
        "import math\n",
        "import nltk\n",
        "import random\n",
        "import pickle\n",
        "import numpy as np\n",
        "import pandas as pd\n",
        "from sklearn.model_selection import train_test_split\n",
        "import matplotlib.pyplot as plt\n",
        "\n"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "E4Oi7eg9chG2",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4719fe44-e52e-482c-f6f6-f01443c1b25b"
      },
      "source": [
        "# Since the data is in text format\n",
        "data_dir = \"/content\"\n",
        "file_path = data_dir + \"/en_US.twitter.txt\"\n",
        "\n",
        "## nltk settings\n",
        "nltk.data.path.append(data_dir)\n",
        "nltk.download('punkt')\n",
        "\n",
        "with open(file_path,'r') as filedata:\n",
        "  textdata = filedata.read()"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[nltk_data] Downloading package punkt to /root/nltk_data...\n",
            "[nltk_data]   Unzipping tokenizers/punkt.zip.\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6BbzMzkqgIhz",
        "outputId": "73754264-23c9-4f81-f571-2188f9927cf0"
      },
      "source": [
        "f1 = open(file_path,'r')\n",
        "count =0\n",
        "for i in f1.readlines():\n",
        "  if(count <10):\n",
        "    print(i)\n",
        "    print(\"\\n\")\n",
        "\n",
        "  count+=1\n"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "How are you? Btw thanks for the RT. You gonna be in DC anytime soon? Love to see you. Been way, way too long.\n",
            "\n",
            "\n",
            "\n",
            "When you meet someone special... you'll know. Your heart will beat more rapidly and you'll smile for no reason.\n",
            "\n",
            "\n",
            "\n",
            "they've decided its more fun if I don't.\n",
            "\n",
            "\n",
            "\n",
            "So Tired D; Played Lazer Tag & Ran A LOT D; Ughh Going To Sleep Like In 5 Minutes ;)\n",
            "\n",
            "\n",
            "\n",
            "Words from a complete stranger! Made my birthday even better :)\n",
            "\n",
            "\n",
            "\n",
            "First Cubs game ever! Wrigley field is gorgeous. This is perfect. Go Cubs Go!\n",
            "\n",
            "\n",
            "\n",
            "i no! i get another day off from skool due to the wonderful snow (: and THIS wakes me up...damn thing\n",
            "\n",
            "\n",
            "\n",
            "I'm coo... Jus at work hella tired r u ever in cali\n",
            "\n",
            "\n",
            "\n",
            "The new sundrop commercial ...hehe love at first sight\n",
            "\n",
            "\n",
            "\n",
            "we need to reconnect THIS WEEK\n",
            "\n",
            "\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "emExtLSKh1Th"
      },
      "source": [
        "### Preprocessing Pipeline\n",
        "1. Split the data by \\n charachter\n",
        "2. Remove leading and trailing spaces\n",
        "3. Remove Empty sentences\n",
        "4. Tokenise sentences using nltk tokenize"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "z5BNFEk-hk-b"
      },
      "source": [
        "#Returns list\n",
        "def preprocess_pipeline(textdata)-> 'list':\n",
        "  sentence = textdata.split('\\n')\n",
        "\n",
        "  sentence = [s.strip() for s in sentence]\n",
        "\n",
        "  sentence = [s for s in sentence if len(s) >0]\n",
        "\n",
        "  #Tokenize\n",
        "\n",
        "  tokenize=[]\n",
        "\n",
        "  for i in sentence:\n",
        "    i = i.lower()\n",
        "    token = nltk.word_tokenize(i)\n",
        "    tokenize.append(token)\n",
        "\n",
        "  #print(f'Tokenize format :{tokenize[0]}')\n",
        "  return tokenize\n",
        "\n",
        "\n",
        "tokenized_sentence = preprocess_pipeline(textdata)"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "U1AFOnLvlgk_"
      },
      "source": [
        "### Split into Train,Test datasets"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIySVfL8leET"
      },
      "source": [
        "Train,Test = train_test_split(tokenized_sentence,test_size=0.2,random_state = 42)\n",
        "\n",
        "Train, validation = train_test_split(Train, test_size=0.25, random_state=42)"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "CelFQJeemq-G"
      },
      "source": [
        "## 🧹Cleaning the data\n",
        "1. Creating the frequency dictonery\n",
        "2. Creating a Closed Vocabulary - We need to deal with Out-of-vocabulary words. This helps the model to handle words which are not present in the training corpus. \n",
        "3. Adding UNK tokens - In this function we'll add <unk> tokens, to those words which are not in the closed_vocabulary which we just made\n",
        "4. Final Cleaning Pipeline"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gPIczSZ_mpYy"
      },
      "source": [
        "# Frequency dictionery :\n",
        "\n",
        "def frequency_dictionery(sentences)->'dict':\n",
        "  word_count = {}\n",
        "\n",
        "  for sent in sentences:\n",
        "    for token in sent:\n",
        "\n",
        "      if (token not in word_count.keys()):\n",
        "        word_count[token] = 1\n",
        "\n",
        "      else:\n",
        "        word_count[token]+=1\n",
        "\n",
        "  return word_count\n"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YcPRf_b0q38X"
      },
      "source": [
        "'''\n",
        " This function creates a closed vocabulary containing only those words \n",
        " according to the count_threshold parameter.\n",
        "'''\n",
        "\n",
        "def closed_vocabulary(tokenized_sentence,count_threshold)-> 'list':\n",
        "\n",
        "  cv =[]\n",
        "  #Get the frequency dictionery from abpove function\n",
        "  word_count = frequency_dictionery(tokenized_sentence)\n",
        "\n",
        "  for word,count in word_count.items():\n",
        "    if (count >= count_threshold):\n",
        "      cv.append(word)\n",
        "\n",
        "  return cv\n"
      ],
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XhQ1LwaZtq-5"
      },
      "source": [
        "# Adding UNK tokens\n",
        "# This function returns a list\n",
        "def unk_tokenize(tokenized_sentences, vocabulary, unknown_token = \"<unk>\")-> 'list':\n",
        "\n",
        "  # Convert Vocabulary into a set\n",
        "  vocabulary = set(vocabulary)\n",
        "\n",
        "  # Create empty list for sentences\n",
        "  new_tokenized_sentences = []\n",
        "  \n",
        "  # Iterate over sentences\n",
        "  for sentence in tokenized_sentences:\n",
        "\n",
        "    # Iterate over sentence and add <unk> \n",
        "    # if the token is absent from the vocabulary\n",
        "    new_sentence = []\n",
        "    for token in sentence:\n",
        "      if token in vocabulary:\n",
        "        new_sentence.append(token)\n",
        "      else:\n",
        "        new_sentence.append(unknown_token)\n",
        "    \n",
        "    # Append sentece to the new list\n",
        "    new_tokenized_sentences.append(new_sentence)\n",
        "\n",
        "  return new_tokenized_sentences\n",
        "\n"
      ],
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WqVkBSDYvzR5"
      },
      "source": [
        "def final_cleansing_pipeline(train,test,count_threshold):\n",
        "\n",
        "  #Closed vocabulary\n",
        "  vocabulary = closed_vocabulary(train,count_threshold)\n",
        "\n",
        "  new_train = unk_tokenize(train,vocabulary)\n",
        "  new_test = unk_tokenize(test,vocabulary)\n",
        "\n",
        "  return new_test,new_train,vocabulary\n",
        "  \n"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wGZuVUDwU0TL"
      },
      "source": [
        "frequency = 6\n",
        "final_test,final_train,vocabulary = final_cleansing_pipeline(Train,Test,frequency)"
      ],
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "04cfGQAuVMAu"
      },
      "source": [
        "##  🔨 Building the model"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9jOkW8SyVK0T"
      },
      "source": [
        "# This function returns a mapping from n-grams to their frequency in the dataset.\n",
        "\n",
        "#Return dictionery\n",
        "def count_n_grams(data,n,start_token = \"<s>\", end_token = \"<e>\")-> 'dict':\n",
        "  ngrams ={}\n",
        "  for sentence in data:\n",
        "    # Append n start tokens and a single end token to the sentence\n",
        "    sentence = [start_token]*n + sentence + [end_token]\n",
        "    sentence = tuple(sentence)\n",
        "\n",
        "    length1 = len(sentence) if n==1 else len(sentence)-1\n",
        "\n",
        "    for i in range(length1):\n",
        "      # Get the n-grams\n",
        "      n_gram = sentence[i:i+n]\n",
        "\n",
        "      if n_gram in ngrams.keys():\n",
        "        ngrams[n_gram] +=1\n",
        "\n",
        "      else:\n",
        "        ngrams[n_gram]=1\n",
        "\n",
        "  return ngrams"
      ],
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9uS7R55jb4zk"
      },
      "source": [
        "This function calculates the priority for the next word given the prior n-gram.\n",
        "\n",
        "## K Smoothning\n",
        "if we come across a n-gram that wasn't in the training set, then we have our denominator as 0 which raises an error.<br>\n",
        "<br>\n",
        "Thus, we use k-smoothing, which adds a positive constant  k  to each numerator and  k×|V|  in the denominator, where  |V|  is the number of words in the vocabulary. This ensures any n-gram with zero count has the same probability of  1|V| "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rdeGAkvxeMp-"
      },
      "source": [
        "# Returns probablity of float\n",
        "def getProbablity_single_word(word,previous_ngram,ngCount,nplus1_gram_counts, vocabulary_size, k = 1.0) -> 'float':\n",
        "\n",
        "  previous_ngram = tuple(previous_ngram)\n",
        "\n",
        "  previous_ngram_count = ngCount[previous_ngram] if previous_ngram in ngCount else 0\n",
        "\n",
        "  #The denominator - We need to take care\n",
        "  denom = previous_ngram_count + k * vocabulary_size\n",
        "\n",
        "  nplus1_gram = previous_ngram + (word,)\n",
        "\n",
        "  # Calculating the nplus1_gram count .If it exist in frequency dict or it is 0 \n",
        "  nplus1_count =nplus1_gram_counts[nplus1_gram] if nplus1_gram in nplus1_gram_counts else 0\n",
        "\n",
        "  numerator = nplus1_count + k   #Numerator\n",
        "\n",
        "  #Final fraction\n",
        "  final_prob = (numerator/denom)\n",
        "  return final_prob\n"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KIet32FLnAdo"
      },
      "source": [
        "Loop over all the words in the vocabulary and then compute their probabilites using our getProbablity_single_word() fn."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dKz07Xv1m5HA"
      },
      "source": [
        "#Returns Dictionery\n",
        "def probs(previous_ngram,ngCount,np1Count,vocab,k=1.0) -> 'dict':\n",
        "  previous_ngram = tuple(previous_ngram)\n",
        "  vocab = vocab + [\"<e>\", \"<unk>\"]\n",
        "  vsize = len(vocab)\n",
        "  probablities ={}\n",
        "\n",
        "  for words in vocab:\n",
        "    probab = getProbablity_single_word(words,previous_ngram,ngCount,np1Count,vsize,k=k)\n",
        "\n",
        "    #Mapping: word->probablity\n",
        "    probablities[words] = probab\n",
        "    \n",
        "  return probablities"
      ],
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hcdc3I8ryZbw"
      },
      "source": [
        "## The Main System"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "W04bfyRjzEM3"
      },
      "source": [
        "def auto_complete(previous_tokens, n_gram_counts, nplus1_gram_counts, vocabulary, k=1.0, start_with=None):\n",
        "\n",
        "    n = len(list(n_gram_counts.keys())[0]) \n",
        "    previous_n_gram = previous_tokens[-n:]\n",
        "    probabilities = probs(previous_n_gram,n_gram_counts, nplus1_gram_counts,vocabulary, k=k)\n",
        "    suggestion = None\n",
        "    max_prob = 0\n",
        "\n",
        "    # Iterate over all words and probabilites, returning the max.\n",
        "    # We also add a check if the start_with parameter is provided\n",
        "    for word, prob in probabilities.items():\n",
        "        \n",
        "        if start_with != None: \n",
        "            \n",
        "            if not word.startswith(start_with):\n",
        "                continue \n",
        "\n",
        "        if prob > max_prob: \n",
        "\n",
        "            suggestion = word\n",
        "            max_prob = prob\n",
        "\n",
        "    return suggestion, max_prob"
      ],
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xT1xX0o7yVme"
      },
      "source": [
        "## Getting multiple suggestions"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tH7qg5wbzMv2"
      },
      "source": [
        "def multiple_suggestion(previous_token,ngram_clist,vocab,k=1.0,start_with=None):\n",
        "\n",
        "  cnt = len(ngram_clist)\n",
        "  suggest =[]\n",
        "\n",
        "  for i in range(cnt-1):\n",
        "    ngcount = ngram_clist[i]\n",
        "    np1_gram_count = ngram_clist[i+1]\n",
        "\n",
        "    suggestion = auto_complete(previous_token,ngcount,np1_gram_count,vocab,k=k,start_with=start_with)\n",
        "    suggest.append(suggestion)\n",
        "    \n",
        "  return suggest\n"
      ],
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qh9jSPuF4swd"
      },
      "source": [
        "## ✔️ Almost done!!"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oOiX3cnR4zif"
      },
      "source": [
        "ngram_clist = []\n",
        "for i in range(1,6):\n",
        "  n_models = count_n_grams(final_train,i)\n",
        "  ngram_clist.append(n_models)\n",
        "  "
      ],
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 87
        },
        "id": "mj9Rby4S66U7",
        "outputId": "7c785c24-7bdb-4cc6-d0fb-7787d5206411"
      },
      "source": [
        "previous_tokens = [\"i\",\"was\",\"about\",\"to\"]\n",
        "suggestions = multiple_suggestion(previous_tokens,ngram_clist,vocabulary,k=1.0)\n",
        "display(suggestions)"
      ],
      "execution_count": 32,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "[('<unk>', 0.04396425310571895),\n",
              " ('go', 0.002950452741886255),\n",
              " ('give', 0.0002078353943676608),\n",
              " ('give', 0.0002079002079002079)]"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "X0F-yugoihAI"
      },
      "source": [
        "## 📋Exporting them!!\n",
        "We are not going to train model everytime.So we are exporting the vocabulary as text and we will use these as reference"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NM1W_boBjCjn"
      },
      "source": [
        "with open(\"vocabulary.txt\",\"wb\") as f:\n",
        "  pickle.dump(vocabulary,f)"
      ],
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QHPIK6Ejj579"
      },
      "source": [
        "# Getting n-gram counts\n",
        "with open(\"ngram_counts.txt\", 'wb') as f:\n",
        "    pickle.dump(ngram_clist, f)"
      ],
      "execution_count": 36,
      "outputs": []
    }
  ]
}