Learning_Resources/notes/Tokenization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tokenization\n",
    "\n",
    "*Unfinished...*\n",
    "\n",
    "There are many types of tokens from raw text: characters, words, subwords, sentences, etc.. In this note, we mainly focus on **Word Tokenization/ Subword Tokenization**. The main purpose of word tokenization is that we need to <u> convert raw text into data that can be processed by model </u>. \n",
    "\n",
    "\n",
    "Comparisons among different tokenization strategies for NLP models:\n",
    "\n",
    "- character tokenization:\n",
    "    - pros: easy; small vocabulary (low dimension)\n",
    "    - cons: long sequence\n",
    "- subword tokenization:\n",
    "    - trade-off 🤗\n",
    "- word tokenization:\n",
    "    - pros: easy; short sequence\n",
    "    - cons: large vocabulary (high dimension, out-of-vocabulary)\n",
    "\n",
    "## Table of Contents\n",
    "\n",
    "- [Pre-requirement Knowledge](#pre-requirement-knowledge)\n",
    "    - [Character Encoding](#character-encoding)\n",
    "    - [Unicode Normalization](#unicode-normalization)\n",
    "- [Rule-based Tokenization](#rule-based-tokenization)\n",
    "    - [Basic Rules](#1-basic-rules-whitespace-blankspace-or-self-defined-rules)\n",
    "    - [Advanced Rules](#2-advanced-rules-penn-treebank-ptb-tweet-mwe-spacy)\n",
    "- [Statistics-based Tokenization](#statistic-based-tokenization)\n",
    "    - [Byte-Pair Encoding (BPE)](#byte-pair-encoding-bpe)\n",
    "        - [Byte-level BPE (BBPE)](#byte-level-bpe-bbpe)\n",
    "    - [WordPiece](#wordpiece)\n",
    "    - [Unigram](#unigram)\n",
    "    - [SentencePiece](#sentencepiece)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pre-requirement Knowledge\n",
    "\n",
    "### Character Encoding\n",
    "\n",
    "**Basic Concepts:**\n",
    "- Character Set\n",
    "- Coded Character Set: convert Character into Code Point (numerical value that maps to a specific character). \n",
    "    - the Unicode Standard, ISO/IEC 8859-1 (Latin-1), Windows Code Page 1252\n",
    "- Character Encoding Form: convert Code Point into Code Unit (particular sequences of bits). \n",
    "    - fixed width: ASCII (7-bit), EASCII (8-bit), ISO 8859-1 (8-bit), Windows CP 1252 (8-bit),  UTF-32/USC-4 (32-bit)\n",
    "    - variable width:  UTF-8, UTF-16\n",
    "- Character Encoding Scheme: convert Code Unit into Byte. \n",
    "    - UTF-16 BE (big endian)\n",
    "\n",
    "**Encoding Procedure:**\n",
    "\n",
    "Character -> Code Point -> Code Unit -> Bytes \n",
    "\n",
    "`'A'` --(Unicode)-> `U+0041` --(UTF-16)-> `0x0041` --(UTF-16 LE)-> `0x41 0x00`\n",
    "\n",
    "`'A'` --(ASCII)-> `0x41`\n",
    "\n",
    "### Unicode Normalization\n",
    "\n",
    "**Problems:** two types of equivalence\n",
    "- Canonical equivalence: different Unicode have same visual appearance\n",
    "    - Combining sequence: Ç\t↔\tC+◌̧\n",
    "    - Ordering of conbining marks: q+◌̇+◌̣\t↔\tq+◌̣+◌̇\n",
    "    - Hangual & conjoining jamo: 가\t↔\tᄀ +ᅡ\n",
    "    - Singleton equivalence: Ω\t↔\tΩ\n",
    "- Compatibility equivalence: same abstract chracter have distinct visual appearances\n",
    "    - Font variants: ℌ\t→\tH\n",
    "    - Linebreaking differences: [NBSP]\t→\t[SPACE]\n",
    "    - Positional variant forms: ﻉ\t→\t‌ع‌\n",
    "    - Circled variants: ①\t→\t1\n",
    "    - Width variants: ｶ\t→\tカ\n",
    "    - Rotated variants: ︷\t→\t{\n",
    "    - Superscripts/subscripts: i⁹\t→\ti9\n",
    "    - Squared characters: ㌀\t→\tアパート\n",
    "    - Fractions: ¼\t→\t1/4\n",
    "    - Other: ǆ\t→\tdž\n",
    "\n",
    "**Solutions:** Unicode Normalization: determin whether any two Unicode strings are equivalent to each other.\n",
    "- Normalization Form D (NFD): Canonical Decomposition. \n",
    "- Normalization Form C (NFC): Canonical Decomposition, followed by Canonical Composition\n",
    "- Normalization Form KD (NFKD): Compatibility Decomposition\n",
    "- Normalization Form KC (NFKC): Compatibility Decomposition, followed by Compatibility Composition\n",
    "\n",
    "<img style=\"left;\" src=\"assets/Norm.jpg\" width=\"500\">\n",
    "\n",
    "References\n",
    "- [Wikipedia](https://www.wikipedia.org/)\n",
    "- [UNICODE NORMALIZATION FORMS](https://www.unicode.org/reports/tr15/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "## Rule-based Tokenization\n",
    "\n",
    "tools: NLTK, spaCy, TextBlob, Gensim, AllenNLP, Keras, Transformers \n",
    "\n",
    "### 1. Basic Rules: whitespace, blankspace, or self-defined rules"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['A', 'nice', 'day', ',', 'Let', \"'s\", 'do', 'tokenization', 'at', 'U', '.K.!']  (RE)\n",
      "['A', 'nice', 'day,', \"Let's\", 'do', 'tokenization', 'at', 'U.K.!']  (Whitespace)\n",
      "[\"A nice day, Let's do tokenization at U.K.!\"]  (Blankline)\n",
      "['A', 'nice', 'day', ',', 'Let', \"'\", 's', 'do', 'tokenization', 'at', 'U', '.', 'K', '.!']  (Word+Punctuation)\n"
     ]
    }
   ],
   "source": [
    "from nltk.tokenize import  RegexpTokenizer, WhitespaceTokenizer, BlanklineTokenizer, WordPunctTokenizer\n",
    "text = \"A nice day, Let's do tokenization at U.K.!\"\n",
    "re_tokenizer = RegexpTokenizer(r'\\w+|\\$[\\d\\.]+|\\S+')\n",
    "ws_tokenizer = WhitespaceTokenizer() # the same as RegexpTokenizer(r'\\s+', gaps=True)\n",
    "bs_tokenizer = BlanklineTokenizer() # the same as RegexpTokenizer(r'\\s*\\n\\s*\\n\\s*', gaps=True)\n",
    "wp_tokenizer = WordPunctTokenizer() # the same as RegexpTokenizer(r'\\w+|[^\\w\\s]+', gaps=True)\n",
    "print(re_tokenizer.tokenize(text), \" (RE)\")\n",
    "print(ws_tokenizer.tokenize(text), \" (Whitespace)\")\n",
    "print(bs_tokenizer.tokenize(text), \" (Blankline)\")\n",
    "print(wp_tokenizer.tokenize(text), \" (Word+Punctuation)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Advanced Rules: Penn Treebank (PTB), Tweet, MWE, Spacy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['A', 'nice', 'day', ',', 'Let', \"'s\", 'do', 'tokenization', 'at', 'the', 'U.K.', '!', ':', '-D']  (PTB)\n",
      "['A', 'nice', 'day', ',', 'Let', \"'s\", 'do', 'tokenization', 'at', 'the', 'U.K.', '!', ':', '-D']  (PTB+)\n",
      "['A', 'nice', 'day', ',', \"Let's\", 'do', 'tokenization', 'at', 'the', 'U', '.', 'K', '.', '!', ':-D']  (Tweet)\n",
      "['A', 'nice', 'day', ',', \"Let's\", 'do_tokenization', 'at', 'the', 'U', '.', 'K', '.', '!', ':-D']  (MWE+Tweet)\n"
     ]
    }
   ],
   "source": [
    "# Penn Treebank (NLTK version)\n",
    "from nltk.tokenize import NLTKWordTokenizer, TreebankWordTokenizer, TweetTokenizer, MWETokenizer\n",
    "text = \"A nice day, Let's do tokenization at the U.K.! :-D\"\n",
    "tb_tokenizer = TreebankWordTokenizer()\n",
    "\"\"\"\n",
    "The Treebank tokenizer uses regular expressions to tokenize text as in Penn Treebank, see utils/tokenizer.sed for reference\n",
    "(1) split standard contractions, e.g. ``don't`` -> ``do n't`` and ``they'll`` -> ``they 'll``\n",
    "(2) treat most punctuation characters as separate tokens\n",
    "(3) split off commas and single quotes, when followed by whitespace\n",
    "(4) separate periods that appear at the end of line\n",
    "Reference: https://www.nltk.org/api/nltk.tokenize.TreebankWordTokenizer.html#nltk.tokenize.TreebankWordTokenizer\n",
    "\"\"\"\n",
    "w_tokenizer = NLTKWordTokenizer()\n",
    "\"\"\"\n",
    "The NLTK tokenizer that has improved upon the TreebankWordTokenizer with additional relues, they share the same algorithm\n",
    "\"\"\"\n",
    "print(w_tokenizer.tokenize(text), \" (PTB)\")\n",
    "print(tb_tokenizer.tokenize(text), \" (PTB+)\")\n",
    "\n",
    "# Special for Tweet\n",
    "tweet_tokenizer = TweetTokenizer()\n",
    "\"\"\"\n",
    "tokenizer for Tweets, e.g emoj, Kaomoji\n",
    "\"\"\"\n",
    "print(tweet_tokenizer.tokenize(text), \" (Tweet)\")\n",
    "\n",
    "# Merge multi-words\n",
    "mwe_tokenizer = MWETokenizer()\n",
    "mwe_tokenizer.add_mwe(('do', 'tokenization'))\n",
    "\"\"\"\n",
    "merge multi-word expressions into single tokens\n",
    "\"\"\"\n",
    "print(mwe_tokenizer.tokenize(tweet_tokenizer.tokenize(text)), \" (MWE+Tweet)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['A', 'nice', 'day', ',', 'Let', \"'s\", 'do', 'tokenization', 'at', 'U.K.', '!']  (spaCy)\n"
     ]
    }
   ],
   "source": [
    "# Spacy rules\n",
    "import spacy\n",
    "text = \"A nice day, Let's do tokenization at U.K.!\"\n",
    "nlp = spacy.load('en_core_web_sm')\n",
    "\"\"\"\n",
    "(1) Does the substring match a tokenizer exception rule? For example, “don’t” does not contain whitespace, but should be split into two tokens, “do” and “n’t”, while “U.K.” should always remain one token.\n",
    "(2) Can a prefix, suffix or infix be split off? For example punctuation like commas, periods, hyphens or quotes.\n",
    "Reference: https://spacy.io/usage/spacy-101\n",
    "\"\"\"\n",
    "doc = nlp(text)\n",
    "print([token.text for token in doc], \" (spaCy)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Statistic-based Tokenization\n",
    "\n",
    "### Byte-Pair Encoding (BPE)\n",
    "\n",
    "**Brief Introduction (data compression)**\n",
    "\n",
    "> The algorithm compresses data by finding the most frequently occurring pairs of adjacent bytes in the data and replacing all instances of the pair with a byte that was not in the original data. The algorithm repeats this process until no further compression is possible, either because there are no more frequently occurring pairs or there are no more unused bytes to represent pairs. [1]\n",
    "\n",
    "**Example (Wiki)**\n",
    "\n",
    "Suppose the data to be encoded is `aaabdaaabac`, The byte pair \"aa\" occurs most often, so it will be replaced by a byte that is not used in the data, such as \"Z\". Now there is the following data and replacement table: `ZabdZabac`, `Z=aa`. Then the process is repeated with byte pair \"ab\", replacing it with \"Y\": `ZYdZYac`, `Y=ab, Z=aa`. The only literal byte pair left occurs only once, and the encoding might stop here. Alternatively, the process could continue with recursive byte pair encoding, replacing \"ZY\" with \"X\": `XdXac`, `X=ZY, Y=ab, Z=aa`. This data cannot be compressed further by byte pair encoding because there are no pairs of bytes that occur more than once.\n",
    "\n",
    "**Word Segmentation Algorithm**\n",
    "> Firstly, we initialize the symbol vocabulary with the character vocabulary, and represent each word as a sequence of characters, plus a special end-ofword symbol ‘·’, which allows us to restore the original tokenization after translation. We iteratively count all symbol pairs and replace each occurrence of the most frequent pair (‘A’, ‘B’) with a new symbol ‘AB’. Each merge operation produces a new symbol which represents a character n-gram. Frequent character n-grams (or whole words) are eventually merged into a single symbol, thus BPE requires no shortlist. The final symbol vocabulary size is equal to the size of the initial vocabulary, plus the number of merge operations – the latter is the only hyperparameter of the algorithm. [2]\n",
    "\n",
    "\n",
    "*References*\n",
    "> [1] Gage, Philip. “A new algorithm for data compression.” The C Users Journal archive 12 (1994): 23-38. \n",
    "\n",
    "> [2] Sennrich, Rico et al. “Neural Machine Translation of Rare Words with Subword Units.” ArXiv abs/1508.07909 (2015): n. pag.\n",
    "\n",
    "**Pretrained Language Models**\n",
    "\n",
    "GPT-2, RoBERTa, BART, DeBERTa\n",
    "\n",
    "**Implementation**\n",
    "\n",
    "huggingface-tokenizer training script: https://github.com/EleutherAI/gpt-neo/blob/master/data/train_tokenizer.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before BPE:  {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w e s t </w>': 6, 'w i d e s t </w>': 3}\n",
      "after BPE:  {'low</w>': 5, 'low e r </w>': 2, 'newest</w>': 6, 'wi d est</w>': 3}\n"
     ]
    }
   ],
   "source": [
    "# The following pipeline comes from the original paper: Neural Machine Translation of Rare Words with Subword Units.\n",
    "import re, collections\n",
    "vocab = {'l o w </w>' : 5, 'l o w e r </w>' : 2, 'n e w e s t </w>':6, 'w i d e s t </w>':3} # add special token </w> for detokenize\n",
    "print(\"before BPE: \", vocab)\n",
    "num_merges = 10 # evidence: 1) empirical testing; 2) computational constraints; 3) common choices; 4) frequency plateau\n",
    "for i in range(num_merges):\n",
    "    # step-1: get the pair frequence\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",
    "    best = max(pairs, key=pairs.get)\n",
    "    # step-2: merge most pairs\n",
    "    v_out = {}\n",
    "    bigram = re.escape(' '.join(best))\n",
    "    p = re.compile(r'(?<!\\S)' + bigram + r'(?!\\S)')\n",
    "    for word in vocab:\n",
    "        w_out = p.sub(''.join(best), word)\n",
    "        v_out[w_out] = vocab[word]\n",
    "    vocab = v_out\n",
    "print(\"after BPE: \", vocab)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "vocab before bpe:  ['d', 'e', 'i', 'l', 'n', 'o', 'r', 's', 't', 'w', 'Ġ', 'UNK']\n",
      "vocab after bpe:  ['d', 'e', 'i', 'l', 'n', 'o', 'r', 's', 't', 'w', 'Ġ', 'UNK', 'es', 'est', 'lo', 'low', 'Ġlow', 'Ġn', 'Ġne', 'Ġnew']\n"
     ]
    }
   ],
   "source": [
    "# The following pipeline is modified from tokenizer: https://github.com/huggingface/tokenizers (the original code is implemented by RUST)\n",
    "from collections import defaultdict\n",
    "# 0.0 normalization: some general cleanup, such as removing needless whitespace, lowercasing, and/or removing accents\n",
    "raw_text = \"lôw low low low low lowér Lower newest newest newest newest newest newest widest widest widest\"\n",
    "text = \"low low low low low lower lower newest newest newest newest newest newest widest widest widest\"\n",
    "# 0.1 pre-tokenization: add special tag to the begining of each word\n",
    "text = \"low Ġlow Ġlow Ġlow Ġlow Ġlower Ġlower Ġnewest Ġnewest Ġnewest Ġnewest Ġnewest Ġnewest Ġwidest Ġwidest Ġwidest\"\n",
    "# 1. add all special tokens to the vocabulary\n",
    "vocab = ['UNK']\n",
    "# 2. compute the initial alphabet\n",
    "vocab = ['d', 'e', 'i', 'l', 'n', 'o', 'r', 's', 't', 'w', 'Ġ', 'UNK']\n",
    "# 3. tokenize word: get the word frequency by rule-based tokenization strategy\n",
    "word_freq = {'low' : 1, 'Ġlow': 4, 'Ġlower' : 2, 'Ġnewest':6, 'Ġwidest':3}\n",
    "print(\"vocab before bpe: \", vocab)\n",
    "# 4. core algorithm: rank and merge\n",
    "vocab_size = 20\n",
    "merges = {} # used for further tokenize\n",
    "splits = {word: [c for c in word] for word in word_freq.keys()} # intermedia results \n",
    "while len(vocab) < vocab_size:\n",
    "    # count pairs in words\n",
    "    pair_freqs = defaultdict(int)\n",
    "    for word, freq in word_freq.items():\n",
    "        split = splits[word]\n",
    "        if len(split) == 1: continue\n",
    "        for i in range(len(split)-1):\n",
    "            pair = (split[i], split[i+1])\n",
    "            pair_freqs[pair] += freq\n",
    "    # get most frequent pair\n",
    "    best_pair = ''\n",
    "    max_freq = None\n",
    "    for pair, freq in pair_freqs.items():\n",
    "        if max_freq is None or max_freq < freq:\n",
    "            best_pair = pair\n",
    "            max_freq = freq\n",
    "    # merge pair\n",
    "    for word in word_freq:\n",
    "        split = splits[word]\n",
    "        if len(split) == 1: continue\n",
    "        i = 0\n",
    "        while i < len(split)-1:\n",
    "            if split[i] == best_pair[0] and split[i+1] == best_pair[1]:\n",
    "                split = split[:i] + [best_pair[0]+best_pair[1]] + split[i+2:]\n",
    "            else:\n",
    "                i += 1\n",
    "        splits[word] = split\n",
    "    merges[best_pair] = best_pair[0] + best_pair[1]\n",
    "    vocab.append(best_pair[0]+best_pair[1])\n",
    "print(\"vocab after bpe: \", vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Byte-level BPE (BBPE)\n",
    "\n",
    "**Brief Introduction**\n",
    "\n",
    "the basic unit for BPE is byte\n",
    "\n",
    "example[3]\n",
    "\n",
    "<img style=\"left;\" src=\"assets/BBPE.png\" width=\"600\">\n",
    "\n",
    "*Reference*\n",
    "> [3] Wang, Changhan et al. “Neural Machine Translation with Byte-Level Subwords.” ArXiv abs/1909.03341 (2019): n. pag.\n",
    "\n",
    "\n",
    "**Pretrained Language Models**\n",
    "GPT2, RoBERTa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### WordPiece\n",
    "\n",
    "**Brief Introduction**\n",
    "Difference with BPE: the merge creteria: Choose the new word unit out of all possible ones that increases the likelihood on the training data the most when added to the model [4]\n",
    "\n",
    "**Pretrained Models**\n",
    "\n",
    "Bert, DistilBert\n",
    "\n",
    "*Reference*\n",
    "> [4] Schuster, Mike and Kaisuke Nakajima. “Japanese and Korean voice search.” 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2012): 5149-5152.\n",
    "\n",
    "> [5] Wu, Yonghui et al. “Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation.” ArXiv abs/1609.08144 (2016): n. pag.\n",
    "\n",
    "**Implementation**\n",
    "\n",
    "Huggingface's Version:\n",
    "\n",
    "The main difference is the way the pair to be merged is selected. Instead of selecting the most frequent pair, WordPiece computes a score for each pair, using the following formula: `score=(freq_of_pair)/(freq_of_first_element×freq_of_second_element)`, see [WordPiece tokenization](https://huggingface.co/learn/nlp-course/chapter6/6?fw=pt) for details.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Unigram\n",
    "\n",
    "**Brief Introduction**\n",
    "> Compared to BPE and WordPiece, Unigram works in the other direction: it starts from a big vocabulary and removes tokens from it until it reaches the desired vocabulary size.\n",
    "\n",
    "*Reference*\n",
    "> [6] Kudo, Taku. “Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates.” ArXiv abs/1804.10959 (2018): n. pag.\n",
    "\n",
    "**Implementation**\n",
    "\n",
    "Huggingface's Version:\n",
    "\n",
    "[Unigram tokenization](https://hf-mirror.com/learn/nlp-course/chapter6/7?fw=pt)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Sentencepiece\n",
    "\n",
    "**Brief Introduction**\n",
    "> Treats the input as a raw input stream (language unrelated)\n",
    "\n",
    "**Pretrained Language Model**\n",
    "\n",
    "Albert, XLNet, Marian, T5\n",
    "\n",
    "*Reference*\n",
    "> [7] Kudo, Taku and John Richardson. “SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing.” Conference on Empirical Methods in Natural Language Processing (2018).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tools\n",
    "\n",
    "- [minbpe](https://github.com/karpathy/minbpe), Minimal, clean code for the (byte-level) Byte Pair Encoding (BPE) algorithm commonly used in LLM tokenization. The BPE algorithm is \"byte-level\" because it runs on UTF-8 encoded strings."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "nlp",
   "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}