12.3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "view-in-github"
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/udlbook/udlbook/blob/main/Notebooks/Chap12/12_3_Tokenization.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "t9vk9Elugvmi"
   },
   "source": [
    "# **Notebook 12.3: Tokenization**\n",
    "\n",
    "This notebook builds set of tokens from a text string as in figure 12.8 of the book.\n",
    "\n",
    "Work through the cells below, running each cell in turn. In various places you will see the words \"TO DO\". Follow the instructions at these places and make predictions about what is going to happen or write code to complete the functions.\n",
    "\n",
    "I adapted this code from *SOMEWHERE*.  If anyone recognizes it, can you let me know and I will give the proper attribution or rewrite if the license is not permissive.\n",
    "\n",
    "Contact me at udlbookmail@gmail.com if you find any mistakes or have any suggestions.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "3_WkaFO3OfLi"
   },
   "outputs": [],
   "source": [
    "import re, collections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "tVZVuauIXmJk"
   },
   "outputs": [],
   "source": [
    "text = \"a sailor went to sea sea sea \"+\\\n",
    "                  \"to see what he could see see see \"+\\\n",
    "                  \"but all that he could see see see \"+\\\n",
    "                  \"was the bottom of the deep blue sea sea sea\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "fF2RBrouWV5w"
   },
   "source": [
    "Tokenize the input sentence To begin with the tokens are the individual letters and the </w> whitespace token. So, we represent each word in terms of these tokens with spaces between the tokens to delineate them.\n",
    "\n",
    "The tokenized text is stored in a structure that represents each word as tokens together with the count of how often that word occurs.  We'll call this the *vocabulary*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "OfvXkLSARk4_"
   },
   "outputs": [],
   "source": [
    "def initialize_vocabulary(text):\n",
    "  vocab = collections.defaultdict(int)\n",
    "  words = text.strip().split()\n",
    "  for word in words:\n",
    "      vocab[' '.join(list(word)) + ' </w>'] += 1\n",
    "  return vocab"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "aydmNqaoOpSm"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vocabulary: defaultdict(<class 'int'>, {'a </w>': 1, 's a i l o r </w>': 1, 'w e n t </w>': 1, 't o </w>': 2, 's e a </w>': 6, 's e e </w>': 7, 'w h a t </w>': 1, 'h e </w>': 2, 'c o u l d </w>': 2, 'b u t </w>': 1, 'a l l </w>': 1, 't h a t </w>': 1, 'w a s </w>': 1, 't h e </w>': 2, 'b o t t o m </w>': 1, 'o f </w>': 1, 'd e e p </w>': 1, 'b l u e </w>': 1})\n",
      "Size of vocabulary: 18\n"
     ]
    }
   ],
   "source": [
    "vocab = initialize_vocabulary(text)\n",
    "print('Vocabulary: {}'.format(vocab))\n",
    "print('Size of vocabulary: {}'.format(len(vocab)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "fJAiCjphWsI9"
   },
   "source": [
    "Find all the tokens in the current vocabulary and their frequencies"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "qYi6F_K3RYsW"
   },
   "outputs": [],
   "source": [
    "def get_tokens_and_frequencies(vocab):\n",
    "  tokens = collections.defaultdict(int)\n",
    "  for word, freq in vocab.items():\n",
    "      word_tokens = word.split()\n",
    "      for token in word_tokens:\n",
    "          tokens[token] += freq\n",
    "  return tokens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "Y4LCVGnvXIwp"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tokens: defaultdict(<class 'int'>, {'a': 12, '</w>': 33, 's': 15, 'i': 1, 'l': 6, 'o': 8, 'r': 1, 'w': 3, 'e': 28, 'n': 1, 't': 11, 'h': 6, 'c': 2, 'u': 4, 'd': 3, 'b': 3, 'm': 1, 'f': 1, 'p': 1})\n",
      "Number of tokens: 19\n"
     ]
    }
   ],
   "source": [
    "tokens = get_tokens_and_frequencies(vocab)\n",
    "print('Tokens: {}'.format(tokens))\n",
    "print('Number of tokens: {}'.format(len(tokens)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "_-Rh1mD_Ww3b"
   },
   "source": [
    "Find each pair of adjacent tokens in the vocabulary\n",
    "and count them.  We will subsequently merge the most frequently occurring pair."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "id": "OqJTB3UFYubH"
   },
   "outputs": [],
   "source": [
    "def get_pairs_and_counts(vocab):\n",
    "    pairs = collections.defaultdict(int)\n",
    "    for word, freq in vocab.items():\n",
    "        symbols = word.split()\n",
    "        for i in range(len(symbols)-1):\n",
    "            pairs[symbols[i],symbols[i+1]] += freq\n",
    "    return pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "id": "d-zm0JBcZSjS"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pairs: defaultdict(<class 'int'>, {('a', '</w>'): 7, ('s', 'a'): 1, ('a', 'i'): 1, ('i', 'l'): 1, ('l', 'o'): 1, ('o', 'r'): 1, ('r', '</w>'): 1, ('w', 'e'): 1, ('e', 'n'): 1, ('n', 't'): 1, ('t', '</w>'): 4, ('t', 'o'): 3, ('o', '</w>'): 2, ('s', 'e'): 13, ('e', 'a'): 6, ('e', 'e'): 8, ('e', '</w>'): 12, ('w', 'h'): 1, ('h', 'a'): 2, ('a', 't'): 2, ('h', 'e'): 4, ('c', 'o'): 2, ('o', 'u'): 2, ('u', 'l'): 2, ('l', 'd'): 2, ('d', '</w>'): 2, ('b', 'u'): 1, ('u', 't'): 1, ('a', 'l'): 1, ('l', 'l'): 1, ('l', '</w>'): 1, ('t', 'h'): 3, ('w', 'a'): 1, ('a', 's'): 1, ('s', '</w>'): 1, ('b', 'o'): 1, ('o', 't'): 1, ('t', 't'): 1, ('o', 'm'): 1, ('m', '</w>'): 1, ('o', 'f'): 1, ('f', '</w>'): 1, ('d', 'e'): 1, ('e', 'p'): 1, ('p', '</w>'): 1, ('b', 'l'): 1, ('l', 'u'): 1, ('u', 'e'): 1})\n",
      "Number of distinct pairs: 48\n",
      "Most frequent pair: ('s', 'e')\n"
     ]
    }
   ],
   "source": [
    "pairs = get_pairs_and_counts(vocab)\n",
    "print('Pairs: {}'.format(pairs))\n",
    "print('Number of distinct pairs: {}'.format(len(pairs)))\n",
    "\n",
    "most_frequent_pair = max(pairs, key=pairs.get)\n",
    "print('Most frequent pair: {}'.format(most_frequent_pair))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "pcborzqIXQFS"
   },
   "source": [
    "Merge the instances of the best pair in the vocabulary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "id": "xQI6NALdWQZX"
   },
   "outputs": [],
   "source": [
    "def merge_pair_in_vocabulary(pair, vocab_in):\n",
    "    vocab_out = {}\n",
    "    bigram = re.escape(' '.join(pair))\n",
    "    p = re.compile(r'(?<!\\S)' + bigram + r'(?!\\S)')\n",
    "    for word in vocab_in:\n",
    "        word_out = p.sub(''.join(pair), word)\n",
    "        vocab_out[word_out] = vocab_in[word]\n",
    "    return vocab_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "id": "TRYeBZI3ZULu"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vocabulary: {'a </w>': 1, 's a i l o r </w>': 1, 'w e n t </w>': 1, 't o </w>': 2, 'se a </w>': 6, 'se e </w>': 7, 'w h a t </w>': 1, 'h e </w>': 2, 'c o u l d </w>': 2, 'b u t </w>': 1, 'a l l </w>': 1, 't h a t </w>': 1, 'w a s </w>': 1, 't h e </w>': 2, 'b o t t o m </w>': 1, 'o f </w>': 1, 'd e e p </w>': 1, 'b l u e </w>': 1}\n",
      "Size of vocabulary: 18\n"
     ]
    }
   ],
   "source": [
    "vocab = merge_pair_in_vocabulary(most_frequent_pair, vocab)\n",
    "print('Vocabulary: {}'.format(vocab))\n",
    "print('Size of vocabulary: {}'.format(len(vocab)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "bkhUx3GeXwba"
   },
   "source": [
    "Update the tokens, which now include the best token 'se'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "id": "Fqj-vQWeXxQi"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tokens: defaultdict(<class 'int'>, {'a': 12, '</w>': 33, 's': 2, 'i': 1, 'l': 6, 'o': 8, 'r': 1, 'w': 3, 'e': 15, 'n': 1, 't': 11, 'se': 13, 'h': 6, 'c': 2, 'u': 4, 'd': 3, 'b': 3, 'm': 1, 'f': 1, 'p': 1})\n",
      "Number of tokens: 20\n"
     ]
    }
   ],
   "source": [
    "tokens = get_tokens_and_frequencies(vocab)\n",
    "print('Tokens: {}'.format(tokens))\n",
    "print('Number of tokens: {}'.format(len(tokens)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "K_hKp2kSXXS1"
   },
   "source": [
    "Now let's write the full tokenization routine"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "id": "U_1SkQRGQ8f3"
   },
   "outputs": [],
   "source": [
    "# TODO -- write this routine by filling in this missing parts,\n",
    "# calling the above routines\n",
    "def tokenize(text, num_merges):\n",
    "  # Initialize the vocabulary from the input text\n",
    "  vocab = initialize_vocabulary(text)\n",
    "\n",
    "  for i in range(num_merges):\n",
    "    # Find the tokens and how often they occur in the vocabulary\n",
    "    tokens = get_tokens_and_frequencies(vocab)\n",
    "\n",
    "    # Find the pairs of adjacent tokens and their counts\n",
    "    pairs = get_pairs_and_counts(vocab)\n",
    "\n",
    "    # Find the most frequent pair\n",
    "    most_frequent_pair = max(pairs, key=pairs.get)\n",
    "    print('Most frequent pair: {}'.format(most_frequent_pair))\n",
    "\n",
    "    # Merge the code in the vocabulary\n",
    "    vocab = merge_pair_in_vocabulary(most_frequent_pair, vocab)\n",
    "\n",
    "  # Find the tokens and how often they occur in the vocabulary one last time\n",
    "  tokens = get_tokens_and_frequencies(vocab)\n",
    "\n",
    "  return tokens, vocab"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "id": "w0EkHTrER_-I"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Most frequent pair: ('s', 'e')\n",
      "Most frequent pair: ('e', '</w>')\n",
      "Most frequent pair: ('a', '</w>')\n",
      "Most frequent pair: ('se', 'e</w>')\n",
      "Most frequent pair: ('se', 'a</w>')\n",
      "Most frequent pair: ('t', '</w>')\n",
      "Most frequent pair: ('h', 'e</w>')\n",
      "Most frequent pair: ('t', 'o')\n",
      "Most frequent pair: ('to', '</w>')\n",
      "Most frequent pair: ('h', 'a')\n",
      "Most frequent pair: ('ha', 't</w>')\n",
      "Most frequent pair: ('c', 'o')\n",
      "Most frequent pair: ('co', 'u')\n",
      "Most frequent pair: ('cou', 'l')\n",
      "Most frequent pair: ('coul', 'd')\n",
      "Most frequent pair: ('could', '</w>')\n",
      "Most frequent pair: ('t', 'he</w>')\n",
      "Most frequent pair: ('s', 'a')\n",
      "Most frequent pair: ('sa', 'i')\n",
      "Most frequent pair: ('sai', 'l')\n",
      "Most frequent pair: ('sail', 'o')\n",
      "Most frequent pair: ('sailo', 'r')\n"
     ]
    }
   ],
   "source": [
    "tokens, vocab = tokenize(text, num_merges=22)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "id": "moqDtTzIb-NG"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tokens: defaultdict(<class 'int'>, {'a</w>': 1, 'sailor': 1, '</w>': 6, 'w': 3, 'e': 3, 'n': 1, 't</w>': 2, 'to</w>': 2, 'sea</w>': 6, 'see</w>': 7, 'hat</w>': 2, 'he</w>': 2, 'could</w>': 2, 'b': 3, 'u': 2, 'a': 2, 'l': 3, 't': 2, 's': 1, 'the</w>': 2, 'o': 2, 'to': 1, 'm': 1, 'f': 1, 'd': 1, 'p': 1, 'e</w>': 1})\n",
      "Number of tokens: 27\n",
      "Vocabulary: {'a</w>': 1, 'sailor </w>': 1, 'w e n t</w>': 1, 'to</w>': 2, 'sea</w>': 6, 'see</w>': 7, 'w hat</w>': 1, 'he</w>': 2, 'could</w>': 2, 'b u t</w>': 1, 'a l l </w>': 1, 't hat</w>': 1, 'w a s </w>': 1, 'the</w>': 2, 'b o t to m </w>': 1, 'o f </w>': 1, 'd e e p </w>': 1, 'b l u e</w>': 1}\n",
      "Size of vocabulary: 18\n"
     ]
    }
   ],
   "source": [
    "print('Tokens: {}'.format(tokens))\n",
    "print('Number of tokens: {}'.format(len(tokens)))\n",
    "print('Vocabulary: {}'.format(vocab))\n",
    "print('Size of vocabulary: {}'.format(len(vocab)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "jOW_HJtMdAxd"
   },
   "source": [
    "TODO - Consider the input text:\n",
    "\n",
    "\"How much wood could a woodchuck chuck if a woodchuck could chuck wood\"\n",
    "\n",
    "How many tokens will there be initially and what will they be?\n",
    "How many tokens will there be if we run the tokenization routine for the maximum number of iterations (merges)?\n",
    "\n",
    "When you've made your predictions, run the code and see if you are correct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Most frequent pair: ('u', 'c')\n",
      "Most frequent pair: ('w', 'o')\n",
      "Most frequent pair: ('wo', 'o')\n",
      "Most frequent pair: ('woo', 'd')\n",
      "Most frequent pair: ('c', 'h')\n",
      "Most frequent pair: ('ch', 'uc')\n",
      "Most frequent pair: ('chuc', 'k')\n",
      "Most frequent pair: ('chuck', '</w>')\n",
      "Most frequent pair: ('wood', '</w>')\n",
      "Most frequent pair: ('c', 'o')\n",
      "Most frequent pair: ('co', 'u')\n",
      "Most frequent pair: ('cou', 'l')\n",
      "Most frequent pair: ('coul', 'd')\n",
      "Most frequent pair: ('could', '</w>')\n",
      "Most frequent pair: ('a', '</w>')\n",
      "Most frequent pair: ('wood', 'chuck</w>')\n",
      "Most frequent pair: ('H', 'o')\n",
      "Most frequent pair: ('Ho', 'w')\n",
      "Most frequent pair: ('How', '</w>')\n",
      "Most frequent pair: ('m', 'uc')\n",
      "Most frequent pair: ('muc', 'h')\n",
      "Most frequent pair: ('much', '</w>')\n"
     ]
    }
   ],
   "source": [
    "text = 'How much wood could a woodchuck chuck if a woodchuck could chuck wood'\n",
    "tokens, vocab = tokenize(text, num_merges=22)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tokens: defaultdict(<class 'int'>, {'How</w>': 1, 'much</w>': 1, 'wood</w>': 2, 'could</w>': 2, 'a</w>': 2, 'woodchuck</w>': 2, 'chuck</w>': 2, 'i': 1, 'f': 1, '</w>': 1})\n",
      "Number of tokens: 10\n",
      "Vocabulary: {'How</w>': 1, 'much</w>': 1, 'wood</w>': 2, 'could</w>': 2, 'a</w>': 2, 'woodchuck</w>': 2, 'chuck</w>': 2, 'i f </w>': 1}\n",
      "Size of vocabulary: 8\n"
     ]
    }
   ],
   "source": [
    "print('Tokens: {}'.format(tokens))\n",
    "print('Number of tokens: {}'.format(len(tokens)))\n",
    "print('Vocabulary: {}'.format(vocab))\n",
    "print('Size of vocabulary: {}'.format(len(vocab)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyP0/KodWM9Dtr2x+8MdXXH1",
   "include_colab_link": true,
   "provenance": []
  },
  "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}