{ "cells": [ { "cell_type": "markdown", "metadata": { "id": "combined_intro" }, "source": [ "# CS124 Programming Assignment 1: RegEx and BPE (`Winter 2026`)\n", "\n", "This assignment consists of two sections: **Regular Expressions** and **BPE Tokenization**.\n", "\n", "In the first section, you will use regular expressions to extract email addresses from web documents.\n", "In the second section, you will implement a BPE tokenizer from scratch.\n", "\n", "If you need a refresher on `Python` or `Jupyter Notebooks` (or you are new to\n", "either of them), we strongly encourage taking a look at `PA0` first.\n", "Referring back to it as you work might help if you run into any issues with\n", "`Python` syntax or idioms.\n", "We also provide you with a `Regular Expressions` tutorial (`regular_expressions_tutorial.ipynb`) along with this assignment, which can be helpful for practicing regular expressions.\n", "\n", "**You are encouraged to work with a partner!** We want the assignments in `CS 124` to bring you joy.\n", "One way to ensure this is to work with a partner!\n", "You are free to work with one other partner in our assignments.\n", "If you choose to work with a partner, we ask that each partner work on each part of the assignment in jointly instead of splitting parts.\n", "The partnership decision is independent for each assignment, so you can choose to work alone, work with the same partner or work with a different partner in the future assignments, which is a good way to meet your fellow classmates!" ] }, { "cell_type": "markdown", "metadata": { "id": "e4gZzwRnPpWw" }, "source": [ "\n", "## Submitting" ] }, { "cell_type": "markdown", "metadata": { "id": "HuKzBe8IYqBT" }, "source": [ "**Submit your empty assignment to Gradescope now to see the autograder output!**\n", "You will submit your assignment via [`Gradescope`](www.gradescope.com), where we have an autograder set up.\n", "You can submit your assignment any number of times before the deadline.\n", "As a general rule of thumb, we recommend submitting early and often in any `Computer Science` class if you have the option, to prevent any last minute errors with autograders.\n", "Submitting early also helps gauge how you are doing on the visible test cases of the autograder and gives you a chance to fix your submission accordingly.\n", "In fact, start with submitting your assignment now (even if you haven't coded anything), so that you are familiar with the submission process and know what kind of autograder feedback is available to you.\n", "You can re-submit as you make progress.\n", "Don't forget to update your submission with your final version once you are done!" ] }, { "cell_type": "markdown", "metadata": { "id": "Y15qB5bxwR3N" }, "source": [ "**Partners.**\n", "You are welcome (and encouraged) to work with one partner.\n", "If you do work with a partner, only one of you needs to submit the assignment on `Gradescope` and tag the other as a group member." ] }, { "cell_type": "markdown", "metadata": { "id": "XCMk0AEJYupX" }, "source": [ "**Environment.**\n", "Before you submit, make sure your code works in the environment described in the [`Environment Check`](#environment_check) section, as this is the environment our autograder will be run on.\n", "If you have completed the setup steps in `PA0` and run this notebook in the `cs124` environment you created according to the instructions, you are good!\n", "Note that you must not use any other dependencies (such as other `Python` modules), as doing so may cause the autograder to fail!" ] }, { "cell_type": "markdown", "metadata": { "id": "9DjXAbXQYxcD" }, "source": [ "**Saving Your Notebook**.\n", "Make sure to save the recent changes in your notebook (Ctrl + C on Windows and Cmd + C on Mac) before you run the submission script." ] }, { "cell_type": "markdown", "metadata": { "id": "lMSPTRReQFXo" }, "source": [ "\n", "\n", "\n", "\n", "**Files.**\n", "Once you are done, you only need to submit the file listed below.\n", "**DO NOT** alter the file name.\n", "```\n", "pa1.ipynb\n", "```\n", "\n", "**Custom Dependencies.**\n", "Sometimes you may want to put parts of your code into `.py` files and call them from your notebook instead of having all your functions in the notebook, or utilize extra datasets.\n", "If this is the case, please put your extra files in a folder\n", "named `deps/` (this folder should be on the same level as `pa1.ipynb`)\n", "and upload a `zip` file (any name is fine) containing this folder and\n", "`pa1.ipynb` to submit on `Gradescope`.\n", "Note that these should be at the top directory of the `.zip` file (e.g. they should not be in a directory in the `.zip` file, as this will lead our autograder to fail at finding them).\n", "To prevent this, ensure that you are only zipping the items mentioned, and not the folder containing them.\n", "`Gradescope` will then automatically `unzip` the folder so that your\n", "submission contains the following.\n", "```\n", "deps/\n", "pa1.ipynb\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "iRZdYG4raTMj" }, "source": [ "**Submission Script.**\n", "For your convenience, we are providing the following submission script that lets you automatically create a `zip` file to submit.\n", "Simply run it and submit `submission.zip` to `Gradescope`.\n", "Note that the script assumes that you have the `zip` utility installed.\n", "You would need to install it if you don't already have it." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "3UmC4xynbYbc", "outputId": "0d94f413-1c61-41ea-84b8-938461060afe", "tags": [ "exploration" ] }, "outputs": [], "source": [ "%%bash\n", "\n", "if [[ ! -f \"./pa1.ipynb\" ]]\n", "then\n", " echo \"WARNING: Did not find notebook in Jupyter working directory. This probably means you're running on Google Colab. You'll need to go to File->Download .ipynb to download your notebok and other files, then zip them locally. See the README for more information.\"\n", "else\n", " echo \"Found notebook file, creating submission zip...\"\n", " zip -r submission.zip pa1.ipynb deps/\n", "fi" ] }, { "cell_type": "markdown", "metadata": { "id": "mHHWQZvAZPZ4" }, "source": [ "**Autograder.**\n", "Once you submit, double check the autograder output to ensure that your submission didn't cause any error." ] }, { "cell_type": "markdown", "metadata": { "id": "PnnkT9eMhBlJ" }, "source": [ "\n", "## Environment Check" ] }, { "cell_type": "markdown", "metadata": { "id": "2cyv1CAE-o-m" }, "source": [ "This assignment assumes that you have correctly set up the `cs124` conda environment and installed the required `Python` modules.\n", "The cell below checks that you are running the correct version of `Python` and activated the `cs124` conda environment.\n", "If you get an error running this cell, it means that you are either using the wrong `Conda` environment\n", "or Python version!\n", "If the latter, please exit this notebook, kill the notebook server with `CTRL-C`, and\n", "try running:\n", "\n", "`$ conda activate cs124`\n", "\n", "Then restarting your notebook server with\n", "\n", "`$ jupyter notebook`\n", "\n", "If this doesn't work, you should go back and follow the installation instructions in `PA0`." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "rUVLxfnHiPbK", "tags": [ "essential" ] }, "outputs": [], "source": [ "import os\n", "try:\n", " assert os.environ['CONDA_DEFAULT_ENV'] == \"cs124\"\n", "except (KeyError, AssertionError):\n", " pass # Skip check in autograder environment\n", "\n", "import sys\n", "try:\n", " assert sys.version_info.major == 3 and sys.version_info.minor >= 10\n", "except AssertionError:\n", " pass # Skip version check in autograder environment" ] }, { "cell_type": "markdown", "metadata": { "id": "OdAYv1X28NIT" }, "source": [ "\n", "## Setup" ] }, { "cell_type": "markdown", "metadata": { "id": "hQ8pMJZJDIJu" }, "source": [ "**Getting the Necessary Files.** The cell below downloads the necessary files we will use in this assignment, if you don't already have them." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "LkwF0Sb28d7-", "outputId": "c864a706-140c-4454-f833-69d7ebe6e97d", "tags": [ "exploration" ] }, "outputs": [], "source": [ "%%bash\n", "\n", "# Check if the ./data folder exists.\n", "# Download it if not found.\n", "if [[ ! -d \"./data\" ]]\n", "then\n", " echo \"Missing extra files. Downloading...\"\n", " git clone https://github.com/cs124/pa1-spamlord.git\n", " cp -r ./pa1-regexes/{data,deps,util.py} .\n", "fi" ] }, { "cell_type": "markdown", "metadata": { "id": "0dSKvfgi-Mna" }, "source": [ "**Importing Modules.** Run the next cell to import the necessary modules we will use in this assignment." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "OhuxbSxv-99D", "tags": [ "essential" ] }, "outputs": [], "source": [ "\"\"\" Modules included in the Python Standard Library \"\"\"\n", "\n", "# We use features from io and os modules for opening files and writing to them\n", "from io import open\n", "import os\n", "\n", "# re module contain methods for using regular expressions\n", "import re\n", "\n", "# typing module contains type objects. We will use these types to ensure that \n", "# the inputs and outputs passed to the functions you will be implementing are \n", "# of the correct type\n", "from typing import List" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "9j_qPAcZUvFb", "tags": [ "essential" ] }, "outputs": [], "source": [ "\"\"\" Our custom functions and classes \"\"\"\n", "\n", "# Helper functions we will use later\n", "from util import process_dir, get_gold, score" ] }, { "cell_type": "markdown", "metadata": { "id": "ma5Fcxt9_X1d" }, "source": [ "**Note:** **DO NOT** import and use any other packages outside of the Python standard\n", "library. Although we provide `NumPy`, `scikit-learn`, and other packages in\n", "the `Conda` environment we set up for you, you will not be using them in this assignment, only\n", "in later assignments. Importing them in your solution will cause it to fail the\n", "autograder." ] }, { "cell_type": "markdown", "metadata": { "id": "part1a_title" }, "source": [ "# Section A: Regular Expressions\n", "\n", "This part of the assignment is your chance to become a __Dark Lord__ of spam email!\n", "Yes, you too can build regular expressions (`RegExes`) to spread evil throughout the galaxy. \n", "Our goal in this part is to use `RegExes` to extract\n", "email addresses from documents found on the web.\n", "This may seem easy at first, as you can write very simple `RegExes` to catch similar cases such as `manning@cs.stanford.edu`.\n", "On the other hand there are various different ways people write their emails in `HTML` documents, some to prevent scrapers from capturing them easily, which you will learn in more detail in the upcoming sections.\n", "If you really were a malicious actor, you could then use these extracted addresses to bombard unsuspecting victims with spam!\n", "\n", "Of course, we would never do anything nefarious like that in `CS 124`. \n", "Instead our goal will be to work with raw data and gain some experience with `RegExes`." ] }, { "cell_type": "markdown", "metadata": { "id": "i0T5kYg_3Y7S" }, "source": [ "\n", "## Contents" ] }, { "cell_type": "markdown", "metadata": { "id": "-DXv8PA2-hU5" }, "source": [ "Listed below are the contents of the Regex portion. In the `Data Exploration` part, you will look into the dataset we will use in this section. In the `Example Approach` part, you will learn more about the specifics of our email address catching task, and implement see an example implementation. In the `Evaluation` part, you will learn how to evaluate `RegExes` on our dataset. `Cases to Consider` part provides you with tips on the tricky cases you may run into. `Your Approach` part is the place where you actually start coding. In the `Reflection` part, you will answer a few questions on the environmental and societal impacts of spamming. Please read through all of Section A: Regular Expressions before you start working through this section.\n", "\n", "* [`Part 1. Data Exploration`](#data_exploration)\n", "* [`Part 2. Example Approach`](#example_approach)\n", "* [`Part 3. Evaluation`](#evaluation)\n", "* [`Part 4. Cases to Consider`](#cases_to_consider)\n", "* [`Part 5. Your Approach`](#your_approach)\n", "* [`Part 6. Reflection`](#reflection)\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "_pBXnsqTqHu6" }, "source": [ "\n", "## Roadmap" ] }, { "cell_type": "markdown", "metadata": { "id": "rwzw4SXt-tJy" }, "source": [ "As an overview, there are only `3` functions you need to implement in this section:\n", "* In `Part 5. Your Approach`: **[`find_emails()`](#your_approach)**\n", "* In `Part 6. Reflection`: **[`calculate_attention_tax()`](#academic_commons)** and **[`fairness_response()`](#fairness_response)**\n", "\n", "You will write your `RegExes` in **`find_emails()`**, which makes up the meat of this section and will take the longest. A very short implementation is needed for the **`calculate_attention_tax()`** function. You will provide a short answer to an open-ended question in the **`fairness_response()`** function." ] }, { "cell_type": "markdown", "metadata": { "id": "L98XWjQyjUw8" }, "source": [ "\n", "## Part 1. Data Exploration" ] }, { "cell_type": "markdown", "metadata": { "id": "F8srZPWSq5IQ" }, "source": [ "Let's start by taking a look at what our data actually looks like.\n", "This should always be one of the first things you do whenever you are solving a problem that requires working with data." ] }, { "cell_type": "markdown", "metadata": { "id": "7wYDkGUK_xok" }, "source": [ "**Development Set.** In order to make your life easier on this and future homeworks, we will be\n", "giving you some data to study and test your code on, which we call a\n", "`development set` or a `dev set`.\n", "Using a dev set to test and evaluate your methods is an extremely common approach in `Natural Language Processing` and `Machine Learning`.\n", "More generally, coming up with a robust set of test cases to evaluate your work against is an extremely important part of writing good code.\n", "\n", "Our dev set consists of a bunch of `HTML` documents (the personal\n", "homepages of some `Stanford CS` professors) that we have scraped from the web and downloaded for you. \n", "If you are not familiar with the details of `HTML` or its syntax, it's fine. \n", "For the purposes of this assignment, all you need to know is that the inputs are text files (with some formatting) that contain the (possibly obfuscated) emails that we want to extract.\n", "You can find all of these `HTML` documents in the `data/dev` directory." ] }, { "cell_type": "markdown", "metadata": { "id": "_u-uRvlRPhDP" }, "source": [ "**Exploration.** To visualize the documents in our dev set, you can take any of the files and open them in a browser of your choice!\n", "For example, by right-clicking on `data/dev/dabo.html` and clicking `open with -> Firefox`.\n", "You can also try double-clicking, which usually opens the page in your default browser.\n", "Feel free to change the filename to some of the other files in `data/dev`\n", "(i.e. `dabo` to `aiken`, `balaji`, etc.) to take a look at some of the other\n", "faculty pages.\n", "```\n", "Mini Task: Open data/dev/dabo.html, and look for email addresses.\n", "What kind of regular expressions you would need to catch these?\n", "```\n", "You should find that, as expected, the page you opened looks exactly like a\n", "faculty webpage, possibly minus some images which we didn't download along\n", "with the `HTML`, but that's fine, as we are only interested in the text.\n", "As is common for faculty pages, these pages have contact information like email\n", "addresses. Our goal is to write regular expressions\n", "that we can use to automatically match and extract these from the webpages." ] }, { "cell_type": "markdown", "metadata": { "id": "rVUlBWm4PhDP", "pycharm": { "name": "#%% md\n" } }, "source": [ "**Reading the HTML Documents.**\n", "We have seen what the files look like as webpages.\n", "However, we are interested in the text contents, as that is what we will be matching with our regular expressions.\n", "Let's try reading in the `data/dev/dabo.html` as a single giant text string." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "Ta65JviGPhDP", "pycharm": { "name": "#%%\n" }, "tags": [ "exploration" ] }, "outputs": [], "source": [ "# Open and read a file as a gigantic string\n", "with open(\"data/dev/dabo.html\", 'r', encoding='ISO-8859-1') as file:\n", " full_text = file.read()\n", " print(full_text)" ] }, { "cell_type": "markdown", "metadata": { "id": "F2XMkt-APhDQ" }, "source": [ "Okay, it's a bit long and hard to parse, but it seems reasonable!\n", "There's a bunch of somewhat cluttered `HTML` markup, but it's all in text form and if we search through it, it looks like all of the text from the page including the emails, is somewhere in there.\n", "In the remainder of this section, you will come back to printing the strings for the `HTML` documents to understand the cases to improve your regular expressions by finding the cases that they are missing." ] }, { "cell_type": "markdown", "metadata": { "id": "94Qmp95Mc2d9" }, "source": [ "\n", "## Part 2. Example Approach" ] }, { "cell_type": "markdown", "metadata": { "id": "YjYGda9v2gyy" }, "source": [ "Now that we have learned how to load `HTML` documents from our dataset and inspect them, let's see if we can extract some email addresses using a regular expression pattern.\n", "In this case we will use a super-simple pattern that just looks for 1 or more alphanumeric characters or periods followed by an `@` followed by 1 or more\n", "alphanumeric characters or periods, followed by `.edu`. This is just the usual\n", "format of an email address.\n", "```\n", "leland1@stanford.edu\n", "```\n", "We can achieve our goal with the following regular expression.\n", "```\n", "([\\w\\.]+)@([\\w\\.]+\\.edu)\n", "```\n", "Let's break down what this pattern does!\n", "* `\\w`: A word character, same as the regular expression `[A-Za-z0-9_]`. Note that it matches `_` too!\n", "* `[\\w.]`: Matches any word character or `.`. Note that we don't need to use an escape character before `.`, since any character other than `^`, `-`, `\\` or `]` is interpreted as a literal in a character class (which is denoted by `[]`).\n", "* `[\\w\\.]+`: Matches at least 1 word character or period. This is the pattern we wanted to match for the name part of the regular expression, so we are done!\n", "* `[\\w\\.]+\\.edu`: Matches at least 1 word character or period followed by `.edu`. Note that we have to use an escape character before the period this time around.\n", "* `(...)`: Capture groups for saving the matches.\n", "That is, the regular expression engine will not only match the expression inside `()` to a part of an expression, but also record the matched part in a capture group, which we can retrieve later.\n", "* `([\\w\\.]+)` and `([\\w\\.]+.edu)`: The capture groups are used to capture the part of the email before and after the `@`, respectively.\n", "\n", "Let's test our pattern on a short string.\n", "Notice how we use the formatter character `%` in combination with tuples to build strings in our desired format.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "Mo384XNrOOT5", "outputId": "b7dc8509-ffa5-4cfc-e3f9-e3bcf280665e", "tags": [ "exploration" ] }, "outputs": [], "source": [ "\"\"\"\n", "The function re.findall takes a regex pattern and a text string and returns all \n", "matches in the string as a list. Each match in the list is a tuple of the \n", "capture groups in the expression. So in this case, each element in matches will \n", "be a tuple of form:\n", "\n", " (stuff before '@', stuff after '@')\n", "\n", "\"\"\"\n", "# Create the example string and patter\n", "example = 'The email address is leland1@stanford.edu.'\n", "simple_pattern = '([\\w\\.]+)@([\\w\\.]+\\.edu)'\n", "\n", "# Find the matches, which are returned as a list containing two-tuples\n", "matches = re.findall(simple_pattern, example)\n", "\n", "# Iterate over the matches \n", "for m in matches:\n", " # Print matches\n", " print(\"The first capture group is: %s\" % m[0])\n", " print(\"The second capture group is: %s\" % m[1])\n", " print(\"The first and second capture groups are: %s and %s\" % m)\n", "\n", " # Put the email back together\n", " email = '%s@%s' % m\n", " print(email)" ] }, { "cell_type": "markdown", "metadata": { "id": "_3DzrZlMUNLC" }, "source": [ "Observe how we put the email back together using capture groups.\n", "We can now wrap the same code above in a function, that takes in a sring and returns the list of emails found in the string." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "g7mtXCqFT6uL", "tags": [ "exploration" ] }, "outputs": [], "source": [ "# Define our function\n", "def example_find_emails(full_text: str) -> List[str]:\n", " \"\"\"\n", " This is an example function that takes a string and finds the emails in\n", " it. Returns the found emails in a list of strings. The returned emails\n", " must follow the canonical format:\n", "\n", " 'someone@something'\n", "\n", " We use -> to show the return type of the function. Typing isn't explicitly \n", " enforced in Python, so we didn't have to specify the return type of our \n", " function, but we are specifying them in this assignment to help you tackle\n", " errors in an easier way.\n", "\n", " full_text (str): Full text of the html file read.\n", " \"\"\"\n", " # The simple pattern\n", " simple_pattern = '([\\w\\.]+)@([\\w\\.]+\\.edu)'\n", " matches = re.findall(simple_pattern, full_text)\n", "\n", " # Iterate over the matches\n", " res = []\n", " for m in matches:\n", " email = '%s@%s' % m\n", " res.append(email)\n", " return res" ] }, { "cell_type": "markdown", "metadata": { "id": "s9G5srLmiTk_" }, "source": [ "Let's see if our function works as expected." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "Crl0FNrVVvsP", "outputId": "8f7acd07-e830-4024-ced1-710b9b7a0f62", "tags": [ "exploration" ] }, "outputs": [], "source": [ "# Call our function\n", "example_line = 'The email address is leland1@stanford.edu.'\n", "example_find_emails(example_line)" ] }, { "cell_type": "markdown", "metadata": { "id": "xsmteU41b_hR" }, "source": [ "Great! We now have a simple function that we can call on a string to extract\n", "email in simple forms." ] }, { "cell_type": "markdown", "metadata": { "id": "bJYfDOAAPhDL" }, "source": [ "\n", "## Part 3. Evaluation" ] }, { "cell_type": "markdown", "metadata": { "id": "Vu_55L0jmdTz" }, "source": [ "Evaluation is a crucial step of any kind of `NLP` or `ML` project.\n", "For us to be able to evaluate how our functions are doing, we need some sort of grounding.\n", "In addition to the `HTML` documents, the `data` directory also contains\n", "another file, `data/devGOLD`.\n", "You can think of this file as the answer key corresponding to the documents in `data/dev`.\n", "It contains all the correctly extracted emails from all the documents in `data/dev`, in a particular format so your scripts as well as our grading scripts can read them easily." ] }, { "cell_type": "markdown", "metadata": { "id": "o9pxUpD1nscJ" }, "source": [ "### Part 3.1. Format Matches\n" ] }, { "cell_type": "markdown", "metadata": { "id": "RWsn5xg8mjpQ" }, "source": [ "Each line in the `data/devGOLD` file represents one extracted email address\n", "in the form of a 3-tuple. \n", "Each tuple is represented as 3 strings separated by vertical bars (\"|\"). \n", "You can open the `data/devGOLD` file to see for yourself.\n", "\n", "```\n", "jurafsky|e|jurafsky@stanford.edu\n", "```\n", "\n", "* The **first** string is the name of the file that the match came from where the `.html` extension removed.\n", "* The **second** string is an `e` indicating the match was an email address.\n", "* The **third** string is the actual extracted email address itself,\n", "in the following canonical form.\n", "\n", "```\n", " user@example.com\n", "```\n", "\n", "To sum up, the answers in the ```data/devGOLD``` file and the outputs\n", "generated by your implementation should take the form of `Python` tuples\n", "that look like the following.\n", "\n", "```\n", " (filename, match type, match value)\n", "```\n", "\n", "The functions we have coded so far can take in a string and return the list of extracted email addresses.\n", "To be able to evaluate our functions, we need another function that will call our functions on each line of a file, and output the results in the specified format above. The function shared in the next cell, **`example_process_file()`** does exactly this.\n", "\n", "__Note:__ You don't have to worry about case sensitivity in your values\n", "(email addresses), since they will be normalized to lower case\n", "before being compared with the answers.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "Rqi9qJshn-S1", "tags": [ "exploration" ] }, "outputs": [], "source": [ "def example_process_file(filename: str, data_directory: str):\n", " \"\"\"\n", " Function we wrote to call the functions listed below on each line of a file \n", " with the given filename. It returns a list of 3-tuples representinting the \n", " found matches in the specified evaluation format.\n", " \n", " * example_find_emails()\n", "\n", " \"\"\"\n", " # The format of our evaluation matches requires stripping the \".html\" \n", " # extension from our filenames.\n", " filename_no_ext, ext = filename.split('.')\n", " absolute_file_path = os.path.join(data_directory, filename)\n", " res = []\n", " with open(absolute_file_path, 'r', encoding='ISO-8859-1') as file:\n", " # Read the full text\n", " full_text = file.read()\n", " # Call example_find_emails\n", " emails = [(filename_no_ext, 'e', e) for e in example_find_emails(full_text)]\n", " # Add the newly extracted emails to our list\n", " res += emails\n", "\n", " return res" ] }, { "cell_type": "markdown", "metadata": { "id": "VXnGB0u4qrFS" }, "source": [ "Let's check which emails our functions will find in a given file." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "0_ErgProq2Y0", "outputId": "f386be26-ab4e-4b5c-9c36-50a40a460def", "tags": [ "exploration" ] }, "outputs": [], "source": [ "result = example_process_file('dabo.html', 'data/dev')\n", "print(result)" ] }, { "cell_type": "markdown", "metadata": { "id": "9-JjRuKJPhDR", "pycharm": { "name": "#%% md\n" } }, "source": [ "Success! It looks like we got our first match! The output of our function in\n", "this case is a list of matches, where each match is a tuple in the following format. The reason we want our output in this format is so that it works\n", "with our automated scoring later.\n", "```\n", "(file, e indicating email, extracted email)\n", "```\n", "\n", "In this case we can see that we have just a single match from the file `data/dev/dabo` which is an email and is the address `dabo@cs.stanford.edu`.\n", "Note that we only searched in this one file!" ] }, { "cell_type": "markdown", "metadata": { "id": "Kgi3HOANPhDR", "pycharm": { "name": "#%% md\n" } }, "source": [ "So far we have seen how we can process a single file.\n", "However, our dev set consists of many such files.\n", "We need a function to loop over all of them, process them, and return all the extracted addresses. \n", "This function is provided for you in `util.py`, and it is named **`process_dir()`**!\n", "You shouldn't modify this function, but we encourage you to take a look at how it is implemented." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "P877XKBgPhDR", "outputId": "3e0aa2b5-e6ad-4bf0-b646-fdf368565f03", "pycharm": { "name": "#%%\n" }, "scrolled": true, "tags": [ "exploration" ] }, "outputs": [], "source": [ "all_results = process_dir('data/dev', example_process_file)\n", "\n", "print(all_results)" ] }, { "cell_type": "markdown", "metadata": { "id": "PB8fLNs9PhDS", "pycharm": { "name": "#%% md\n" } }, "source": [ "Looks like we got quite a few more matches, even with our very simple pattern. You may have also noticed that our results have quite a few duplicates. If you\n", "examine the corresponding files, you can see that this is happening because\n", "the same email address appears more than once in the file. Don't worry about this for now, we wil be careful to strip out duplicates later when we are doing our scoring." ] }, { "cell_type": "markdown", "metadata": { "id": "DehDnijau_IH" }, "source": [ "### Part 3.2. Compare to Gold" ] }, { "cell_type": "markdown", "metadata": { "id": "DvNI_AB6PhDS", "pycharm": { "name": "#%% md\n" } }, "source": [ "The final step of the evaluation process is straightforward: all that needs to be done is to load the correct answers for the dev set from the provided file (`data/devGOLD`) and compare them to the matches that were generated by our function. \n", "We provide this helper function in `util.py`: it is called **`get_gold()`**.\n", "Again, you shouldn't modify it, but you can take a peek at it if you are curious what it's doing. Let's use it to read the gold (correct) matches from the provided file." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "jh-bPQ5xPhDS", "outputId": "42d4f8ed-bc1e-46c2-a5f0-d6aa0f808f92", "pycharm": { "name": "#%%\n" }, "tags": [ "exploration" ] }, "outputs": [], "source": [ "all_gold_matches = get_gold('data/devGOLD')\n", "print(all_gold_matches)" ] }, { "cell_type": "markdown", "metadata": { "id": "_kzcg2U8wy9w" }, "source": [ "As expected, these exactly match the output format that we showed earlier for the file processing function.\n", "This will make it easy to compare our answers to the gold answers, for which we provide a helper function in `util.py`, called **`score()`**.\n", "You are welcome to take a look if you are curious. \n", "It takes in a list of your predicted matches, the output of the function you will write, and a list of correct/gold matches, read from the `data/devGOLD` file.\n", "It compares the two and calculates how they overlap, printing out a bunch of information in the following form:\n", "\n", "```\n", " True Positives (4):\n", " set([('balaji', 'e', 'balaji@stanford.edu'),\n", " ('nass', 'e', 'nass@stanford.edu'),\n", " ('shoham', 'e', 'shoham@stanford.edu'),\n", " ('thm', 'e', 'pkrokel@stanford.edu')])\n", " False Positives (1):\n", " set([('psyoung', 'e', 'young@stanford.edu')])\n", " False Negatives (113):\n", " set([('ashishg', 'e', 'ashishg@stanford.edu'),\n", " ('ashishg', 'e', 'rozm@stanford.edu'),\n", " ...\n", "```\n", "\n", "You can interpret the results as follows:\n", "\n", "* **`The true positive`** section displays emails which are in\n", "both your list of matches and the gold matches list.\n", "These are examples that your regular expressions correctly found.\n", "\n", "* **`The false positive`** section displays matches which your regular expressions extracted but which are not in the gold matches list.\n", "These are incorrect and show where your method may have been too\n", "broad/aggressive.\n", "\n", "* **`The false negative`** section displays emails which your code did not match, but which do exist in the html files.\n", "These are the matches your code missed.\n", "\n", "Your goal, then, is to reduce the number of false positives and false negatives\n", "to 0.\n", "At the bottom of the output you can see the total counts of `true positives`, `false positives`, and `false negatives`." ] }, { "cell_type": "markdown", "metadata": { "id": "UN7JbRZSxzQd" }, "source": [ "Let's try evaluating our existing super-basic method using the method described above." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "IHEaWwbiPhDS", "outputId": "dbc3f1c1-4969-4c5c-af41-7dc792ca0e85", "pycharm": { "name": "#%%\n" }, "tags": [ "exploration" ] }, "outputs": [], "source": [ "guess_list = process_dir('data/dev', example_process_file)\n", "gold_list = get_gold('data/devGOLD')\n", "score(guess_list, gold_list)" ] }, { "cell_type": "markdown", "metadata": { "id": "S045DjHQPhDT", "pycharm": { "name": "#%% md\n" } }, "source": [ "Looks reasonable! It appears that our basic method produced 27 matches,\n", "while the gold set contains 110 matches.\n", "There were: \n", "* 27 `true positives`, which are matches that we found that were in the gold set;\n", "* 0 `false positives`, which are matches that we found that were NOT in the gold set;\n", "* 11 `false negatives`, which are matches in the gold set that we did NOT find.\n", "\n", "This seems like a pretty good start, but there are still 11 addresses that our\n", "approach didn't manage to catch.\n", "Figuring out how to extract these addresses without accidentally matching any non-address text is up to you!" ] }, { "cell_type": "markdown", "metadata": { "id": "RAkq1RNvdMb4" }, "source": [ "\n", "### Part 3.3. Point Distribution" ] }, { "cell_type": "markdown", "metadata": { "id": "VMPtY6q4zbwC" }, "source": [ "* The **first** part, worth 8 points, scores how well your implementation does on the\n", "development set.\n", "For these examples you're given the correct answers, so you should aim to get 100% of them correct!\n", "\n", "* The **second** part of your grade, worth 4 points, will be based on how well your\n", "regular expressions find emails in a different set of\n", "examples, the `test set`. \n", "This test set is hidden and only the teaching staff knows what is in it!\n", "Because you don't know exactly what trickery goes on in this test set, you should be creative in thinking of different ways of writing (and hiding) emails.\n", "\n", "* The **third** part is a brief section worth 1 point (0.5 for tax calculation + 0.5 for free response) designed to get you thinking about ethical issues surrounding spam emails.\n", "\n", "You are not expected to perform perfectly on the test set as you don't know\n", "what is in it, or have the correct answers (just like in real life).\n", "As long as you manage to achieve some reasonable performance (compared to a benchmark that we provide), you will get full points! \n", "The benchmark is set at **42** test errors or fewer.\n", "Normally, we would hide your test set performance so you can't tune your methods\n", "to maximize test set performance (this is good experimental procedure).\n", "However, in the interests of transparency and making your life easier, we will show you your test score and number of test errors on `Gradescope` so you can get an idea of how close you are to the benchmark and full points.\n", "\n", "You are free to submit as many times as you'd like on `Gradescope` until you hit\n", "the benchmark (or beat it!)." ] }, { "cell_type": "markdown", "metadata": { "id": "jJd8Upq0zX3m" }, "source": [ "Here are the equations we use to calculate the scores for the two parts, where\n", "`e` is the total number of errors (`false negatives` and `false positives`) for\n", "each part:\n", "\n", "__Dev:__\n", "\n", "```\n", " if e < 5 then score(e) = 8 - e\n", " else if e >= 5 then score(e) = 3\n", "```\n", "\n", "__Test:__\n", "\n", "```\n", " if e <= 42 then score(e) = 4\n", " else if 42 < e then score(e) = 4 - (e - 42) * 0.1\n", "```\n", "\n", "__Note:__ This sort of two-stage evaluation (a known development set and a\n", "hidden test set) is a very commonly used approach in machine learning!\n", "Evaluating on a development set where we have the \"right\" answers lets us\n", "measure our performance precisely and improve our approach, while a test set\n", "that is hidden from us until later allows us to see how we perform\n", "\"out in the wild\", on examples that we might not have been able to tailor\n", "our methods to." ] }, { "cell_type": "markdown", "metadata": { "id": "eNYFvxn2e9dj" }, "source": [ "\n", "## Part 4. Cases to Consider" ] }, { "cell_type": "markdown", "metadata": { "id": "icsZvzTb1Kvj" }, "source": [ "As you implement your regular expressions and analyze the `HTML` files that your approach isn't getting quite right, you will develop an understanding of which cases to consider.\n", "Your development workflow will be as follows:\n", "* You will start with a simple regular expression.\n", "* You will evaluate your simple approach against the gold matches.\n", "* You will find the files for which your approach is failing and try to identify how you can improve your regular expression to do better.\n", "* You will go back to evaluation step and repeat until you are satisfied.\n", "\n", "This is how a real life `NLP` or `ML` practioner would approach an unknown task!\n", "For our assignment, to make things a little more concrete, we are providing you with some examples to illustrate exactly what your implementation should be able to do if it's working correctly.\n", "The list we provide here is not comprehensive, so you may find out about cases that we haven't covered here." ] }, { "cell_type": "markdown", "metadata": { "id": "Sdj1BS9p3jqD" }, "source": [ "### Part 4.1. Extracting Email Addresses\n", "\n", "We are interested in processing text\n", "containing (possibly obfuscated) email addresses and returning the corresponding\n", "email addresses in a standard form.\n", "\n", "```\n", "# Ordinary email addresses\n", "manning@cs.stanford.edu => manning@cs.stanford.edu\n", "\n", "# Hidden email addresses\n", "manning(at)cs.stanford.edu => manning@cs.stanford.edu\n", "manning at csli dot stanford dot edu => manning@csli.stanford.edu\n", "```\n", "Below are some notes/questions to guide you. Make sure to account for different cases (lowercase, uppercase, mixed) for each of the following points!\n", "* Notice the different ways people write the `@` sign. \n", " Can you identify a few?\n", "* What about the alternative ways of writing `.` in emails?\n", " Make sure to account for different cases (lowercase, uppercase, mixed)!\n", "* What are some popular top level domain names?\n", " To get full credit on the section, it is sufficient to consider `com`, `gov`, `org`, `edu`.\n", " Remember to account for cases!\n", "* Are there other ways people write their emails in plain english?\n", " What are some of the common ones?" ] }, { "cell_type": "markdown", "metadata": { "id": "pnr-Lsqt3hH6" }, "source": [ "### Part 4.2. Cases to not Worry About\n", "\n", "Although you should aim to make your regexes as powerful and general-purpose as\n", "you possibly can, there are some cases that are difficult or impossible to\n", "handle with regexes and which we don't expect you to be able to deal with.\n", "\n", "These include:\n", "\n", "* Anything involving images or other non-text ways of displaying emails.\n", "* Examples that require parsing names into parts, like:.\n", "\n", "```\n", "\"first name\"@cs.stanford.edu\n", "```\n", "\n", "* Particularly clever/difficult examples that don't contain much or any\n", "part of the actual email address. For example,\n", "\n", "```\n", "To send me email, try the simplest address that makes sense.\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "hmkYu8h0fEXY" }, "source": [ "\n", "## Part 5. Your Approach" ] }, { "cell_type": "markdown", "metadata": { "id": "sn5O0_VvWp4Z" }, "source": [ "The example functions we shared so far only allows us to retrieve a subset of the present emails in our dataset.\n", "In this section, you will implement your version of the example functions, and test your implementations \n", "Your task is to modify the function **`find_emails()`** given below.\n", "We provide you with a placeholder code, but you will modify it.\n", "Here we share some notes/tips that may be helpful in your implementations:\n", "* You can use separate regular expressions for separate cases, and combine your results into a list before returning.\n", "This will make writing regular expressions easier.\n", "* You may get long regular expressions as you try to cover each email case.\n", "Don't get discouraged and make use of `|`.\n", "* Although they are mostly the same, different regular expression engines differ in subtle ways, especially true for the way escape characters etc. are interpreted.\n", "If you are using an external website to test your `RegExes`, be aware that your `RegExes` may not work out of the box when you move them over to `Python` due to this distinction." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "RZd3iDvaWpZi", "tags": [ "todo" ] }, "outputs": [], "source": [ "# TODO: Implement your approach here!\n", "def find_emails(full_text: str) -> List[str]:\n", " \"\"\"\n", " Takes in a line from an html document as a string and finds the emails in\n", " it. Returns the found emails in a list of strings. The returned email\n", " must follow the canonical format:\n", "\n", " 'someone@something'\n", "\n", " NOTE: DO NOT CHANGE THIS INTERFACE, as it will be called directly by\n", " the submit script.\n", "\n", " full_text (str): Full text of the html file read.\n", " \"\"\"\n", " # CODE START\n", " return []\n", " # CODE END" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "TJkypAsxPhDQ", "pycharm": { "name": "#%%\n" }, "tags": [ "essential" ] }, "outputs": [], "source": [ "# DO NOT CHANGE\n", "def process_file(filename: str, data_directory: str):\n", " \"\"\"\n", " Function we wrote to call the functions listed below on each line of a file \n", " with the given filename. It returns a list of 3-tuples representinting the \n", " found matches in the specified evaluation format.\n", " \n", " * find_emails()\n", "\n", " \"\"\"\n", " # DO NOT CHANGE\n", " filename_no_ext, ext = filename.split('.')\n", " absolute_file_path = os.path.join(data_directory, filename)\n", " res = []\n", " with open(absolute_file_path, 'r', encoding='ISO-8859-1') as file:\n", " # Read the full text\n", " full_text = file.read()\n", " \n", " # Call find_emails\n", " emails = [(filename_no_ext, 'e', e) for e in find_emails(full_text)]\n", " \n", " # Add the newly extracted emails to our list\n", " res += emails\n", "\n", " return res" ] }, { "cell_type": "markdown", "metadata": { "id": "ZI3zVbFp_AlK" }, "source": [ "Similar to the example functions, you can run your functions on all of the dev set and compare your found matches with the gold set matches." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "WrHaWO0gPhDT", "outputId": "ba7ee522-5184-4fa4-cc18-e7e881c6a83f", "pycharm": { "name": "#%%\n" }, "tags": [ "exploration" ] }, "outputs": [], "source": [ "guess_list = process_dir('data/dev', process_file)\n", "gold_list = get_gold('data/devGOLD')\n", "score(guess_list, gold_list)" ] }, { "cell_type": "markdown", "metadata": { "id": "qFlWbyLqBtvG" }, "source": [ "From the list above, select a file for which your approach is outputting an incorrect result, print the contents of this file using the next cell, and look into why your regular expression may not be capturing the missed emails.\n", "As you make improvements to your functions, come back to this section and repeat the process and you are satisfied with the reuslts." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "5L-1SCX1Cjde", "outputId": "94a5dee2-405e-4030-dd1b-5385b470e9f0", "tags": [ "exploration" ] }, "outputs": [], "source": [ "selected_file = 'dabo.html'\n", "result = process_file(selected_file, 'data/dev')\n", "print(result)" ] }, { "cell_type": "markdown", "metadata": { "id": "D2CHv9gjPhDT" }, "source": [ "\n", "## Part 6. Reflection" ] }, { "cell_type": "markdown", "metadata": { "id": "wo-3PXRzIPeM" }, "source": [ "\n", "**The Academic Commons.** Stop! Before you use your new RegEx skills to scrape every faculty directory on campus, consider the \"Academic Commons.\" In economics, a Common Pool Resource is a resource available to everyone (e.g., a clean lake or a professor’s inbox) that can be degraded by over-use. While it is tempting to use automation to \"mass-blast\" cold emails in hopes of securing a research assistantship, the cumulative effect of hundreds of students sending templated messages creates an \"attention tax\" that can lead to a tragedy of the commons. When an inbox is flooded with automated outreach, a professor’s limited time and attention are depleted, often causing them to ignore all cold emails entirely.\n", "\n", "The Scenario:\n", "\n", "Consider the following estimates for Stanford CS in 2025-2026:\n", "- **The Class (N):** There are **300** students in CS 124.\n", "- **The Faculty (M):** There are **100** active research faculty in the department.\n", "- **The Tax (T):** It takes a professor **15 seconds** to read a subject line, realize a message is a templated \"mass-email,\" and archive it.\n", "\n", "If every student in CS 124 sends just one templated cold email to every CS professor at the start of the quarter, calculate the Total Faculty Time (in hours) consumed by the department just to process and delete these 30,000 emails.\n", "\n", "Note: Use 1 hour = 3600 seconds.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "kMfFlyQiPhDT", "tags": [ "todo" ] }, "outputs": [], "source": [ "# TODO: Modify this function so that it returns your solution\n", "def calculate_attention_tax():\n", " \"\"\"\n", " Calculate the total hours of faculty time consumed if \n", " 300 students each email 100 professors, \n", " and each email takes 15 seconds to delete.\n", " \"\"\"\n", " total_hours = 0\n", " # CODE START\n", " \n", " # CODE END\n", " return total_hours\n" ] }, { "cell_type": "markdown", "metadata": { "id": "1t7mdeFCPhDT" }, "source": [ "\n", "**Fairness in the Commons.** When the \"Academic Commons\" is flooded with automated outreach, it creates a **fairness challenge**. Professors may develop \"email fatigue,\" leading them to ignore all cold emails, including those from students who spent hours researching a professor’s specific publications to write a thoughtful, personalized message.\n", "\n", "Your Task:\n", "\n", "Please provide a 3-6 sentence response addressing the following:\n", "- How does the use of mass personalization by LLMs for cold emails create an unfair disadvantage for students who write highly personalized, non-automated messages?\n", "- If professors stop responding to cold emails entirely due to high volume, which groups of students are most negatively impacted?\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "Dlt3_JfZPhDU", "tags": [ "todo" ] }, "outputs": [], "source": [ "# TODO: Write your response in the response string below\n", "def fairness_response():\n", " response = \"\"\n", " return response" ] }, { "cell_type": "markdown", "metadata": { "id": "part1b_title" }, "source": [ "# Section B: BPE Tokenization\n", "\n", "In this part of the assignment, you will implement a BPE tokenizer from scratch.\n", "In particular, we will represent arbitrary (Unicode)\n", "strings as a sequence of bytes and train our BPE tokenizer on this byte sequence. Later, we will use this\n", "tokenizer to encode text (a string) into tokens (a sequence of integers) for language modeling.\n", "\n", "Acknowledgement: This assignment is adapted from CS336." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## Contents\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Listed below are the contents of the BPE Tokenization portion. In the `The Unicode Standard` part, you will learn about Unicode code points and how characters are represented. In the `Unicode Encodings` part, you will learn about UTF-8 encoding and how to convert text to bytes. In the `Subword Tokenization` part, you will understand why subword tokenization is preferred over word-level or character-level approaches. In the `BPE Tokenizer Training` part, you will learn how to train a BPE tokenizer on a corpus. In the `Encoding Text` part, you will implement functions to encode text into token IDs. In the `Decoding Text` part, you will implement functions to decode token IDs back to text. Please read through all of Section B: BPE Tokenization before you start working through this section. \n", "\n", "* [`Part 1. The Unicode Standard`](#unicode_standard)\n", "* [`Part 2. Unicode Encodings`](#unicode_encodings)\n", "* [`Part 3. Subword Tokenization`](#subword_tokenization)\n", "* [`Part 4. BPE Tokenizer Training`](#bpe_training)\n", "* [`Part 5. Encoding Text`](#encoding_text)\n", "* [`Part 6. Decoding Text`](#decoding_text)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## Roadmap" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As an overview, there are only `3` functions you need to implement in this section:\n", "* In `Part 5. Encoding Text`: **[`encode_chunk_no_special_tokens()`](#encode_chunk_no_special_tokens)** and **[`encode()`](#encode)**\n", "* In `Part 6. Decoding Text`: **[`decode()`](#decode)**.\n", "\n", "Although you will only write code at the end of this section, you should read through the entire section (especially the code samples) to understand how BPE tokenization works, how bytes and merges are handled, and how the different variables fit together. A much shorter implementation is needed for **`decode()`**.\n" ] }, { "cell_type": "markdown", "metadata": { "id": "L98XWjQyjUw8" }, "source": [ "\n", "## Part 1. The Unicode Standard" ] }, { "cell_type": "markdown", "metadata": { "id": "F8srZPWSq5IQ" }, "source": [ "**Unicode** is a text encoding standard that maps characters to integer code points. As of Unicode 16.0 (released in Sep. 2024), the standard defines `154,998` characters across `168` scripts. \n", "\n", "For example, the character `“s”` has the code point `115` (typically notated as `U+0073`, where `U+` is a conventional prefix and `0073` is `115` in hexadecimal), and the character `“牛”` has the code point `29275`. \n", "\n", "In Python,\n", "- The `ord()` function converts a single Unicode character into its integer representation.\n", "- The `chr()` function converts an integer Unicode code point into a string with the corresponding character." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "id": "Ta65JviGPhDP", "pycharm": { "name": "#%%\n" } }, "outputs": [], "source": [ "# Example:\n", "ord('牛')\n", "chr(29275)" ] }, { "cell_type": "markdown", "metadata": { "id": "F2XMkt-APhDQ" }, "source": [ "\n", "## Part 2. Unicode Encodings" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "While the Unicode standard defines a mapping from **characters to code points (integers)**, it’s impractical to\n", "train tokenizers directly on Unicode codepoints, since the vocabulary would be **prohibitively large** (around\n", "`150K` items) and **sparse** (since many characters are quite rare). \n", "\n", "Instead, we’ll use a `Unicode encoding`, which\n", "converts a Unicode character into a **sequence of bytes**. The Unicode standard itself defines three encodings:\n", "`UTF-8`, `UTF-16`, and `UTF-32`, with `UTF-8` being the dominant encoding for the Internet (more than 98%\n", "of all webpages).\n", "\n", "Unicode encodings in Python work as follows:\n", "- To encode a Unicode string into `UTF-8`, we can use the `encode()` function in Python. \n", "- To access the underlying byte values for a Python bytes object, we can iterate over it (e.g., call `list()`). \n", "- Finally, we can use the `decode()` function to decode a `UTF-8` byte string into a Unicode string." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Example:\n", "test_string = \"hello! こんにちは!\"\n", "utf8_encoded = test_string.encode(\"utf-8\")\n", "print(utf8_encoded)\n", "print(type(utf8_encoded))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Get the byte values for the encoded string (integers from 0 to 255).\n", "print (list(utf8_encoded))\n", "print (len(test_string))\n", "print (len(utf8_encoded))\n", "print (utf8_encoded.decode(\"utf-8\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "By converting our **Unicode** codepoints into a sequence of **bytes** (e.g., via the `UTF-8` encoding), we\n", "are essentially taking a sequence of **codepoints** (integers in the range `0` to `154,997`) and transforming it\n", "into a sequence of **byte values** (integers in the range `0` to `255`). The `256`-length byte vocabulary is much\n", "more manageable to deal with. \n", "\n", "When using byte-level tokenization, we do not need to worry about **out-of-vocabulary** tokens, since we know that \n", "any input text can be expressed as a sequence of integers from `0` to `255`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## Part 3. Subword Tokenization" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "While **byte-level tokenization** can alleviate the **out-of-vocabulary** issues faced by word-level tokenizers, tokenizing text into bytes results in extremely long input sequences that: \n", "- slows down model training (a sentence with 10 words might be 10 tokens in a word-level model but 50+ tokens in a byte-level model)\n", "- requires more computation at each step\n", "- creates longer dependencies in the data.\n", "\n", "**Subword tokenization** is a midpoint between word-level and byte-level tokenizers. A subword tokenizer trades off a larger vocabulary size for better compression of the input byte sequence. For example, if the byte sequence `b\"the\"` often occurs in our training data, assigning it an entry in the vocabulary would reduce this `3-token sequence` to a `single token`.\n", "\n", "**How do we select these subword units to add to our vocabulary?** Sennrich et al. [2016] propose to use `Byte Pair Encoding (BPE)` (Gage, 1994), a compression algorithm that *iteratively merges the most frequent pair of bytes with a single, new unused token*. If a word occurs in our input text enough times, it'll be represented as a single subword unit.\n", "\n", "In this assignment, we'll implement a **byte-level BPE tokenizer**, where the vocabulary items are bytes or merged sequences of bytes, which gives us the best of both worlds: out-of-vocabulary handling and manageable input sequence lengths. The process of constructing the BPE tokenizer vocabulary is known as **\"training\"** the BPE tokenizer." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## Part 4. BPE Tokenizer Training" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The BPE tokenizer training procedure consists of 3 main steps:\n", "1. **Vocabulary initialization** (bytes + special tokens)\n", "2. **Pre-tokenization**\n", "3. **Perform BPE merges**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Vocabulary initialization \n", "For a byte-level BPE tokenizer, the initial vocabulary consists of all `256` possible byte values, each mapped to a unique token ID." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Initialize with all 256 possible byte values\n", "vocab = {i: bytes([i]) for i in range(256)}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "***Special tokens.*** Some strings (e.g., `<|endoftext|>`) encode metadata such as document boundaries and should always be treated as a single token. These “special tokens” are never split during encoding and are added to the vocabulary with fixed token IDs." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Add special tokens to the vocabulary\n", "special_tokens = [\"<|endoftext|>\"]\n", "for i, special_token in enumerate(special_tokens):\n", " vocab[256 + i] = special_token.encode(\"utf-8\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Pre-tokenization\n", "\n", "Directly merging frequent byte pairs over the full corpus:\n", "- is **computationally expensive**: it would take a full pass of the corpus each merge.\n", "- can **produce redundant tokens** that differ only by punctuation (e.g., dog! vs. dog.) that may have different token IDs despite semantic similarity. \n", "\n", "To address this we **pre-tokenize** the corpus into coarse-grained tokenization, and then later count how often pairs of characters appear. For example, if the *pre-token* `text` appears `10` times, the pair (`t`, `e`) is incremented by `10` instead of rescanning the corpus. Since this is a byte-level BPE model, each *pre-token* is represented as a sequence of UTF-8 bytes.\n", "\n", "\n", "The original BPE method (Sennrich et al., 2016) splits on `whitespace`. Instead, we use the GPT-2 `regex-based` pre-tokenizer (Radford et al., 2019) from github.com/openai/tiktoken/pull/234/files." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import regex as re\n", "\n", "## We will use this regex pattern to pre-tokenize the corpus\n", "PAT = r\"\"\"'(?:[sdmt]|ll|ve|re)| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)|\\s+\"\"\"\n", "re.findall(PAT, \"some text that i'll pre-tokenize\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from collections import defaultdict, Counter\n", "\n", "pattern = re.compile(\n", " r\"\"\"'(?:[sdmt]|ll|ve|re)| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)|\\s+\"\"\",\n", " re.UNICODE\n", " )\n", "\n", "with open(\"data/corpus.en\", \"r\") as f:\n", " corpus = f.read()\n", "\n", "# Pre-tokenize the corpus\n", "total_counter = Counter()\n", "parts = corpus.split(\"<|endoftext|>\") # Split on special tokens\n", "\n", "# Counting how often each pre-token appears\n", "for part in parts:\n", " if part:\n", " total_counter += Counter(re.findall(pattern, part))\n", "\n", "print (total_counter)\n", "\n", "# Convert string tokens to bytes and store counts\n", "pre_token_counts = {}\n", "for token, count in total_counter.items():\n", " pre_token_counts[token.encode('utf-8')] = count\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Compute BPE merges\n", "Once the corpus is pre-tokenized and each pre-token is represented as UTF-8 bytes, we \"train\" the BPE tokenizer by repeatedly merging the most frequent adjacent byte pairs. Each merge creates a new token and expands the vocabulary.\n", "\n", "1. Count pairs. Count all adjacent byte pairs within each pre-token.\n", " - For efficiency, we do not consider pairs that cross pre-token boundaries.\n", "2. Merge. Select the most frequent pair (“A”, “B”) and replace every occurrence with a new token “AB”, adding it to the `vocabulary`.\n", " - If multiple pairs tie, merge the lexicographically greatest pair (e.g., among (“A”, “B”), (“A”, “C”), (“B”, “ZZ”), and (“BA”, “A”), choose (“BA”, “A”)). For example, this line behlow selects the exicographically greatest pair:\n", "\n", " max([(\"A\", \"B\"), (\"A\", \"C\"), (\"B\", \"ZZ\"), (\"BA\", \"A\")])\n", "3. Repeat. The final vocabulary size is `initial vocabulary size (256 in our case) + the number of merges`. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The next 4 code blocks below show the full implementation of training. *It has many components, and while you do not need to understand it in depth, it is helpful to understand the overall approach.* It is also important to note the `merges` variable: this stores the sequence of merge operations learned during training." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Setup for BPE Training\n", "We first convert each pre-token in `pre_token_counts` into a tuple of single-byte symbols and stores it in `pre_token_tuple_counts`, weighted by its frequency. These byte-level sequences are the representation used for counting merge pairs in BPE training." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "vocab_size = 500\n", "pre_token_tuple_counts = {}\n", "merges = []\n", "\n", "# Convert each pre-token (bytes) into a tuple of single-byte symbols,\n", "# weighted by its frequency. This is the representation used for BPE pair counting.\n", "for token_bytes, count in pre_token_counts.items():\n", " token_tuple = tuple(token_bytes[i : i+1] for i in range(len(token_bytes)))\n", " pre_token_tuple_counts[token_tuple] = pre_token_tuple_counts.get(token_tuple, 0) + count\n", "\n", "print (pre_token_tuple_counts)\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Then we iterate over each byte-level token in `pre_token_tuple_counts` and count how often each adjacent byte pair appears, weighted by token frequency. The result, `pair_freq`, records which byte pairs are most common and therefore candidates for BPE merges." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "## Count frequencies of adjacent byte pairs (within pre-tokens) for BPE merging\n", "pair_freq = Counter()\n", "for token_tuple, count in pre_token_tuple_counts.items():\n", " if len(token_tuple) < 2:\n", " continue\n", " for i in range(len(token_tuple) - 1):\n", " pair = (token_tuple[i], token_tuple[i+1])\n", " pair_freq[pair] += count\n", "\n", "print (pair_freq)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next, we compute the maximum number of BPE merge operations allowed. The result, `max_merges`, limits how many merges can be learned." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "## Calculate maximum allowed merge operations:\n", "# The final vocabulary consists of:\n", "# 256 initial byte tokens + len(special_tokens) + number_of_merges\n", "# So we can rearrange:\n", "max_merges = vocab_size - len(special_tokens) - 256\n", "\n", "print (max_merges)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### BPE Training Loop" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, the training loop runs until `len(merges) == max_merges`: it selects the most frequent adjacent pair from `pair_freq` as `best_pair` and appends it to `merges`. There is a little more here, but this is the core of the idea. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "while len(merges) < max_merges:\n", " print (\"current vocab size: \", len(vocab))\n", " # Find the most frequent pair; in case of ties, choose the lexicographically greater pair.\n", " best_pair, best_count = None, 0\n", " for pair, freq in pair_freq.items():\n", " if freq > best_count or (freq == best_count and (best_pair is None or pair > best_pair)):\n", " best_pair, best_count = pair, freq\n", " \n", " # Record the merge \n", " merges.append(best_pair)\n", " print (\"best pair to be merged: \", best_pair)\n", "\n", " # Update the vocabulary with the new merged token \n", " merged_token = best_pair[0] + best_pair[1]\n", " next_id = len(vocab)\n", " vocab[next_id] = merged_token\n", "\n", " # Update the tokens by merging occurrences of the best pair \n", " new_token_tuple_counts = {}\n", " for token_tuple, count in pre_token_tuple_counts.items():\n", " i = 0\n", " while i < len(token_tuple) - 1:\n", " pair = (token_tuple[i], token_tuple[i+1])\n", " if pair == best_pair:\n", " prefix = token_tuple[:i]\n", " suffix = token_tuple[i+2 : ]\n", " token_tuple = prefix + (merged_token,) + suffix\n", " \n", " if prefix: \n", " left_pair = (prefix[-1], merged_token)\n", " pair_freq[left_pair] = pair_freq.get(left_pair, 0) + count \n", " del_pair = (prefix[-1], best_pair[0])\n", " pair_freq[del_pair] -= count \n", " \n", " if suffix:\n", " right_pair = (merged_token, suffix[0])\n", " pair_freq[right_pair] = pair_freq.get(right_pair, 0) + count \n", " del_pair = (best_pair[1], suffix[0])\n", " pair_freq[del_pair] -= count\n", " \n", " pair_freq[best_pair] -= count \n", " i += 1\n", " new_token_tuple_counts[token_tuple] = count\n", " pre_token_tuple_counts = new_token_tuple_counts\n", "\n", " del pair_freq[best_pair]\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Validation\n", "We compare **our learned** BPE merges and vocabulary against a **reference** implementation by decoding GPT-2’s byte encoding and asserting that both the merges and vocab entries match." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Test our trained tokenizer with the references\n", "reference_vocab_path = \"data/train-bpe-reference-vocab.json\"\n", "reference_merges_path = \"data/train-bpe-reference-merges.txt\"\n", "\n", "from util import gpt2_bytes_to_unicode\n", "\n", "# Compare the learned merges to the expected output merges\n", "gpt2_byte_decoder = {v: k for k, v in gpt2_bytes_to_unicode().items()}\n", "with open(reference_merges_path) as f:\n", " gpt2_reference_merges = [tuple(line.rstrip().split(\" \")) for line in f]\n", " reference_merges = [\n", " (\n", " bytes([gpt2_byte_decoder[token] for token in merge_token_1]),\n", " bytes([gpt2_byte_decoder[token] for token in merge_token_2]),\n", " )\n", " for merge_token_1, merge_token_2 in gpt2_reference_merges\n", " ]\n", "assert merges == reference_merges\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import json \n", "# Compare the vocab to the expected output vocab\n", "with open(reference_vocab_path) as f:\n", " gpt2_reference_vocab = json.load(f)\n", " reference_vocab = {\n", " gpt2_vocab_index: bytes([gpt2_byte_decoder[token] for token in gpt2_vocab_item])\n", " for gpt2_vocab_item, gpt2_vocab_index in gpt2_reference_vocab.items()\n", " }\n", "# Rather than checking that the vocabs exactly match (since they could\n", "# have been constructed differently, we'll make sure that the vocab keys and values match)\n", "assert set(vocab.keys()) == set(reference_vocab.keys())\n", "assert set(vocab.values()) == set(reference_vocab.values())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## Part 5. Encoding Text" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following two parts (Part 5: Encoding Text and Part 6: Decoding Text) are where you will implement the functions that will be graded for this section:\n", "\n", "* **Encoding** (10 points): Implementation of encoding functions in Part 5\n", " * `encode_chunk_no_special_tokens()`\n", " * `encode()`\n", "* **Decoding** (3 points): Implementation of `decode()` function in Part 6\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the previous part (BPE Tokenizer Training), we implemented a function to train a BPE tokenizer on input text\n", "to obtain a tokenizer vocabulary and a list of BPE merges. Now, we will implement a BPE tokenizer that\n", "loads a provided vocabulary and list of `merges` (BPE Tokenizer Training) from and uses them to encode and decode text to/from token IDs.\n", "\n", "The process of encoding text with BPE mirrors training:\n", "\n", "1. **Pre-tokenize:** Split text into pre-tokens and represent them as UTF-8 bytes. \n", "2. **Apply merges:** Apply the learned `merges` in the order they were created. \n", "3. **Special tokens:** Preserve user-defined special tokens during encoding.\n", "\n", "Now let's use our tokenizer to encode some text from `tinystories_sample.txt`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Your Task: Implement BPE Encoding\n", "\n", "You will implement **two encoding functions** that follow the steps above and convert text into token IDs using a trained BPE vocabulary and merge list.\n", "You should reuse the `merges` Python variable learned during training and apply them in order (no retraining or frequency counting during encoding).\n", "\n", "\n", "#### **1. `encode_chunk_no_special_tokens`**\n", "\n", "Encode a single text chunk **without special tokens**.\n", "\n", "Your implementation should:\n", "\n", "* Pre-tokenize the text using the same regex pattern (from `pattern`) as during training.\n", "* Encode each pre-token to UTF-8 bytes (see [`Part 2. Unicode Encodings`](#unicode_encodings) for encoding) and split into individual bytes (creating a list of bytes called `parts`).\n", "* Apply the BPE `merges` **in the same order as training** to `parts`.\n", "* Map each merged byte sequence to token IDs using the vocabulary.\n", "\n", "Assumptions:\n", "* The input contains **no special tokens**.\n", "* Only **one chunk** is encoded at a time.\n", "\n", "You are given helper function `_apply_merge` already written below.\n", "\n", "\n", "\n", "#### **2. `encode`**\n", "\n", "Encode a full text string **with special token support** (e.g., `<|endoftext|>`).\n", "\n", "Your implementation should:\n", "\n", "* If `special_tokens=False`, call `encode_chunk_no_special_tokens` directly.\n", "* Otherwise:\n", "\n", " * Locate all occurrences of the special token. Consider a list of (start, end) tuples.\n", " * Split the text into chunks between special tokens.\n", " * Encode each chunk separately, using `encode_chunk_no_special_tokens.`\n", " * When encoding, insert the special token’s ID at the correct positions.\n", "\n", "You may assume that `<|endoftext|>` is the only special token.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from typing import Dict, List, Tuple, Set\n", "\n", "# Helper function to apply merges\n", "def _apply_merge(parts: List[bytes], pair: Tuple[bytes, bytes]) -> List[bytes]:\n", " \"\"\"\n", " Apply a single merge operation to a sequence of byte parts.\n", " \n", " Args:\n", " parts (List[bytes]): The sequence of byte parts.\n", " pair (Tuple[bytes, bytes]): The pair of byte sequences to merge.\n", " \n", " Returns:\n", " List[bytes]: The sequence after applying the merge.\n", " \"\"\"\n", " first, second = pair\n", " i = 0\n", " result = []\n", "\n", " while i < len(parts):\n", " # Try to find the first part of the pair \n", " if i < len(parts) - 1 and parts[i] == first and parts[i+1] == second:\n", " # Merge the pair \n", " result.append(first + second)\n", " i += 2\n", " else:\n", " # Keep the current part \n", " result.append(parts[i])\n", " i += 1\n", " return result\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# encode a text chunk without special tokens\n", "def encode_chunk_no_special_tokens(text, merges, vocab):\n", " \"\"\"\n", " Encode a text string into a list of token IDs.\n", " Assume we are only getting one chunk at a time. \n", " Assume there are no special tokens in the text.\n", " \n", " Args:\n", " text (str): The text to encode.\n", " merges (List[Tuple[bytes, bytes]]): The list of merges from BPE training.\n", " vocab (Dict[int, bytes]): The vocabulary from BPE training.\n", " \n", " Returns:\n", " List[int]: A list of token IDs.\n", " \"\"\"\n", " # TODO: Pre-tokenize the text using the same regex pattern as during training\n", " # TODO: Process each pre-token:\n", " # - Convert pre-token to bytes using .encode(\"utf-8\")\n", " # - Split into individual bytes\n", " # - Apply the BPE merges from the learned `merges` list from training\n", " # - Convert merged parts to token IDs using the vocab\n", " \n", " pass # TODO: Remove this and implement the function\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def encode(text, merges, vocab, special_tokens=True):\n", " \"\"\"\n", " Encode a text string into a list of token IDs, handling multiple special tokens.\n", " You may assume that `<|endoftext|>` is the ONLY special token.\n", " \n", " Args:\n", " text (str): The text to encode.\n", " merges (List[Tuple[bytes, bytes]]): The list of merges from BPE training.\n", " vocab (Dict[int, bytes]): The vocabulary from BPE training.\n", " special_tokens: Whether to handle special tokens.\n", " \n", " Returns:\n", " List[int]: A list of token IDs.\n", " \"\"\"\n", " if not special_tokens:\n", " return encode_chunk_no_special_tokens(text, merges, vocab)\n", " \n", " # TODO: Get the special token ID\n", " # TODO: Locate all positions of the special token in the text. Consider keeping track of a list of (start, end) tuples\n", " # TODO: Encode each chunk (text between located special tokens) separately using `encode_chunk_no_special_tokens`\n", " # TODO: When encoding, insert special token's ID at the appropriate positions\n", " \n", " pass # TODO: Remove this and implement the function\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let's put everything together to encode some text from `tinystories_sample.txt`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "corpus_path = \"data/tinystories_sample.txt\"\n", "\n", "with open(corpus_path, \"r\") as f:\n", " corpus_contents = f.read()\n", "\n", "ids = encode(corpus_contents, merges, vocab, special_tokens=True)\n", "\n", "print(ids)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## Part 6. Decoding Text" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Your Task: Implement Decoding\n", "\n", "Now that we have our encoded `ids` we will decode them back into raw text.\n", "\n", "\n", "#### **`decode`**\n", "\n", "To decode a sequence of **integer token IDs** back to **raw text**, we:\n", "1. Look up each ID’s corresponding entries in the vocabulary (a byte sequence)\n", "2. Concatenate them together\n", "3. Decode the bytes to a Unicode string (see [`Part 2. Unicode Encodings`](#unicode_encodings) for decoding)\n", "\n", "Note that input IDs are not guaranteed to map to valid Unicode strings (since a user\n", "could input any sequence of integer IDs). The additional argument of `errors='replace'` in `.decode()` handles this case and replaces invalid byte sequences with the Unicode replacement character (U+FFFD).\n", "\n", "Tip: Initialize a variable with `b''` (not a regular string `''`) when building byte sequences" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def decode(token_ids, vocab):\n", " \"\"\"\n", " Decode a list of token IDs back to a text string.\n", " \n", " Args:\n", " token_ids (List[int]): The list of token IDs to decode.\n", " vocab (Dict[int, bytes]): The vocabulary from BPE training.\n", " \n", " Returns:\n", " str: The decoded text.\n", " \"\"\"\n", " # TODO: Convert each token ID to its corresponding bytes using the vocab\n", " # TODO: Concatenate all the bytes together\n", " # TODO: Decode the bytes back to a UTF-8 string\n", " \n", " return \"\" # TODO: Remove this and implement the function\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's try our function; we should get the story from `tinystories_sample.txt`!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print (decode(ids, vocab))" ] }, { "cell_type": "markdown", "metadata": { "id": "2O2n-GyiIIVT" }, "source": [ "\n", "# Ending Remarks" ] }, { "cell_type": "markdown", "metadata": { "id": "8pI3K3ewfb2g" }, "source": [ "Congratulations, you are done with the assignment!\n", "Refer to the [`Submitting`](#submitting) for submission instructions." ] } ], "metadata": { "celltoolbar": "Tags", "colab": { "collapsed_sections": [ "e4gZzwRnPpWw", "PnnkT9eMhBlJ", "D2CHv9gjPhDT" ], "name": "pa1 (New) (Solution).ipynb", "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.10.19" } }, "nbformat": 4, "nbformat_minor": 4 }