Glossary

Internal vowel change as a grammatical mark, as in sing, sang, sung and the noun song: the English strong-verb pattern, inherited from Proto-Indo-European, and a non-concatenative process with no segment to cut off.

• Slide 21

A bound morpheme attached to a host: a prefix such as un-, a suffix such as -ed, or the rarer infix and circumfix. Affixes show high selectivity and belong to morphological paradigms.

• Slide 18
• Slide 19
• Slide 23

A language that stacks many affixes, each with one clear function, such as Turkish ev-ler-im-den, from my houses.

• Slide 24
• Slide 25

A correspondence between two strings that makes explicit which characters match, substitute, insert or delete, recovered from the DP table with backpointers.

• Slide 81
• Slide 82
• Slide 87
• Slide 90

A language toward the low end of morphemes per word that relies on syntax, auxiliaries and word order; English is largely analytic.

• Slide 26
• Slide 27

A zero-width assertion on position: ^ start of line or string, $ end, \b a word boundary between a word and non-word character.

• Slide 64
• Slide 74

The 7-bit character code covering U+0000 to U+007F, in which A is hex 41 (decimal 65) and a is hex 61 (decimal 97). UTF-8 encodes these code points in one byte, unchanged.

• Slide 33
• Slide 35

The argmin arrow stored in each DP cell recording which neighbor (up for deletion, left for insertion, diagonal for substitution or match) produced its value; following them from the bottom-right cell, D[n,m] in the pseudocode, back to D[0,0] is the backtrace.

• Slide 90
• Slide 91

A reference to the text a capture group matched earlier: \1 inside the pattern, so (\w+) \1 finds a doubled word, or \1 and $1 in a replacement, so (\d{4})-(\d{2})-(\d{2}) with \3/\2/\1 turns 2026-01-25 into 25/01/2026.

• Slide 70
• Slide 72

Following the stored backpointers from the final cell back to D[0,0] to recover one minimum-cost alignment. Every step decreases i, j or both, so it takes O(n + m) steps; each choice at a tie cell yields a different optimal alignment of the same cost.

• Slide 90
• Slide 91

Treating the UTF-8 bytes of text as the base symbols, so any script, emoji or typo can be represented with no unknown character, at the cost of less interpretable tokens.

• Slide 37
• Slide 50

A subword tokenizer with a trainer that starts from characters or bytes and repeatedly merges the most frequent adjacent pair for k steps, and an encoder that replays the learned merges in order on new text.

• Slide 42
• Slide 43
• Slide 44
• Slide 45
• Slide 46
• Slide 47
• Slide 48

Unicode's declaration that two code point sequences are the same character, such as precomposed e-acute U+00E9 and e plus combining acute U+0065 U+0301. NFC and NFD fold canonical variants; the weaker compatibility equivalence (ligature U+FEFB to lam plus alef) is folded only by NFKC and NFKD.

• Slide 34

A parenthesized part of a pattern whose matched text is stored and can be reused as a backreference such as \1 in the pattern or $1 in a replacement; (?:...) groups without capturing.

• Slide 68
• Slide 70
• Slide 74

Mapping all letters to one case, usually lowercase, so that Apple and apple become the same type.

• Slide 9
• Slide 53

Exponential running time of a backtracking regex engine on patterns with nested or ambiguous quantifiers such as (a+)+ applied to a long non-matching input.

• Slide 78

A bracket expression such as [mM], [a-z] or [^0-9] that matches any one of a set of characters; a leading caret negates the set.

• Slide 59
• Slide 60
• Slide 61
• Slide 65

An element that behaves like a word syntactically but attaches phonologically to a host, showing low selectivity; examples are English 's and 'm, French l', Arabic proclitics wa- and bi- and the enclitic pronoun -hu.

• Slide 10
• Slide 22
• Slide 23
• Slide 26

The abstract numeric identifier Unicode assigns to a character, written U+ followed by hex digits, such as U+0061 for a.

• Slide 32
• Slide 34
• Slide 36

Mixing two or more languages or varieties within one utterance or text, such as Arabic and English in the same tweet. It adds foreign types to a corpus and is one of the dimensions along which corpora vary.

• Slide 8
• Slide 29

Building the meaning of a token sequence from the meanings of its reusable parts. If way is one token wherever it appears, the model reuses what it learned about way; a single Milky Way token removes that shared part, and its meaning must be learned from scratch.

• Slide 52

Word formation that joins two free roots into one word without any affix, as in snow-man and lap-top. It is concatenative and, with derivation, the most productive part of English morphology.

• Slide 18
• Slide 26

Word formation by attaching segments in sequence: prefixes, suffixes and compounding, as in cat-s or Turkish ev-ler-im-den.

• Slide 21

Derivation that changes part of speech without adding any morpheme, as in the noun email becoming the verb to email.

• Slide 20

A structured collection of texts, often annotated, that varies by domain, genre, time, demographics and language variety.

• Slide 6
• Slide 29

Edit distance extended with a fourth operation, transposition of two adjacent characters.

• Slide 86

Structured documentation accompanying a dataset: motivation and intended use, composition, collection process, preprocessing and annotation, ethical considerations and distribution constraints.

• Slide 30
• Slide 31

A morphological process that creates a new lexeme, often changing part of speech, as in happy to happiness or kitab versus katib.

• Slide 20

A filled pause such as uh or um, or a word fragment such as main-, in a speech transcript. Whether to keep it is a tokenization decision.

• Slide 4

Solving a problem by filling a table of overlapping subproblem answers, here D[i,j] for every prefix pair, so the shortest edit path is found in O(mn) instead of exponential search.

• Slide 83
• Slide 85
• Slide 88
• Slide 92

D[i,j] = min of D[i-1,j] + del, D[i,j-1] + ins, D[i-1,j-1] + sub(x_i, y_j), with D[0,0] = 0, D[i,0] = i and D[0,j] = j under unit costs.

• Slide 85
• Slide 88
• Slide 89

The tendency to unconsciously assume that computer behaviors are analogous to human behaviors, named after Weizenbaum's 1966 pattern-matching chatbot.

• Slide 56

A clitic that leans backward onto the preceding word, such as the Arabic pronoun -hu in kitab-u-hu (his book) and kataba-hu (he wrote it), or English 's in the person I was talking to's.

• Slide 22
• Slide 23

A backslash that strips a metacharacter of its special meaning, as in \. for a literal period or \* for a literal asterisk, or gives a plain letter one, as in \n for a newline and \d for a digit. The metacharacters are . ^ $ * + ? ( ) [ ] { } | and the backslash itself.

• Slide 66
• Slide 67

A language whose affixes bundle several grammatical features at once, such as Spanish habl-o where -o carries person, number, tense and mood.

• Slide 24
• Slide 25
• Slide 26

The rendered visual shape of a character. One glyph can correspond to several code points and vice versa.

• Slide 32
• Slide 34

The default behavior of quantifiers to match as much text as possible, as in .*; the lazy form .*? stops at the first match that lets the rest succeed.

• Slide 63
• Slide 73

A type that occurs exactly once in a corpus. Hapax legomena form a large fraction of all types, about half under Zipf's law, and draw as the longest bottom step of a log-log rank-frequency plot.

• Slide 12
• Slide 16

Also Herdan's law: the vocabulary size grows sublinearly but without bound with the number of tokens, |V| = k N^beta with 0 < beta < 1.

• Slide 7
• Slide 13
• Slide 14

A 1975 divide-and-conquer recomputation that recovers the full alignment in O(m + n) space and O(mn) time: run the two-row fill forward from the start and backward from the end, find where the optimal path crosses the middle column, then recurse on the two halves.

• Slide 92

Greenberg's 1960 ratio of morphemes to words in a sufficiently long text: 1.06 for Vietnamese, 1.68 for English, 2.59 for Sanskrit and 3.72 for Eskimo (Greenlandic). Below about 2 is analytic, 2 to 3 synthetic, above 3 polysynthetic.

• Slide 27

A morphological process that marks grammar such as tense, number, case or agreement without creating a new lexeme, as in walk to walked or katab-tu.

• Slide 20

A language with little morphology whose grammar is carried by word order and function words, such as Mandarin Chinese.

• Slide 24
• Slide 25

In UTF-8 the first byte of a character announces its length by its run of leading ones (0, 110, 1110 or 11110) and every later byte starts 10 and carries six payload bits. A 10 byte can never start a character, which makes the encoding self-synchronizing.

• Slide 35
• Slide 36

The straight line on log-log axes that minimises the squared vertical distance to the data points; its slope estimates the Zipf exponent alpha and its intercept the constant C. A line pinned to f(1) instead shows the same head bend as a bulge above the line.

• Slide 12

The dictionary form that a set of inflected wordforms shares, so walk, walks, walked and walking are four wordform types but one lemma. Morphology multiplies types per lemma, which is one reason the vocabulary keeps growing.

• Slide 8

Minimum edit distance with insertion, deletion and substitution each at cost 1 and a match at cost 0, after Levenshtein's 1966 paper; intention to execution is 5. His variant that allows only insertions and deletions is equivalent to charging 2 per substitution, which gives 8.

• Slide 79
• Slide 80
• Slide 89

The abstract dictionary word behind a set of forms. Inflection keeps the lexeme (walk, walked, walks are one entry); derivation creates a new one (happy and happiness are two), with or without adding a morpheme.

• Slide 20

A zero-width assertion that requires, (?=...), or forbids, (?!...), a pattern after the current position without consuming text, so stacked lookaheads such as ^(?=.*[A-Z])(?=.*\d).{8,}$ can check overlapping rules from the same position.

• Slide 71
• Slide 75

A zero-width assertion, (?<=...) or (?<!...), that tests the text before the current position without consuming it. Python's re module requires it to be fixed-width; JavaScript since ES2018 and the regex module accept variable-length lookbehind.

• Slide 75

One BPE training step: the most frequent adjacent pair of tokens tL, tR is concatenated into a new token tNEW, added to the vocabulary, and replaced everywhere in the corpus.

• Slide 43
• Slide 45
• Slide 46
• Slide 47

The minimum total cost of insertions, deletions and substitutions that transform a source string into a target string; with unit costs it is the Levenshtein distance.

• Slide 79
• Slide 80
• Slide 85

The smallest unit that carries meaning or grammatical function. Morphemes are free when they stand alone and bound when they must attach, as affixes do.

• Slide 17
• Slide 19
• Slide 27

A Leipzig-style line under a word with one label per morpheme, hyphens matching the segmentation, such as house-PL-1SG.POSS-ABL for Turkish ev-ler-im-den; a period joins several categories that one morpheme carries at once.

• Slide 21
• Slide 24

Splitting words at morpheme boundaries with a linguistic analyzer rather than by frequency, as MADAMIRA and CAMeL Tools do for Arabic under the ATB or D3 clitic schemes; used when a task needs the bare lemma.

• Slide 28

A parenthesized group written (?:...) that scopes an alternation or a quantifier without recording what it matched, so it takes no register number and leaves the numbering of the real capture groups alone.

• Slide 68
• Slide 74

Word formation by internal change, templatic root-and-pattern combination, or suppletion, as in sing, sang, sung, Arabic kataba, yaktubu, kitab, or go to went.

• Slide 21

The binding order of regex operators: parentheses first, then counters (* + ? {}), then sequences and anchors, and disjunction | last. It is why (cat|dog)s matches cats and dogs while cat|dogs matches cat and dogs.

• Slide 68

The property that every prefix of an optimal edit path is itself optimal: if a cheaper route to an intermediate string existed it could be spliced in, contradicting optimality. It licenses a table of prefix pairs (i, j) in place of a search over edit sequences.

• Slide 83
• Slide 87

A word or token that appears in new text but not in the vocabulary fixed at training time.

• Slide 15
• Slide 39
• Slide 40

Splitting a language's words into many more tokens than a comparable language needs, producing longer sequences. It is what a tokenization premium above 1 measures for a low-resource language under a shared, English-heavy vocabulary.

• Slide 51

The standard convention for parsed English corpora: separate all punctuation, keep hyphenated words together, and split clitics and possessives, so doesn't becomes does n't and children's becomes children 's.

• Slide 10

A language whose single words can encode sentence-like content with many morphemes, such as Inuktitut.

• Slide 24
• Slide 25
• Slide 27

A quantifier with an extra plus, such as ++ or *+, that consumes as much as it can and refuses to give characters back to the engine, so it can never participate in the retries behind catastrophic backtracking.

• Slide 78

A regex-based first pass that splits text roughly into words, numbers, punctuation, contractions and whitespace before BPE merges run inside each piece.

• Slide 49
• Slide 76
• Slide 77

A clitic that leans forward onto the following word, such as the Arabic conjunction wa- and the prepositions bi- and li- written solid onto whatever word begins the phrase.

• Slide 22
• Slide 23

Kiss and Strunk's 2006 unsupervised, language-independent sentence boundary detector, the default in NLTK. It finds abbreviations as tight collocations of a truncated word and a period from raw text, plus frequent sentence starters, reaching 98.74 percent mean accuracy over eleven languages.

• Slide 55

A count operator on the preceding element: * zero or more, + one or more, ? zero or one, {n} exactly n, {m,n} between m and n; adding ? makes it lazy.

• Slide 62
• Slide 63
• Slide 73

A pattern language for matching strings built from literals, concatenation, disjunction, grouping, character classes, quantifiers and anchors, used in NLP for tokenization, normalization, cleaning and feature extraction.

• Slide 57
• Slide 58

The core lexical material of a word, such as walk, or the consonantal skeleton K-T-B in Arabic that combines with patterns.

• Slide 18
• Slide 19

How restricted an attached element is in what it attaches to. Affixes are highly selective (specific stems or categories); clitics attach to almost any host.

• Slide 23

Finding sentence boundaries in text, hard mainly because a period may end a sentence or belong to an abbreviation or number; solved with heuristics, abbreviation lexicons or learned boundary classifiers.

• Slide 54
• Slide 55

A symbol attached to each word before BPE training: a leading marker for the space before a word (an open box on the slides, G-dot in GPT-2, the lower one-eighth block ▁ (U+2581) in SentencePiece) or Sennrich's end-of-word suffix. It makes word-initial pieces such as _re distinct from word-internal re.

• Slide 44
• Slide 45
• Slide 46
• Slide 47

Reserved vocabulary entries with control meaning such as <BOS>, <EOS>, <UNK> and <PAD>.

• Slide 53

The inflectable base of a word to which affixes attach.

• Slide 18
• Slide 19

The cost of replacing one character with another: 0 for identical characters, 1 in the unit-cost convention, 2 in the Levenshtein variant used by the SLP3 table, or a weighted value from a confusion matrix.

• Slide 80
• Slide 86
• Slide 89

Splitting text into units between characters and words, giving a smaller vocabulary than words and shorter sequences than characters, and composing unseen words from pieces.

• Slide 28
• Slide 41
• Slide 49

A BPE variant whose later merge stage may cross spaces to form multiword tokens such as 'By the way', trading compositionality for shorter sequences.

• Slide 52

An irregular form that replaces the expected inflected form entirely, such as went for the past of go.

• Slide 21

The Arabic root-and-pattern system in which a consonantal root such as K-T-B is interleaved with vowel patterns to yield kataba, kitab and katib.

• Slide 19
• Slide 21
• Slide 26

One occurrence of a unit in running text. The total number of tokens in a corpus is written N.

• Slide 5
• Slide 7
• Slide 38

Converting raw text into a sequence of tokens, the units a model or pipeline operates on, balancing coverage, compactness, meaningfulness and cross-lingual applicability.

• Slide 38
• Slide 39
• Slide 40
• Slide 41

Petrov et al. 2023: the token count of a sentence in language A divided by the count for its translation in language B. Relative to English under the GPT-4 cl100k vocabulary, Arabic pays 3.04 and Shan 15.05, the cost of a shared vocabulary trained mostly on English.

• Slide 51

A distinct vocabulary item. The number of types in a corpus is the vocabulary size, written |V|.

• Slide 5
• Slide 7

|V| divided by N, the number of distinct types over the number of running tokens. It falls as a corpus grows and rises with morphological richness: 0.144 for Inuktitut against 0.003 for English on the parallel Nunavut Hansard.

• Slide 7
• Slide 28

Converting text to a canonical form (NFC, NFD, NFKC or NFKD) so that characters composed in different ways, such as precomposed and decomposed accented letters, compare and tokenize identically.

• Slide 34
• Slide 53

An escape of the form \p{...} that matches every character with a given Unicode property, such as \p{L} for any letter or \p{N} for any number, defined by Unicode Standard Annex 44; requires the regex module in Python or the u flag in JavaScript.

• Slide 76
• Slide 78

Kudo's 2018 subword tokenizer, named by SLP3 with BPE as the two widely used families: it starts from a large candidate vocabulary, prunes it under a unigram language model, and segments each word into the most probable sequence of pieces.

• Slide 49

A variable-length encoding of Unicode code points into 1 to 4 bytes: one byte for U+0000 to U+007F, two for up to U+07FF, three for up to U+FFFF, four for up to U+10FFFF, with lead bytes 110, 1110 or 11110 and continuation bytes 10xxxxxx.

• Slide 35
• Slide 36

The set of distinct types a corpus or a tokenizer uses. Its size is |V|, and for a tokenizer it is a design choice, typically 30k to 100k subword units.

• Slide 5
• Slide 13
• Slide 49

The zero-width position \b between a word character (a letter, digit or underscore) and a non-word character or a string edge; \B is any other position. \bthe\b matches the but not other or theme, and \b99\b matches in $99 but not in 299.

• Slide 64
• Slide 74

An ASR evaluation metric equal to the word-level edit distance between hypothesis and reference divided by the number of reference words.

• Slide 79

The subword tokenizer of BERT (Schuster and Nakajima 2012, Wu et al. 2016) that divides words into a limited set of common sub-word units and encodes by taking the longest vocabulary entry that matches first.

• Slide 28
• Slide 49

Zipf's law with a rank shift, f(R) = P (R + rho)^-B, added by Mandelbrot to fit the flattened head of the rank-frequency curve, where the top few words fall off more slowly than a pure power law predicts.

• Slide 11
• Slide 12

The empirical rank-frequency law that a word's frequency falls roughly as a power law in its rank, f(R) proportional to 1 / R^alpha, with alpha close to 1.

• Slide 11
• Slide 12