ICS 582Lecture 02Reference

Reference sheet

Words and tokens compressed onto one page: the definitions, formulas and numbers to have in your head before a quiz or exam.

Tokens, types and vocabulary

A token is one occurrence, counted by N. A type is one distinct vocabulary item, counted by |V|. The count is never a property of the language: it follows from the policy. Part 01: What is a word

N = \sum_{w \in V} c(w)

Every token belongs to exactly one type, so the type counts add up to N

Policy	Tokens N	Types \|V\|
Whitespace only	16	14
Punctuation split	18	16

The picnic sentence under two policies

Definitions worth memorizing

Token: One occurrence in running text; the total is N.
Type: A distinct vocabulary item; the total is |V|, the vocabulary size.
Lemma: The dictionary form shared by a word family: walk, walks, walked, walking.
Hapax legomenon: A type seen exactly once; about half the types of a natural corpus.
Out of vocabulary: A test-time token absent from V; unavoidable at the word level.
Type to token ratio: |V| / N, which falls as N grows.

Corpus	Types \|V\|	Tokens N	Types per 1,000
Shakespeare	31 k	884 k	35.1
Brown	38 k	1 M	38.0
Switchboard	20 k	2.4 M	8.3
COCA	2 M	440 M	4.5
Google n-grams	13 M	1 T	0.013

One table of English corpora, with types per 1,000 tokens computed

Zipf and Heaps

Frequency follows a steep power law and vocabulary follows a sublinear power law. Both are straight lines on log axes. Part 02: Zipf and Heaps

f(R) \propto \frac{1}{R^{\alpha}} \qquad f(R) \approx \frac{f(1)}{R^{\alpha}}

Zipf's law: the frequency of the rank R type

\log f = \log C - \alpha \log R

Log frequency falls linearly in log rank with slope minus alpha

f(R) = P (R + \rho)^{-B}

Mandelbrot's refined form, which flattens the lowest ranks

|V| = k N^{\beta}

Heaps' law, also Herdan's law

Fit	k	beta	at 10^4	at 10^6	at 10^8
English (dotted)	14.947	0.583	3,210	47,049	689,531
Arabic (dotted)	73.321	0.533	2,576	115,672	5,193,404
Arabic (undotted)	90.491	0.506	2,846	98,312	3,396,228

Heaps fits and predicted vocabulary size

Sample numbers worth quoting

Tom Sawyer: 71,370 tokens and 8,018 types.
Top type: the at 3,332, then and at 2,972, then a at 1,775.
Zipf check: The product of frequency and rank holds near 8,000 to 10,000 over the top ranks.
Printed slip: Manning and Schütze print 5,235 for a at rank 3; the arithmetic gives 1,775 x 3 = 5,325.
Coverage: The top 100 types are 50.9% of all tokens.
Tail: The frequency staircase collapses at f = 3, 2, 1, where thousands of types tie.
Hapax share: 49.8% of Tom Sawyer types occur once.

Morphemes and word structure

The meaningful parts inside a word explain why walk, walks and walked are three types but one lemma. Part 03: Morphemes

Morpheme	Position	Free or bound	Function	Example
un-	Prefix	Bound	Negation	unhappy
happy	Root	Free	Lexical core	unhappiness
-ness	Suffix	Bound	Nominalizer	happiness
-s	Suffix	Bound	Inflectional plural	cats
abso-bloody-lutely	Infix	Bound	Intensifier	abso-bloody-lutely
ge- ... -t	Circumfix	Bound	Participle	gespielt

Morpheme types in unhappiness and beyond

Process	What changes	Lexicon effect	Example
Inflection	Same lexeme, grammatical features	Phrase stays the same	walk to walks, walked
Derivation	New lexeme, new meaning or category	New lexical entry	happy to un+happy+ness
Conversion	No affix at all, category changes	Zero derivation	an email to to email

Inflection, derivation and conversion

Arabic root and pattern

Root: K-T-B
kataba: Pattern CaCaCa, he wrote.
kitāb: Pattern CiCāC, book.
kātib: Pattern CāCiC, writer.
yaktubu: Prefix ya- around CCuC plus suffix -u, he writes.
Non-concatenative: Ablaut and suppletion: sing, sang, sung; go, went; good, better.

Four decision tests for an affix: the lexeme test, the category test, the productivity test and the position test. Give at least two in an answer.
Agglutinative stacking keeps seams visible: Turkish ev-ler-im-den is house, plural, first person possessive, ablative.

Clitics and typology

A clitic sits between a word and an affix. Zwicky and Pullum's tests, selectivity, paradigm membership, arbitrary gaps, idiosyncrasy, syntactic rules and stacking, decide which side. Part 04: Clitics and typology

Form	Status	Selectivity	Evidence
wa-	Proclitic	Low: conjunctions	Slide 28, ATB keeps it separate
bi-	Proclitic	Low: prepositions	POS varies with host
al-	Borderline	Moderate: definiteness	ATB keeps it, D3 splits it
-hu	Enclitic	Low: nouns, verbs, prepositions	Attaches across categories
-tu	Inflectional affix	High: perfective verbs only	One paradigm cell

Arabic host plus clitic decisions

Policy	Tokens	Output
Whitespace	1	وَبِالْبَيْت
ATB	3	wa+ bi+ albayt
D3	4	wa+ bi+ al+ bayt

One string, three tokenizations of و بالبيت

Type	Definition	Example	M/W	Language
Isolating	One morpheme per word	wǒmen míngtiān qù Běijīng	1.06	Mandarin
Agglutinative	Many morphemes, clear seams	ev-ler-im-den	2.55	Turkish
Fusional	Portmanteau morphemes	habl-o	2.59	Spanish, Sanskrit
Polysynthetic	Many morphemes, often a sentence	t-ə-nk'e-mejŋ-ə-jetemə-nni-k	3.72	Inuktitut, Koryak

Typology, with Greenberg's index of synthesis M/W

Language	M/W	Rounded on the slide
Vietnamese	1.06	Slide 1.1
Persian	1.52	Slide 1.5
English	1.68	Slide 1.7
Old English	2.12	Slide 2.1
Yakut	2.17	Slide 2.2
Swahili	2.55	Slide 2.5
Sanskrit	2.59	Slide 2.6
Eskimo / Greenlandic	3.72	Slide 3.7

Greenberg's index by language

\text{index of synthesis} = \frac{M}{W}

Morphemes per word; bands are analytic under 2, synthetic 2 to 3, polysynthetic over 3

\mathrm{TTR} = \frac{|V|}{N}

Type to token ratio, the diagnostic that falls with corpus size

Why morphology decides tokenizer policy

Nunavut Hansard: 10,869,995 Inuktitut tokens give 1,563,883 types, TTR 0.144.
English at the same scale: 20,367,595 tokens give 59,234 types, TTR 0.003, about 26x fewer types.
OOV: A 1.3 million word vocabulary still leaves more than 60% of tokens unknown on a hard language pair (Gupta and Boulianne 2020).
Arabic verbs: Upwards of 5,400 forms per Modern Standard Arabic verb (Obeid et al.).
Three responses: Subword tokenization (BPE, WordPiece), morphological segmentation (MADAMIRA, CAMeL Tools), careful preprocessing.

Corpora, code points and UTF-8

Unicode assigns each character a code point in U+0000 to U+10FFFF, 1,114,112 positions. UTF-8 encodes each code point as one to four bytes. Part 05: Corpora and Unicode

\text{a} = 0x61 = 0x41 + 0x20 = \text{A} \;\lor\; 0x20

Case folding as a single bit: ASCII letters differ by 0x20

Range	Template	Bits	Bytes	Example
U+0000 to U+007F	0xxxxxxx	7	1	a = 0x61
U+0080 to U+07FF	110yyyyy 10xxxxxx	11	2	é = C3 A9
U+0800 to U+FFFF	1110zzzz 10yyyyyy 10xxxxxx	16	3	ب = D8 A8
U+010000 to U+10FFFF	11110uuu 10uuzzzz 10yyyyyy 10xxxxxx	21	4	😀 = F0 9F 98 80

UTF-8 byte templates by code point range

Character	Code point	UTF-8 bytes
a	U+0061	61
é	U+00E9	C3 A9
ب	U+0628	D8 A8
€	U+20AC	E2 82 AC
中	U+4E2D	E4 B8 AD
ﻻ	U+FEFB	EF BB BB
😀	U+1F600	F0 9F 98 80

Worked encodings

Form	Operation	é	Equivalence
NFD	Decompose	e + U+0301	Canonical
NFC	Compose	U+00E9	Canonical
NFKD	Compatibility decompose	E + U+0301	Compatibility
NFKC	Compatibility compose	U+00C9	Compatibility

The four Unicode normalization forms

Byte sequences starting C0, C1 or anything F5 to FF are never valid UTF-8.
UTF-8 is backward compatible with ASCII and self-synchronizing: a lead byte tells you how many bytes follow.
كتاب is four code points and eight bytes, a reminder that byte-level tokenizers see twice the length.

Byte-pair encoding

BPE starts from characters and greedily merges the most frequent adjacent pair, learning a vocabulary from data. Part 06: Tokenization and BPE

|V_{\text{final}}| = |V_{\text{initial}}| + k

k merges add k vocabulary entries

Criterion	Achievable at once	What it means	Effect
Coverage	N	Any character, any script	Byte fallback has no unknown symbol
Compactness	N	Rare words cost few pieces	Fewer tokens per sentence
Meaningfulness	Pieces line up with morphemes	Better generalization to unseen words
Cross-lingual	N	One vocabulary for many scripts	No language left with a long tail

The four design criteria a tokenizer must trade off

Merge	Count	Symbols before	Symbols after
ne	4	29	25
new	4	25	21
_r	3	21	18
_re	3	18	15

Merge trace on the slide corpus set new new renew reset renew

Trainer and encoder procedure

1. Initialize: Split every word into characters plus the space marker, then count.
2. Count pairs: Count every adjacent symbol pair across the corpus.
3. Merge: Take the most frequent pair, replace it with a new symbol, record the rule.
4. Repeat: Run k merges; the recorded rules are the tokenizer.
5. Encode: encode(w) = m_k( ... m_1(chars(w))), replaying the merges in order.
Space marker: Leading _ (GPT-2 Ġ, SentencePiece ▁ U+2581) or a trailing suffix.
Worked replay: _renewed encodes as _re new e d.
Tie rule: First seen, alphabetical, lexicographically largest (subword-nmt) or highest token id; the rule is an implementation choice.

Tokenizers in practice

A modern tokenizer is a pre-tokenizer plus a subword model plus a normalization and special-token policy. Part 07: Tokenizers in practice

Tokenizer	Vocabulary	Tokens
GPT-2	50,257	14
cl100k	100 k	14
o200k	200 k	13

The same sentence under three tokenizers

#	Pattern	Matches
1	's\|'t\|'re\|'ve\|'m\|'ll\|'d	English contractions
2	?\p{L}+	Optional space then letters
3	?\p{N}+	Optional space then digits
4	?[^\s\p{L}\p{N}]+	Everything else, one run
5	\s+(?!\S)	Trailing whitespace
6	\s+	Last resort, any whitespace

GPT-2 style pre-tokenizer, six alternatives in priority order

Vocabulary sizes to know

GPT-2: 50,257
BERT base (WordPiece): 30,522
Llama 3: 128 K
GPT-4o (o200k): 200 K
Special token: <|endoftext|> sits at id 50256 in GPT-2.

Sentence	Language	Words	Tokens	Fertility
The book is on the table.	English	6	7	1.17
الكتاب على الطاولة.	Arabic	3	12	4.0

Fertility: tokens per word

\text{premium}_{A \mid B} = \frac{|t(s_A)|}{|t(s_B)|}

Tokenization premium: tokens for a sentence in A over tokens for its translation in B (Petrov et al. 2023)

Language	GPT-2	cl100k	ByT5
Portuguese	1.94	1.48	n/a
German	2.14	1.58	n/a
Chinese (Simplified)	3.21	1.91	0.93
Standard Arabic	4.40	3.04	1.60
Burmese	16.89	11.70	3.51
Shan	18.76	15.05	3.94

Premium by language, GPT-2 / cl100k / ByT5

Tokenizer	Output	Reversibility
BERT (WordPiece)	Hello \| world	Discarded, not reversible
GPT-2	Hello \| ·world	Glued, reversible
SentencePiece	▁Hello \| ▁world	Explicit, lossless

Whitespace policies on Hello world

Sentence segmentation

A sentence boundary is a period that is not part of an abbreviation, a number or a quotation. Part 07: Tokenizers in practice

One passage, four sentences

Passage: Dr. Ahmad arrived at 5 p.m. on Monday. He paid 3.50 riyals. Was it enough? Yes!
Sentences: 4
Traps: Dr. and p.m. hold periods; 5 and 3.50 hold periods with digits on both sides.

Approach	How it works	Evidence
Rule-based	Punctuation plus capitalization, abbreviation list, quote balancing, digits on both sides	Fast, needs a hand-written abbreviation list
Statistical	Supervised, learn the boundary probability from annotated text	Needs labeled data
Punkt	Unsupervised, English boundary error 1.65% and German 0.35%	98.74% mean accuracy over eleven languages (Kiss and Strunk 2006)

Approaches to segmentation

Regular expressions

Regex is the pattern language under every pre-tokenizer, cleaner and feature extractor. ELIZA 1966 used about 50 keyword patterns of the form .* YOU ARE (DEPRESSED|SAD) .* replacing with I AM SORRY TO HEAR YOU ARE \1. Part 08: Regex basics, Part 09: Regex in practice

Operator	Meaning	Example	Matches
*	Zero or more	ab*c	ac, abc, abbc
+	One or more	ab+c	abc, abbc, not ac
?	Zero or one	ab?c	ac, abc
{n}	Exactly n	a{3}	aaa
{m,n}	Between m and n	a{2,4}	aa, aaa, aaaa
.	Any char but newline	a.c	abc, a c

Quantifiers

Pattern	Text	Result
<.*>	<a><b>	1 match, length 6
<.*?>	<a><b>	2 matches, length 3
a.*b	xaxbxbx	axbxb, span 1 to 5
a.*?b	xaxbxbx	axb, span 1 to 3

Greedy versus lazy

Anchor	Meaning	Example
^	Start of string, or line under m	^The
$	End of string, or line under m	end$
\b	Word boundary	\b99\b
\B	Not a word boundary	\B99

Anchors

Alias	Meaning	Equivalent
\d	A digit	[0-9]
\D	Not a digit	[^0-9]
\w	Word character	[a-zA-Z0-9_]
\W	Not a word character	[^a-zA-Z0-9_]
\s	Whitespace	[ \r\t\n\f]
\S	Not whitespace	[^ \r\t\n\f]

Character class aliases

Level	Binds	Operators
1	Parenthesis	( )
2	Counters	* + ? { }
3	Sequences and anchors	abc, ^, $
4	Disjunction	\|

Precedence, tightest first

Operator details worth memorizing

The caret: Anchor outside brackets, negation only as the first character inside brackets, literal elsewhere inside.
{m,}: At least m; JavaScript needs {0,n} for the at-most form.
Escape: Fourteen metacharacters take a backslash: dot, caret, dollar, star, plus, question mark, the two parentheses, the two brackets, the two braces, the pipe and the backslash itself.
Lookaround: (?=...) and (?<=...) assert forward and behind without consuming.
Disjunction: cat|dogs matches cat, dogs and the cat inside cats; parenthesize to group.
Flags: g all matches, m multiline anchors, i case-insensitive.

Minimum edit distance

The distance between two strings is the cost of the cheapest edit script, found by dynamic programming over prefix pairs. Part 10: Edit distance, Part 11: Edit distance DP

D[0,0] = 0, \qquad D[i,0] = i, \qquad D[0,j] = j

Initialization: an empty target forces i deletions, an empty source forces j insertions

D[i,j] = \min \begin{cases} D[i-1,j] + \text{del}(x_i) \\ D[i-1,j-1] + \text{sub}(x_i, y_j) \\ D[i,j-1] + \text{ins}(y_j) \end{cases}

The recurrence, SLP3 Eq. 2.19: up, diagonal, left

D[i,j] = \min \begin{cases} D[i-1,j] + 1 \\ D[i-1,j-1] + \begin{cases} 2 & x_i \ne y_j \\ 0 & x_i = y_j \end{cases} \\ D[i,j-1] + 1 \end{cases}

The cost-2 convention of slide 89, SLP3 Eq. 2.20: a substitution counts as a deletion plus an insertion

Operation	Unit cost	Cost 2	Slide 82 example
Match	0	0	E over E
Insertion	1	1	* over C
Deletion	1	1	I over *
Substitution	1	2	N over E

Cost conventions

Move	Operation	Cell
Up	Deletion of source character	D[i-1,j] + del
Diagonal	Substitution or match	D[i-1,j-1] + sub(x_i, y_j)
Left	Insertion of target character	D[i,j-1] + ins

Which move is which

D	ε	c	a	t
ε	0	1	2	3
c	1	0	1	2
a	2	1	1	2
t	3	2	2	1

Worked table, cat to cut, unit costs

Worked numbers

Slide 82 alignment: d s s _ i s: delete, two substitutions, match, insertion, substitution.
Slide 82 totals: 5 under unit cost, 8 under cost 2.
Position by position: Five substitutions, 5 under unit cost and 10 under cost 2.
Step 1: Cost 2 gives D[1,1] = 2 on the slide; under slide 86 unit cost it would be 1.
Alignment count: Cost 2 admits 134 optimal alignments, unit cost only 7.
Erickson to ALTRUISTIC: Exactly 3 optimal paths.
Hamming versus edit: flaw to lawn is Hamming 4 but edit 2.
CallHome WER: 6 substitutions, 3 insertions and 1 deletion over 13 reference words give WER 76.9%.

Backtrace on intention to execution, cost 2

Bottom right: D[m,n] = 8.
Matches: Five on the diagonal, each cost 0: e, t, i, o, n.
Substitutions: n to u, t to x, n to e, each cost 2.
Deletion: i at the left edge of the source, cost 1.
Insertion: c inserted into the target, cost 1.

Evidence for edit distance in spelling correction

Damerau 1964: A single wrong, missing, extra or transposed letter accounts for about 80% of spelling errors.
Kernighan, Church and Gale: On 44 million words of 1988 AP newswire, automatic correction agreed with human judges on 87% of 329 sampled cases.

Task	Time	Space	Note
Distance only	O(mn)	O(min(m,n))	Two rows
Distance and alignment	O(mn)	O(mn)	Store every cell
Alignment in linear space	O(mn)	O(m+n)	Hirschberg, about twice the constant

Space and time

\text{tree nodes} \approx (2|\Sigma| L)^{d} \qquad \text{grid cells} = (m+1)(n+1)

Why DP wins: from cat to cats the search tree has 494 children per step and about 3 x 10^13 nodes at depth 5, the grid only 100 cells

\mathrm{WER} = \frac{I + S + D}{\text{words in the reference}}

Word error rate from a word-level minimum edit distance alignment (SLP3 section 16.6)

Slide errata

Answer with the corrected fact, and name the slide version when a question depends on it. Part 01: What is a word

What the slides get wrong

Slide 12: The second dashed-line legend reads "standard zipfian distribution dotted english un", truncated; it should read English Wikipedia, and that fit belongs to the blue English curve.
Slide 14: The Heaps fit is extrapolated to 1.2 x 10^19, far past the data, and the curves do not reproduce from the legend constants.
Slide 33: The caption promises a binary column that is absent, "for letters" is wrong (the template holds any code point), and hex 5D is displayed as [ where it should be ].
Slide 43: The caption says toy-corpus step-by-step, but the figure is the SLP3 Fig. 2.6 pseudocode; the toy trace is slides 44 to 47.
Slide 44: The bullet says "with end-of-word marker or space markers", but the tables on slides 44 to 47 use the leading space marker only. Follow the tables.
Slide 56: The ELIZA script line reads "WHO ELSE IN YOU FAMILY"; the source line is "WHO ELSE IN YOUR FAMILY".
Slide 61: The a^b example inherited from SLP3 Fig. 2.10 does not hold in modern engines; write a\^b, which matches the span (8, 11).
Slide 72: 2026-25-01 is not valid ISO 8601 (month 25), and <\End> uses a backslash where HTML closes a tag with a slash.
Slide 85 and 88: Slide 85 writes source x length m and target y length n; the slide 88 pseudocode and slide 90 backtrace index rows n and columns m. Fix one convention and keep the answer cell consistent.
Slide 89: The table charges substitution 2, following SLP3 Fig. 2.20, while slide 86 defines substitution cost 1; under slide 86 D[1,1] = 1 and the bottom right is 5, not 8.