Words and tokens

AOverview

This lecture answers a question that looks too simple to matter: what is a word, and how do you cut text into them? It starts with one picnic sentence that has 16 tokens under one policy and 18 under another, and it ends with a table that measures how far one string sits from another. Between the two lies the whole working surface of natural language processing: counting units, the two laws that govern their frequencies, the meaningful parts inside them, the bytes that carry any script, the algorithms that learn units from data, the patterns that find them, and the distance that compares them.

As a PhD student you need it in three places. Exam questions ask you to compute, not to recall: give N and|V| for a sentence under a stated policy, fit |V| = k N^beta to a corpus and read off a prediction, run four BPE merges by hand and state your tie rule, encode a code point into UTF-8 bytes, and fill an edit distance table cell by cell. Your research will depend on every one of these choices, because a vocabulary, a normalization scheme and a tokenizer are design decisions you will have to state and defend in any paper, and Arabic in particular makes them visible through templatic morphology, clitics and a rich orthography. And any system you build or review consumes tokens, so the cost, the coverage and the failure modes of the tokenizer are the first properties of the model you should be able to explain.

The path has five stops. You learn to count units and see that frequency and vocabulary follow two laws that make rare words unavoidable. You look inside those units for the meaningful parts that explain why a single lemma multiplies into many forms. You follow characters down to bytes so that no script is ever unrepresentable. You watch an algorithm learn its own units from data by merging the most frequent pair, and then see what a real tokenizer does with that algorithm in production. Finally you learn the pattern language that finds units and the distance that compares them, which is the dynamic programming pattern the rest of the course reuses.

Success looks like

• Compute the token and type counts N and |V| for a given string under a stated policy for case and punctuation, and explain why the same sentence gives two answers.
• State Zipf's law and Heaps' law, move between rank, frequency and vocabulary size with f(R) and |V| = k N^beta, and argue from them why OOV items are guaranteed.
• Segment a word into morphemes, label each as root or affix and free or bound, and tell inflection from derivation on a new example.
• Apply the selectivity and paradigm diagnostics to place a form as clitic or affix, and locate a language on the typology axes with an example.
• Distinguish code point, glyph and encoding, normalize a decomposed string, and encode any code point into UTF-8 bytes by hand.
• Run the BPE trainer and the encoder on a small corpus, list the vocabulary, state the tie rule, and explain why merge order decides the units of unseen text.
• Read and write a regular expression for a tokenization rule, and fill an edit distance table by hand to return a distance and an alignment under a stated cost convention.

How to study this lecture

1. Choose your route. Read the full guide in one sitting for the big picture, or work through one part at a time when you want depth.
2. Answer every recall prompt in your head, or on paper, before you reveal it. Counting, merging and encoding only stick if you do them by hand, and each is worth attempting cold first.
3. Take each quiz and read the explanation even when you are right. The explanations carry the distinctions an examiner probes, such as inflection against derivation or NFC against NFKC.
4. Use the simulators: count tokens and types, trace BPE merges, tokenize a real sentence, and fill the edit distance grid. Watching a decision go wrong is faster than reading that it can.
5. Practise every computation under both conventions once, unit costs and cost 2 substitutions, so the exam convention never surprises you.
6. Mark a concept as understood only when you could explain it to a classmate without looking. Unmarked concepts show you where to return.
7. Come back after a few days and retry the recall prompts and quizzes cold. Spaced practice builds the long-term memory an exam needs.

BThe 11 parts

1. 01What counts as a wordWhy a word is not a universal unit, the difference between tokens and types, how corpus vocabularies compare, and the preprocessing decisions every tokenizer must make.4 conceptsSlides 1-1024 min
   1. 1.1The lecture in one map: eight stops from words to edit distance
   2. 1.2A word is a design decision, not a fact of nature
   3. 1.3Tokens versus types, and why |V| keeps growing
   4. 1.4The preprocessing checklist and its ambiguous boundaries
2. 02Zipf and Heaps: the shape of vocabularyTwo empirical laws that explain why a few words are everywhere, most words are rare, and vocabulary never stops growing, and why that pushes NLP toward subword units.4 conceptsSlides 11-1624 min
   1. 2.1Zipf's law: a few words carry most of the text
   2. 2.2Why a power law is a straight line, and where real corpora bend
   3. 2.3Heaps' law: the vocabulary never stops growing
   4. 2.4Why it matters: OOV, hapax legomena and the case for subwords
3. 03Morphemes: the parts of wordsThe smallest meaning-bearing units, roots and affixes, inflection versus derivation, and how English concatenation differs from Arabic root-and-pattern morphology.3 conceptsSlides 17-2118 min
   1. 3.1Morphemes: roots carry the meaning, affixes attach to them
   2. 3.2Inflection keeps the lexeme, derivation makes a new one
   3. 3.3Concatenative strings pieces in a line, non-concatenative changes the inside
4. 04Clitics and morphological typologyWhy some attached pieces are words in disguise, how to tell a clitic from an affix, and where languages sit between isolating and polysynthetic, with English and Arabic placed on the map.3 conceptsSlides 22-2818 min
   1. 4.1Clitics: words in syntax, attached in sound, and the selectivity test
   2. 4.2Morphological typology: four tendencies, not four boxes
   3. 4.3Morphemes per word, and why it decides your tokenizer
5. 05Corpora, Unicode and UTF-8What a corpus is and why it must be documented, how Unicode names every character with a code point, and how UTF-8 packs code points into bytes that any model can consume.4 conceptsSlides 29-3724 min
   1. 5.1A corpus is a situated sample, so it needs a data statement
   2. 5.2Code points are numbers, glyphs are pictures, and normalization keeps them consistent
   3. 5.3UTF-8 packs a code point into one to four self-describing bytes
   4. 5.4Why bytes are the universal fallback for tokenizers
6. 06Tokenization units and byte-pair encodingWords, characters or subwords as the unit of text, the tradeoffs among them, and the BPE algorithm that learns a subword vocabulary by merging frequent pairs, traced by hand on a toy corpus.5 conceptsSlides 38-4830 min
   1. 6.1What a tokenizer must balance
   2. 6.2Words, characters and subwords: the trade-offs
   3. 6.3The BPE trainer: merge the most frequent adjacent pair, k times
   4. 6.4Tracing four merges on 'set new new renew reset renew'
   5. 6.5The BPE encoder: replay the merges in order on new text
7. 07Tokenizers in practice and sentence segmentationPre-tokenizers, byte-level BPE, multilingual fairness, SuperBPE, the design checklist for a real tokenizer, and the related problem of finding sentence boundaries.4 conceptsSlides 49-5524 min
   1. 7.1From the BPE algorithm to a shipping tokenizer
   2. 7.2Who pays for a shared vocabulary, and merging across spaces
   3. 7.3The design checklist: every switch has a consequence
   4. 7.4Sentence segmentation: the period is the hard case
8. 08Regular expressions: the core syntaxFrom ELIZA's pattern rules to the building blocks of regular expressions: literals, bracket classes, ranges, negation, quantifiers, wildcards, anchors and the backslash aliases.4 conceptsSlides 56-6524 min
   1. 8.1ELIZA: a conversation built from pattern substitutions
   2. 8.2Literals, disjunction and the square-bracket class
   3. 8.3Counting, the wildcard, and greedy versus lazy
   4. 8.4Anchors and the six aliases
9. 09Regular expressions in practiceEscaping, precedence and groups, substitutions with backreferences, lookarounds, the cheat sheets, the GPT-2 pre-tokenizer regex, and the engineering habits that keep patterns correct and fast.6 conceptsSlides 66-7836 min
   1. 9.1Escaping metacharacters and the precedence ladder
   2. 9.2Composing patterns, capture groups, substitution and lookahead
   3. 9.3The slide 72 practice set, solved
   4. 9.4The cheat sheet as reference tables
   5. 9.5The GPT-2 pre-tokenizer: a regex as the first pass of BPE
   6. 9.6Engineering regexes: error analysis, tests, Unicode, backtracking
10. 10Minimum edit distance: alignments and searchMeasuring how far apart two strings are with insertions, deletions and substitutions, seeing the answer as an alignment, and recognizing the problem as a shortest path that dynamic programming solves.4 conceptsSlides 79-8624 min
    1. 10.1Edit distance: three operations that measure how far apart two strings are
    2. 10.2The alignment view: a distance is a set of columns you can read and cost
    3. 10.3From an exploding search tree to a grid of prefix pairs
    4. 10.4The recurrence, its initialization, and what a cost function can encode
11. 11Filling the DP table and recovering the alignmentThe full algorithm, a cell by cell computation for intention to execution, backpointers and backtrace to read off the alignment, the time and space complexity, and the lecture in one page.5 conceptsSlides 87-9430 min
    1. 11.1One edit at a time: the path that the table will rebuild
    2. 11.2Filling D cell by cell: initialization, three candidates, one minimum
    3. 11.3Backpointers: reading the arrows back to the origin
    4. 11.4What the table costs: O(mn) time, and how little space you really need
    5. 11.5The lecture in seven lines, and where it came from

CGlossary and reference

• GlossaryEvery term from the lecture, defined once, with links back to the slides that use it.
• Reference sheetThe lecture on one printable page, for revision before a quiz or exam.