{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tokenization\n",
    "## What goes into the LLM?\n",
    "\n",
    "**Lecturer:** Vegard H. Larsen\n",
    "\n",
    "---\n",
    "\n",
    " ## Why should we care about tokenization?\n",
    "\n",
    "- Tokenization is the process of breaking a text into words, phrases, symbols, or other meaningful elements.\n",
    "- It is the first step in many natural language processing tasks.\n",
    "- It is a crucial step in text processing, as it helps to understand the text and extract useful information from it.\n",
    "\n",
    "### Challenges with tokenization \n",
    "- Why does LLMs struggle to spell a word? \n",
    "    - The LLM does not observe the letters in the word, but rather the tokens.\n",
    "- Why is LLMs bad as simple arithmetic? \n",
    "    - Numbers are tokenized as words, making it difficult to perform arithmetic operations.\n",
    "- Why is LLMs worse at non-English languages?\n",
    "    - Tokenization is language-dependent, and the same text can be tokenized differently in different languages.\n",
    "- Early LLMs struggled with writing code because of the tokenization of code.\n",
    "    - Code is tokenized as words, making it difficult to understand the code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stemming\n",
    "\n",
    "Stemming is a process in Natural Language Processing (NLP) that involves reducing words to their root or base form, which may not necessarily be a valid word in the language. The primary goal of stemming is to group words with similar meanings together by stripping affixes (e.g., -ing, -ed, -s) to facilitate text normalization.\n",
    "\n",
    "For example, the words \"running,\" \"runner,\" and \"ran\" can all be reduced to the root \"run\" through stemming. This helps in improving text processing tasks by reducing the  of data and enabling algorithms to recognize and treat different variations of a word as a single item.\n",
    "\n",
    "Common stemming algorithms include the **Porter Stemmer** and **Snowball Stemmer**, which use rules to remove suffixes and achieve the desired base form."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original: running -> Stemmed: run\n",
      "Original: runner -> Stemmed: runner\n",
      "Original: ran -> Stemmed: ran\n",
      "Original: runs -> Stemmed: run\n",
      "Original: easily -> Stemmed: easili\n",
      "Original: fairly -> Stemmed: fairli\n"
     ]
    }
   ],
   "source": [
    "# Import the necessary module from nltk\n",
    "from nltk.stem import PorterStemmer\n",
    "\n",
    "# Create an instance of the Porter Stemmer\n",
    "stemmer = PorterStemmer()\n",
    "\n",
    "# List of example words to be stemmed\n",
    "words = [\"running\", \"runner\", \"ran\", \"runs\", \"easily\", \"fairly\"]\n",
    "\n",
    "# Stem each word and print the result\n",
    "for word in words:\n",
    "    stemmed_word = stemmer.stem(word)\n",
    "    print(f\"Original: {word} -> Stemmed: {stemmed_word}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original: running -> Stemmed: run\n",
      "Original: runner -> Stemmed: runner\n",
      "Original: ran -> Stemmed: run\n",
      "Original: runs -> Stemmed: run\n",
      "Original: easily -> Stemmed: easili\n",
      "Original: fairly -> Stemmed: fairli\n"
     ]
    }
   ],
   "source": [
    "# Create an instance of the Porter Stemmer\n",
    "stemmer = PorterStemmer()\n",
    "\n",
    "# Dictionary of exceptions for irregular words\n",
    "exceptions = {\n",
    "    \"ran\": \"run\"\n",
    "}\n",
    "\n",
    "def custom_stemmer(word):\n",
    "    # Check if the word is in the exceptions dictionary\n",
    "    if word in exceptions:\n",
    "        return exceptions[word]\n",
    "    # Otherwise, use the Porter Stemmer\n",
    "    return stemmer.stem(word)\n",
    "\n",
    "# Stem each word and print the result\n",
    "for word in words:\n",
    "    stemmed_word = custom_stemmer(word)\n",
    "    print(f\"Original: {word} -> Stemmed: {stemmed_word}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tokenization\n",
    "\n",
    "\n",
    "**`tiktoken`**\n",
    "\n",
    "A fast and efficient tokenizer library created by OpenAI, primarily designed for tokenizing text data used in large language models (LLMs), such as GPT. The tokenizer's main function is to split input text into manageable sub-word units called tokens. Tokenization is crucial in NLP for handling text input because models operate on tokens rather than raw text.\n",
    "\n",
    "Play with a open web app for tokenization: [tiktoken](https://tiktokenizer.vercel.app)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unicode\n",
    "\n",
    "- Unicode is a standard for encoding characters in different languages.\n",
    "- It is a superset of ASCII and includes characters from all languages."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "97"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord('a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "128077"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ord('👍')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'r'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chr(114)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'👐'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chr(128080)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[104, 101, 108, 108, 111, 32, 230, 248, 229]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[ord(x) for x in 'hello æøå']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### UTF-8\n",
    "\n",
    "- UTF-8 is a variable-width character encoding that can represent every character in the Unicode character set.\n",
    "\n",
    "- It is backward compatible with ASCII and is the preferred encoding for web pages.\n",
    "\n",
    "- UTF-8 uses 8-bit code units, and it can encode any Unicode character using 1 to 4 bytes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[104, 101, 108, 108, 111, 32, 195, 166, 195, 184, 195, 165]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list('hello æøå'.encode('utf-8'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[195, 165]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list('å'.encode('utf-8'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[240, 159, 145, 141]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list('👍'.encode('utf-8'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Byte-pair encoding\n",
    "\n",
    "Byte-pair encoding (BPE) is a simple yet effective method used in natural language processing for text tokenization. It helps in breaking down words into sub-units, allowing for a more flexible representation of vocabulary and better handling of rare or unseen words.\n",
    "\n",
    "Here's an easy introduction:\n",
    "\n",
    "### What is Byte-Pair Encoding?\n",
    "Byte-pair encoding is a data compression algorithm that is adapted for tokenizing text in NLP tasks. It helps manage the trade-off between having many unique words and breaking them into meaningful sub-units. This technique is widely used in modern language models, including those in machine learning, because it strikes a balance between word-based and character-based tokenization.\n",
    "\n",
    "### How Does BPE Work?\n",
    "1. **Initialization**: Start with the vocabulary as individual characters of the text. For instance, for \"hello world,\" the initial tokens would be ['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd'].\n",
    "\n",
    "2. **Counting Pair Frequencies**: Identify pairs of consecutive characters and count their frequencies in the text. For example, in \"hello,\" the pairs would be 'he', 'el', 'll', and 'lo'.\n",
    "\n",
    "3. **Merging Pairs**: Combine the most frequent pair into a single token. If 'el' is the most frequent, it becomes one token, reducing the number of individual tokens. Repeat this step iteratively.\n",
    "\n",
    "4. **Updating the Vocabulary**: The text is scanned and updated after each merge step. New merged tokens replace their original pairs in the text.\n",
    "\n",
    "5. **Iteration**: The process repeats until a predefined number of unique subwords are created or a desired vocabulary size is reached.\n",
    "\n",
    "### Example of BPE in Action:\n",
    "Consider the word list: ['low', 'lower', 'newest', 'widest'].\n",
    "- Initial tokens are individual letters: ['l', 'o', 'w', 'e', 'r', 'n', 'e', 'w', 's', 't', 'i', 'd'].\n",
    "- Pairs like 'lo', 'ow', 'we', etc., are identified.\n",
    "- The most common pair is merged (e.g., 'l''o' → 'lo'), updating the list and reducing token length.\n",
    "- This continues until achieving efficient subword tokenization, such as ['low', 'er', 'new', 'est', 'wide'].\n",
    "\n",
    "### Why Use BPE?\n",
    "- **Efficient Vocabulary Size**: Helps manage a balance between large vocabulary and single character tokens.\n",
    "- **Handling Rare Words**: Splits infrequent or unknown words into subunits that can still be interpreted meaningfully.\n",
    "- **Adaptability**: Can dynamically adapt to various languages and complex words.\n",
    "\n",
    "### Applications\n",
    "BPE is integral to tokenization in popular NLP models like GPT and BERT, allowing these systems to represent words as a sequence of subword tokens, improving their ability to learn and generalize from training data.\n",
    "\n",
    "This simple approach allows NLP models to better handle diverse and complex language structures without requiring enormous vocabularies, leading to more efficient and flexible text processing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "corpus = [\"low\", \"lower\", \"newest\", \"widest\"]\n",
    "words = [list(w) + [\"</w>\"] for w in corpus]\n",
    "\n",
    "def merge_step(words):\n",
    "    \"\"\"Find the most frequent adjacent pair and merge it everywhere.\"\"\"\n",
    "    pairs = Counter()\n",
    "    for w in words:\n",
    "        for a, b in zip(w, w[1:]):\n",
    "            pairs[(a, b)] += 1\n",
    "    if not pairs:\n",
    "        return words, None\n",
    "    (a, b), _ = pairs.most_common(1)[0]\n",
    "    out = []\n",
    "    for w in words:\n",
    "        merged, i = [], 0\n",
    "        while i < len(w):\n",
    "            if i < len(w) - 1 and w[i] == a and w[i + 1] == b:\n",
    "                merged.append(a + b); i += 2\n",
    "            else:\n",
    "                merged.append(w[i]); i += 1\n",
    "        out.append(merged)\n",
    "    return out, (a, b)\n",
    "\n",
    "for step in range(6):\n",
    "    words, pair = merge_step(words)\n",
    "    print(f\"merge {step+1}: {pair!s:18s} -> \" + \" | \".join(\" \".join(w) for w in words))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A real tokenizer: tiktoken\n",
    "\n",
    "The BPE above is a toy — real models train millions of merges on terabytes of\n",
    "text. `tiktoken` (OpenAI) ships the resulting vocabularies, so we can see\n",
    "exactly what a GPT-4o-class model sees (`pip install tiktoken` first).\n",
    "\n",
    "Note the lecture's four challenges appearing live: Norwegian splits into more\n",
    "pieces than English, the number is chopped into `123|45`, and `strawberry`\n",
    "becomes three opaque chunks — which is why models can't count its r's."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# pip install tiktoken\n",
    "import tiktoken\n",
    "\n",
    "enc = tiktoken.get_encoding(\"o200k_base\")   # the GPT-4o-family encoding, ~200k tokens\n",
    "print(\"vocabulary size:\", enc.n_vocab)\n",
    "\n",
    "examples = [\n",
    "    \"The market fell sharply yesterday.\",\n",
    "    \"Markedet falt kraftig i går.\",\n",
    "    \"12345.67 + 89.01\",\n",
    "    \"strawberry\",\n",
    "]\n",
    "for s in examples:\n",
    "    toks = enc.encode(s)\n",
    "    print(f\"{len(toks):2d} tokens: \" + \" | \".join(enc.decode([t]) for t in toks))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pytorch",
   "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.11.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}