{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b08605ee",
   "metadata": {},
   "source": [
    "\n",
    "## Exercise 1: Tokenization and Vocabulary\n",
    "Consider the following corpus: “Apple is a high-tech company; it produces mobile phones and laptops. It's products often feature an apple design on their backs.”\n",
    "\n",
    "**a.** Apply simple whitespace tokenization to the corpus, list all resulting unique tokens and compute the vocabulary size.\n",
    "**b.**\tApply simple whitespace tokenization to the corpus after applying lowercasing, list all resulting unique tokens and compute the vocabulary size.\n",
    "**c.**\tCompare the vocabularies obtained in part a & b. Identify one concrete problem caused by lowercasing.\n",
    "**d.**\tApply Penn Treebank tokenization to the corpus after applying lowercasing, list all resulting unique tokens and compute the vocabulary size.\n",
    "**e.**\tCompare the vocabularies obtained in part a & d. Identify one concrete problem solved by Penn Treebank tokenization.\n",
    "\n",
    "\n",
    "### Solution\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "528a8f87",
   "metadata": {},
   "outputs": [],
   "source": [
    "corpus = \"Apple is a high-tech company; it produces mobile phones and laptops. It's products often feature an apple design on their backs.\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07ce532e",
   "metadata": {},
   "source": [
    "**a.** {'Apple', 'is', 'a', 'high-tech', 'company;', 'it', 'produces', 'mobile', 'phones', 'and', 'laptops.', \"It's\", 'products', 'often', 'feature', 'an', 'apple', 'design', 'on', 'their', 'backs.'}\n",
    "\n",
    "$|V| = 21$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e31d493",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = corpus.split()\n",
    "vocab = set(x)\n",
    "print(\"Tokens: \", vocab)\n",
    "print(\"|V| = \", len(vocab))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35238dda",
   "metadata": {},
   "source": [
    "**b.** {'is', 'a', 'high-tech', 'company;', 'it', 'produces', 'mobile', 'phones', 'and', 'laptops.', \"It's\", 'products', 'often', 'feature', 'an', 'apple', 'design', 'on', 'their', 'backs.'}\n",
    "\n",
    "$|V| = 20$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c90f72e",
   "metadata": {},
   "outputs": [],
   "source": [
    "lowered = corpus.lower()\n",
    "x = lowered.split()\n",
    "vocab = set(x)\n",
    "print(\"Tokens: \", vocab)\n",
    "print(\"|V| = \", len(vocab))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67a161a4",
   "metadata": {},
   "source": [
    "**c.** We loose semantic information *(Apple & apple)*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fcbf8ccc",
   "metadata": {},
   "source": [
    "**d.** tokens:  {'laptops.', 'backs', 'high-tech', 'their', 'a', 'produces', \"'s\", 'is', 'products', 'often', 'an', 'on', '.', 'design', 'and', 'mobile', 'apple', 'phones', 'feature', 'company', 'it', ';'}\n",
    "$|V| =  22$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "38ffd53c",
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.tokenize.treebank import TreebankWordTokenizer\n",
    "\n",
    "tokenizer = TreebankWordTokenizer()\n",
    "lowered = corpus.lower()\n",
    "\n",
    "\n",
    "tokens = tokenizer.tokenize(lowered)\n",
    "vocab = set(tokens)\n",
    "print(\"tokens: \", vocab)\n",
    "print(\"|V| = \", len(vocab))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b41c473f",
   "metadata": {},
   "source": [
    "## Exercise 2- Stemming vs Lemmatization\n",
    "\n",
    "You are given the following list of words and the form they were reduced to by a text normalization process.\n",
    "\n",
    "**a.** For each word, indicate whether the transformation was produced by: Stemming or Lemmatization and justify why?\n",
    "\n",
    "| Original Word | Normalized Word |\n",
    "| ------------ | ------------ |\n",
    "| Studies | Studi |\n",
    "| Better | Good |\n",
    "| Cating | Care |\n",
    "| Wolves | Wolf |\n",
    "| Organization | Organ |\n",
    "\n",
    "**b.** Identify **one transformation** in the table that clearly distinguishes stemming from lemmatization, and explain why.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7e17580",
   "metadata": {},
   "source": [
    "## Exercise 3: Morphological Analysis\n",
    "\n",
    "Below is a list of **morphemes** (the smallest units of meaning) highlighted within specific words.\n",
    "For each example, identify if the highlighted part is an **Inflectional Morpheme**, a **Derivational Morpheme**, or a **Clitic**. Justify why?\n",
    "\n",
    "| Word Example\t| Highlighted Morpheme |\n",
    "| -------------- | -------------- |\n",
    "| Played |\ted |\n",
    "| unhappy\t| un |\n",
    "| cats\t| s |\n",
    "| I'm\t| 'm |\n",
    "| Slowly\t| ly |\n",
    "| she'll |\t'll |\n",
    "| teacher\t| teach |\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fdeeb337",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict, Counter\n",
    "from typing import Dict, List, Tuple\n",
    "\n",
    "\n",
    "def get_vocab(corpus: List[str]) -> Dict[Tuple[str, ...], int]:\n",
    "    \"\"\"\n",
    "    Build initial vocabulary from corpus.\n",
    "    Each word is split into characters + </w>\n",
    "    \"\"\"\n",
    "    vocab = defaultdict(int)\n",
    "    for word in corpus:\n",
    "        tokens = tuple(word) + (\"</w>\",)\n",
    "        vocab[tokens] += 1\n",
    "    return vocab\n",
    "\n",
    "\n",
    "def get_pair_frequencies(vocab: Dict[Tuple[str, ...], int]) -> Counter:\n",
    "    \"\"\"\n",
    "    Count frequency of adjacent symbol pairs\n",
    "    \"\"\"\n",
    "    pairs = Counter()\n",
    "    for word, freq in vocab.items():\n",
    "        for i in range(len(word) - 1):\n",
    "            pairs[(word[i], word[i + 1])] += freq\n",
    "    return pairs\n",
    "\n",
    "\n",
    "def merge_pair(\n",
    "    pair: Tuple[str, str], vocab: Dict[Tuple[str, ...], int]\n",
    ") -> Dict[Tuple[str, ...], int]:\n",
    "    \"\"\"\n",
    "    Merge a given pair in the vocabulary\n",
    "    \"\"\"\n",
    "    merged_vocab = {}\n",
    "\n",
    "    bigram = pair\n",
    "    replacement = \"\".join(pair)\n",
    "\n",
    "    for word, freq in vocab.items():\n",
    "        new_word = []\n",
    "        i = 0\n",
    "        while i < len(word):\n",
    "            # If we see the bigram, merge it\n",
    "            if i < len(word) - 1 and (word[i], word[i + 1]) == bigram:\n",
    "                new_word.append(replacement)\n",
    "                i += 2\n",
    "            else:\n",
    "                new_word.append(word[i])\n",
    "                i += 1\n",
    "\n",
    "        merged_vocab[tuple(new_word)] = freq\n",
    "\n",
    "    return merged_vocab\n",
    "\n",
    "\n",
    "def train_bpe(corpus: List[str], num_merges: int):\n",
    "    \"\"\"\n",
    "    Train BPE and return learned merge rules\n",
    "    \"\"\"\n",
    "    vocab = get_vocab(corpus)\n",
    "    merges = []\n",
    "\n",
    "    for _ in range(num_merges):\n",
    "        pair_freqs = get_pair_frequencies(vocab)\n",
    "        if not pair_freqs:\n",
    "            break\n",
    "\n",
    "        best_pair = pair_freqs.most_common(1)[0][0]\n",
    "        merges.append(best_pair)\n",
    "\n",
    "        vocab = merge_pair(best_pair, vocab)\n",
    "\n",
    "    return merges, vocab\n",
    "\n",
    "\n",
    "corpus = []\n",
    "\n",
    "for i in range(12):\n",
    "    corpus.append(\"pun\")\n",
    "\n",
    "for i in range(10):\n",
    "    corpus.append(\"hug\")\n",
    "\n",
    "\n",
    "for i in range(5):\n",
    "    corpus.append(\"pug\")\n",
    "\n",
    "for i in range(4):\n",
    "    corpus.append(\"bun\")\n",
    "\n",
    "for i in range(2):\n",
    "    corpus.append(\"bus\")\n",
    "\n",
    "\n",
    "vocab = train_bpe(corpus, 100)\n",
    "print(vocab)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.13.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
