Deep NLP

7 episodes · follows chapter 2 of the textbook

Words and Tokens

What is a "word", and what does a model actually read? This module starts from counting (types, instances, Heaps' and Zipf's power laws), descends to the bytes underneath text (Unicode, UTF-8, normalization), treats regular expressions as the finite machines they are, and then builds the tokenizer every modern LLM uses: byte-pair encoding, learned by greedy compression and applied by a merge table. It closes with minimum edit distance as dynamic programming and the noisy-channel spelling corrector, the course's first Bayesian decoder.

Progress — loading…

Objectives

Language

  • Distinguish word types from word instances; explain why vocabulary never stops growing
  • Explain why whitespace tokenization fails for Chinese, Japanese and Thai, and why NFC vs NFD changes token ids
  • Explain how BPE learns subwords, why pretokenization exists, and how tokenization causes 'strawberry' and arithmetic failures and cross-language cost inequity
  • Correct spelling with a noisy-channel model and diagnose its errors

Math & data structures

  • Power laws and log-log linearization; least-squares line fitting in closed form and by gradient descent
  • Code points, UTF-8 bit layout and validity rules; canonical vs compatibility equivalence
  • Regular expressions as NFAs (Thompson construction), set simulation vs backtracking, subset construction and DFA blowup
  • Hash maps, inverted indexes and lazy-deletion heaps for incremental BPE
  • Dynamic programming with backpointers: Wagner-Fischer edit distance, alignment, O(nm) time, two-row space
  • Bayes' rule in log space: prior x likelihood, add-alpha smoothing of confusion counts

Code

  • Heaps/Zipf measurement and fitting with a logged gradient-descent run
  • UTF-8 encoder/validating decoder; grapheme and normalization tools
  • Thompson NFA from scratch; Unix word-count pipeline replicated exactly
  • Character-level and byte-level BPE (naive + heap learners) with merge-table inspection; Rust port
  • Edit distance with backtrace (Python + C), reused by Automatic Speech Recognition for WER
  • Noisy-channel spelling corrector with a learned error model, cross-validated

Episodes

  1. Words, Types, and Heaps' Law31 min · 34 cues

    Types vs instances, corpora, Heaps/Herdan law |V|=kN^β, Zipf, power laws and log-log plots, morphology/morphemes.

  2. Unicode for Programmers27 min · 28 cues

    Code points, UTF-8 bytes, grapheme clusters, normalization NFC/NFD/NFKC, why bytes matter for tokenizers.

  3. Regular Expressions Are Machines (and Unix Is a Tokenizer)34 min · 30 cues

    Regex as finite automata (Kleene, Thompson), NFA/DFA, Unix tools pipelines (tr, sort, uniq), rule-based tokenization and its limits.

  4. BPE I: Learning a Vocabulary by Compression30 min · 30 cues

    Gage 1994 → Sennrich 2016; learner algorithm; pair-count hash maps; heap acceleration; pretokenization.

  5. BPE II: Segmenting, Bytes, and Fairness28 min · 29 cues

    Segmenter (apply merges), byte-level BPE, tiktoken/minbpe dissection, token inequity, 'strawberry' and arithmetic failures.

  6. Minimum Edit Distance as Dynamic Programming26 min · 29 cues

    Levenshtein/Wagner–Fischer, DP table + backpointers, alignment, costs, complexity, link to git diff and WER later.

  7. The Noisy Channel: Spelling Correction (Appendix D)30 min · 30 cues

    Noisy-channel model, Bayes in action, candidate generation, error models, language-model prior; Shannon's channel.

Exercises

ExerciseTierLadderTime
Heaps' law and Zipf's law, measured and fitted on log-log axes browserPredict · Scratch · Probe a claim50 min
UTF-8 by hand, three lengths of a string, and a normalization diff tool browserPredict · Scratch · Harden45 min
A Thompson NFA from scratch, and the Unix word-count pipeline replicated in Python browserPredict · Scratch · Harden · Probe a claim75 min
The BPE learner, naive and heap-accelerated, with merge-table inspection browserPredict · Scratch · Harden · Compose90 min
Systems lane: byte-level BPE learner and segmenter in Rust, verified against Python systems · rustPort · Harden120 min
Byte-level BPE with exact round trips on emoji and Chinese, and token inequity across languages browserPredict · Scratch · Harden · Compose75 min
Break it: BPE without pretokenization, and NFC vs NFD token ids (a replicated mini-experiment) browserPredict · Break it · Probe a claim60 min
Minimum edit distance with DP table, backpointers and alignment (reused for WER in C16) browserPredict · Scratch · Compose60 min
Systems lane: edit distance in C with two-row and flat-table versions, verified against Python systems · cPort · Harden75 min
Noisy-channel spelling correction with a learned error model, vs a Norvig-style corrector browserScratch · Compose · Probe a claim80 min

Labs

Library contributions

Files in nlpcore this module teaches you to write.

Sources

  1. Eric Brill, Robert C. Moore, An Improved Error Model for Noisy Channel Spelling Correction, ACL 2000
  2. Kenneth Ward Church, Unix for Poets (tutorial notes)
  3. Cloudflare, Details of the Cloudflare outage on July 2, 2019 (WAF regex backtracking) · link
  4. Graham, Knuth, Patashnik, Concrete Mathematics, 2nd ed., ch. 9 (asymptotics) and ch. 2 (sums)
  5. Russ Cox, Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...) · link
  6. Zhang, Lipton, Li, Smola, Dive into Deep Learning, sec. 3.1 (linear regression, squared loss, closed form, minibatch SGD) · link
  7. Fred J. Damerau, A technique for computer detection and correction of spelling errors, Communications of the ACM 7(3), 1964
  8. Philip Gage, A New Algorithm for Data Compression, The C Users Journal 12(2):23-38, February 1994
  9. Go standard library, src/testdata/Isaac.Newton-Opticks.txt, used by compress/flate, compress/bzip2, internal/zstd and index/suffixarray tests
  10. Gustav Herdan, Type-Token Mathematics (1960); H. S. Heaps, Information Retrieval: Computational and Theoretical Aspects (1978)
  11. D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, CACM 1975
  12. Mark D. Kernighan, Kenneth W. Church, William A. Gale, A Spelling Correction Program Based on a Noisy Channel Model, COLING 1990 · link
  13. S. C. Kleene, Representation of Events in Nerve Nets and Finite Automata, RAND (research memorandum, 1951; in Automata Studies, Princeton 1956) · link
  14. Taku Kudo, John Richardson, SentencePiece (2018); Taku Kudo, Subword Regularization (2018, unigram LM tokenizer)
  15. Jeremy Kun, A Programmer's Introduction to Mathematics (culture notes: notation as API, definitions as type signatures)
  16. Sander Land, Max Bartolo, Fishing for Magikarp: Automatically Detecting Under-trained Tokens in Large Language Models (EMNLP 2024) · arXiv:2405.05417
  17. V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Doklady Akademii Nauk SSSR 163(4), 1965 (English: Soviet Physics Doklady 10(8), 1966) · link
  18. Jon Bentley, Programming Pearls column 'A Literate Program' with Don Knuth's program and Doug McIlroy's review and six-line shell pipeline, CACM 1986
  19. Eugene W. Myers, An O(ND) Difference Algorithm and Its Variations, Algorithmica 1986 (basis of diff/git diff)
  20. Peter Norvig, How to Write a Spelling Corrector (essay) · link
  21. Aleksandar Petrov, Emanuele La Malfa, Philip H.S. Torr, Adel Bibi, Language Model Tokenizers Introduce Unfairness Between Languages (NeurIPS 2023) · arXiv:2305.15425
  22. Rob Pike, UTF-8 history (email, 2003), archived at https://www.cl.cam.ac.uk/~mgk25/ucs/utf-8-history.txt · link
  23. Radford et al., Language Models are Unsupervised Multitask Learners (GPT-2 report), OpenAI 2019 (byte-level BPE, regex pretokenizer)
  24. Rico Sennrich, Barry Haddow, Alexandra Birch, Neural Machine Translation of Rare Words with Subword Units (ACL 2016) · arXiv:1508.07909
  25. Claude E. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal 27, 1948
  26. Aaditya K. Singh, DJ Strouse, Tokenization counts: the impact of tokenization on arithmetic in frontier LLMs (2024) · arXiv:2402.14903
  27. Jurafsky & Martin, SLP3, Appendix D: Spelling Correction and the Noisy Channel (online appendix) · link
  28. Jurafsky & Martin, SLP3 draft (Aug 2026), Ch. 1 Introduction (tokens; Einstein's German title, 27 tokens) · link
  29. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft (Aug 19, 2026), Ch. 2 Words and Tokens · link · §2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7, 2.8, 2.9, Historical Notes
  30. Ken Thompson, Programming Techniques: Regular expression search algorithm, Communications of the ACM 11(6):419-422, 1968
  31. Unicode Standard Annex #15, Unicode Normalization Forms (NFC, NFD, NFKC, NFKD) · link
  32. Unicode Standard Annex #29, Unicode Text Segmentation (grapheme cluster rules GB1-GB999) · link
  33. Robert A. Wagner, Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM 21(1):168-173, 1974 · link
  34. George Kingsley Zipf, The Psycho-Biology of Language (1935); Human Behavior and the Principle of Least Effort (1949)