Words and Tokens

By simple pattern matching on words: it recognized phrases like “I need X” and transformed them into outputs like “What would it mean to you if you got X?”, imitating a Rogerian psychotherapist.

Separating out (tokenizing) words and word parts from running text: the first step in modern NLP.

A measure of how similar two strings are, based on the number of insertions, deletions and substitutions needed to turn one into the other. It is used whenever strings must be compared, e.g. in the word error rate metric for speech recognition.

It depends on the task. Punctuation marks boundaries (commas, periods, colons) and some meaning (question marks, quotation marks). LLMs generally treat punctuation as separate words.

The spoken correlate of a sentence.

A fragment (the broken-off word main-) and a filled pause or filler (uh).

They help predict the upcoming word, since they may signal that the speaker is restarting a clause or idea. They can also be a cue to speaker identity.

Types are the distinct words in a corpus (their number is the vocabulary size \(|V|\)); instances are the running words, \(N\). “The cat saw the dog” has 5 instances but 4 types.

It reserves “token” for the output of subword tokenization algorithms.

It depends on the task: they may be merged where formatting doesn’t matter, but capitalization is a useful feature for other tasks. Sometimes both cased and uncased versions of a model are kept.

It functions as the subject pronoun I plus the verb ’m (short for am).

Chinese, Japanese and Thai don’t use spaces to mark word boundaries, so deciding what counts as a word requires a (debatable) standard.

A hanzi. Each character generally represents a single morpheme and is pronounced as a single syllable.

3 words under the Chinese Treebank standard (names are one word: YaoMing / reaches / finals); 5 under the Peking University standard (Yao / Ming / reaches / overall / finals); or 7 characters if words are ignored entirely.

Chinese characters are at a reasonable semantic level (roughly morphemes) for most applications; in Japanese and Thai the individual character is too small a unit.

The number of word types grows with the number of instances as \(|V| = kN^{\beta}\), with constants \(k > 0\) and \(0 < \beta < 1\). Roughly, vocabulary grows a bit faster than the square root of text length.

Function words (a, of) form a roughly fixed set that is exhausted early. Content words, especially nouns such as names and technical terms, keep growing indefinitely. So vocabulary growth has two regimes, with different \(\beta\) values.

No vocabulary, however big, contains every word that might occur, so models constantly meet unknown words they have never seen before.

Many languages lack orthographic words, and defining them post hoc is hard; and the number of words grows without bound. So models use smaller subword units that can be recombined into unseen words.

A morpheme is a minimal meaning-bearing unit of language (cats = cat + plural -s). Morphology is the study of morphemes.

The root is the central morpheme that supplies the main meaning (work in worked); affixes add additional meanings (-ed).

Inflectional morphemes are grammatical, play a syntactic role such as agreement or tense (plural -s, past -ed), are productive, often obligatory and predictable in meaning. Derivational morphemes are idiosyncratic, apply to specific word subclasses, usually change the word class, and have less predictable meanings (care → careful → carefully).

A morpheme that acts syntactically like a word but is reduced and attached to another word, so it cannot stand alone: English ’ve in I’ve, possessive ’s, French l’ in l’opéra, Arabic b ‘by/with’ and w ‘and’.

The study of how languages vary in their morphology, i.e. how words break up into parts.

A scale from isolating (analytic) languages with about one morpheme per word (Vietnamese, Cantonese), through synthetic languages, to polysynthetic languages where one word can express a whole English sentence (Koryak).

How easily morphemes can be segmented: agglutinative languages (Turkish) have morphemes with clean boundaries; fusion languages (Russian) have affixes that conflate several categories, e.g. -om in stolom marks instrumental + singular + first declension at once.

The single suffix means both third person singular and present tense, with no way to divide the meaning between parts.

More accurately they are general tendencies: a language can use different morphological systems.

Morphemes can be hard to define, and many languages have complex fused morphemes that aren’t easy to break into pieces.

A standard for representing text written in any character of any script of the world’s languages (including dead languages like Sumerian cuneiform and invented ones like Klingon), plus symbols, emoji, etc.

The 1960s American Standard Code for Information Interchange: one byte per character, using only 128 values (high-order bit 0), for the Latin characters used in English. It survives as Unicode’s first block (“Basic Latin”).

Even Latin-script languages need characters outside it (Spanish ñ, ó), and many languages use other scripts entirely (Devanagari, Chinese characters…).

A unique abstract id for a character, a number from 0 to 0x10FFFF, written with the prefix U+ (e.g. U+0061 for a).

Unicode was designed to be backwards compatible with ASCII.

A code point is the abstract character; a glyph is its visual representation, stored in a typeface. a in Times, Courier, bold or italic is the same code point U+0061.

The way a character (code point) is actually written as bytes in a text string or file. UTF-8 is by far the most frequent; almost the whole web uses it.

It makes files 4 times longer than ASCII and full of zero bytes, and zero bytes break ASCII-based systems that historically used 0 as an end-of-string marker.

Characters take different numbers of bytes: ASCII characters take 1 byte, other code points 2, 3 or 4 bytes. Each multi-byte byte is between 128 and 255, and the first byte’s leading bits say how many bytes follow.

code points	bytes
U+0000–007F	0xxxxxxx
U+0080–07FF	110yyyyy 10xxxxxx
U+0800–FFFF	1110zzzz 10yyyyyy 10xxxxxx
U+10000–10FFFF	11110uuu 10uuzzzz 10yyyyyy 10xxxxxx

The code point’s bits fill the x, y, z, u slots.

It is in the U+0080–07FF range, so it takes 2 bytes: its bits 00011 110001 fill 110yyyyy 10xxxxxx, giving 11000011 10110001 = 0xC3 0xB1.

ASCII: 1 byte; most other European, Middle Eastern and African scripts: 2 bytes; most Chinese, Japanese and Korean characters: 3 bytes; rarer CJKV characters, emoji and some symbols: 4 bytes.

It is efficient for common characters, uses no zero bytes (except for NULL itself), is backwards compatible with ASCII (ASCII files are valid UTF-8), and is self-synchronizing: after corruption you can find the next or previous character start by moving at most 3 bytes.

Code points (characters), not bytes: Python 3 strings are sequences of Unicode code points. Bytes appear only when encoding/decoding to a file.

No. Every file is in some encoding (UTF-8 or older ones like ASCII or Latin-1), which must be specified when reading or writing.

Words and morphemes are at roughly the right level (consistent meanings) but hard to define formally. Characters are easy to define but too small a unit.

So systems can agree on basic questions (How long is this text? Is New York one token or two?), which is essential for replicability; metrics like perplexity assume a fixed tokenization. Subword tokens also eliminate unknown words.

A system trained on low, new, newer but not lower wouldn’t know what to do with lower at test time. With subword tokens, every unseen word can be built from known pieces (low + er), in the worst case from single characters.

Byte-pair encoding (BPE; Sennrich et al., 2016) and the unigram language model (ULM; Kudo, 2018). The SentencePiece library implements both.

A training phase, which induces a vocabulary of tokens from a raw training corpus, and an encoding phase, which segments new text into tokens from that vocabulary.

Start with a vocabulary of all single characters (or bytes). Repeatedly find the most frequent pair of adjacent tokens in the corpus, add their concatenation as a new token, and replace every occurrence of the pair with it. Stop after \(k\) merges; the vocabulary is the characters plus \(k\) new tokens.

Most frequent pair: A B → new token AB: AB D C AB E C AB. Next most frequent: C AB → CAB: AB D CAB E CAB. Vocabulary is now {A, B, C, D, E, AB, CAB}.

The corpus is first pre-split at whitespace and punctuation (with regexes) into words with counts; merges are allowed only inside these strings, which keeps tokens word-like.

re-: after merging n e and ne w, frequent pairs like (space, r) and then (r, e) merge into a word-initial token “␣re”, since it appears in renew and reset.

merge	corpus afterwards
n e → ne	r e ne w, r e s e t
ne w → new	r e new, r e s e t
␣ r → ␣r	␣r e new, ␣r e s e t
␣r e → ␣re	␣re new, ␣re s e t

It splits each word into characters, then applies the learned merges greedily in the order they were learned (most frequent in training first). Test-data frequencies play no role.

Morpheme-like pieces, e.g. the prefix re- (for unseen revisit, rearrange) or word-internal new without a leading space (for anew).

Tens of thousands of merges, giving 50,000–200,000 tokens, so most (English) words are single tokens and only rare or unknown words are split.

On the individual bytes of the UTF-8 encoding. Only 256 byte values exist, so there are no unknown tokens; BPE first rediscovers common multi-byte UTF-8 sequences. Rare illegal byte sequences can be filtered.

Most words are single tokens, usually including their leading space; clitics like ’s split off rare names but not frequent words like she’s; numbers are chunked into groups of 3 digits; capitalization and position change segmentation (Any+how vs ␣anyhow).

A stage before BPE that segments the input with regular expressions: breaking at spaces and punctuation, splitting off clitics, and chunking numbers.

After learning ordinary subword tokens with pretokenization, they run a second BPE stage that allows merges across spaces and punctuation, producing larger multi-word tokens that encode text more efficiently.

Training data is dominated by English, so most tokens are spent on English; other languages get split into shorter pieces (Spanish hondo → h + ondo), and lower-resource languages sometimes down to single characters.

Poorer representations of meaning, the need for longer contexts, and higher costs to train (and use) models for those languages.

Algorithms should work across languages with different properties; developing and testing only on English (or a few big national languages) excludes most of the world’s roughly 7,000 languages.

African American English and Mainstream American English. AAE features such as iont (MAE I don’t) or talmbout (talking about) affect word segmentation, so tools must handle such varieties.

Using multiple languages within a single utterance, e.g. Spanish–English or Hindi–English mixing in social media posts. It is very common worldwide.

Speakers of mainly oral languages are often diglossic: an oral vernacular for family and local communication, and a vehicular language, usually written, for the wider economy, society or state.

Genre (news, fiction, Wikipedia, conversation, legal or medical text…), the demographics of writers/speakers (age, gender, race, class), and time (language changes).

Documentation by the corpus creator of its motivation, situation, language variety, speaker demographics, collection process (size, sampling, consent, preprocessing), annotation process, and distribution (copyright/IP restrictions).

Formally, an algebraic notation for characterizing a set of strings. Practically, a pattern language for searching text and specifying changes to it; used in grep, editors, every programming language, and BPE pretokenization.

The first match of the pattern inside the string.

In raw strings backslashes are treated literally, so regex escapes like \b or \d reach the regex engine unchanged.

Character disjunction: match any one of the characters inside. [mM]ary matches Mary or mary; [abc] matches a, b or c.

A range: any one character from b to g. [A-Z] is an uppercase letter, [0-9] a digit.

Any single character except a. The caret negates only when it is the first symbol after [; elsewhere (e.g. [e^]) it is a literal caret.

Zero or one occurrence of the previous character or expression: colou?r matches color and colour.

* means zero or more occurrences of the preceding character or expression; + means one or more.

baa+! (or baaa*!). ba*! would also match b! and ba!, since * allows zero as.

[0-9]* also matches the empty string.

{3}: exactly 3 occurrences of the previous character or expression (ax{10}z). .: a wildcard matching any single character except newline.

rose.*rose: .* matches any string of zero or more characters between them.

Special characters that tie a match to a place in the string: ^ matches the start of a line, $ the end. ^The dog\.$ matches a line containing only “The dog.”.

Start of line (anchor), negation as the first symbol inside square brackets, and a literal caret.

\b is a word boundary, \B a non-boundary, where a “word” is a run of letters, digits or underscores. It won’t match inside 299 (99 follows a digit), but will match $99 ($ is not a word character).

They match the empty string at a position without consuming characters, so the following characters remain available to match.

Brackets match a single character from the set. Use the disjunction (pipe) operator: cat|dog.

Sequences bind tighter than |, so it means guppy or ies. Use parentheses: gupp(y|ies).

The * applies only to the preceding space. Group the whole sequence: (Column [0-9]+ +)*.

Parentheses () > counters * + ? {} > sequences and anchors > disjunction |. So the* matches theeee (not thethe), and the|any matches the or any.

Patterns match the largest string they can ([a-z]* on “once upon” matches once). The non-greedy operators *? and +? match as little as possible.

the misses sentence-initial The → [tT]he, which wrongly matches inside other or there → \b[tT]he\b.

False positives are strings incorrectly matched (other); false negatives are strings incorrectly missed (The). Minimizing false positives increases precision; minimizing false negatives increases recall. The two efforts pull against each other.

\d a digit, \w an alphanumeric character or underscore, \s whitespace. \D, \W, \S are their complements.

Escape it with a backslash: \., \*, \[, \\.

Parentheses store what they matched in numbered groups that can be referred to as \1, \2… re.sub(r"(\d{2})/(\d{2})/(\d{4})", r"\2-\1-\3", s) turns 10/15/2011 into 15-10-2011.

\b([A-Za-z]+)\s+\1\b: capture a word, then require the same text again after whitespace.

(?: pattern ): groups for operator precedence without storing the match, e.g. to repeat a long sub-pattern 14 times but capture only the 15th occurrence.

A cascade of substitutions on the uppercased input: first swap pronouns (MY → YOUR, I’M → YOU ARE), then match patterns and rewrite the whole response, e.g. .* YOU ARE (DEPRESSED|SAD) .* → “I AM SORRY TO HEAR YOU ARE \1”.

Zero-width tests on what comes next: (?= pattern) succeeds if the pattern matches, (?! pattern) if it doesn’t, without advancing the match pointer. Negative lookahead is used to rule out special cases.

We · ’re · ␣350 · ␣dogs · ! · ␣Um · , · ␣lunch · ?: contractions split off, words/numbers/punctuation runs separated, leading spaces attached.

Any Unicode letter and any Unicode number (with \P{…} for the complements), in the external regex library, which is more powerful than the built-in re.

Tokenizes naively: -c complements the set (all non-letters), which are changed to newlines, and -s squeezes runs into a single newline, giving one word per line.

Short function words: articles, pronouns, prepositions (the, and, i, to, of, a…).

When tokens must be words: e.g. parsers needing grammatical words as input, linguistic studies with a predefined token definition, or social-science work on orthographic words.

Split off punctuation, but keep word-internal punctuation (m.p.h., Ph.D., AT&T), prices and dates ($45.55, 01/02/06), URLs, hashtags, emails, and numbers with commas (555,500.50). Number formats differ by language (555 500,50).

Expand contractions (what’re → what are, we’re → we are), and optionally keep multiword expressions like New York or rock ’n’ roll as one token using a dictionary, which ties tokenization to named entity recognition.

Used for LDC treebanks: it separates clitics (doesn’t → does + n’t), keeps hyphenated words together, and separates all punctuation (and $ from amounts).

Deterministic regular expressions compiled into efficient finite-state automata (e.g. NLTK’s regexp_tokenize).

Genitive marker (the book’s cover), quotation mark (‘The other class’, she said), or clitic (they’re).

Splitting text into sentences. Question and exclamation marks are fairly unambiguous boundaries; the period is ambiguous.

It marks both sentence ends and abbreviations (Dr., Inc.), sometimes both at once. Segmenters decide whether a period belongs to a word, using rules or ML plus an abbreviation dictionary, often jointly with word tokenization.

Deterministically from tokenization: a sentence ends when ., ! or ? is not already part of another token (abbreviation, number), optionally followed by closing quotes or brackets.

The minimum number of editing operations (insertion, deletion, substitution) needed to transform one string into another.

A correspondence between substrings of two sequences, often shown with an operation row (d, s, i) below the aligned strings.

D R I V E *
| | | | | |
B R I * E F
s     d   i

Turning drive into brief: substitute d→b, delete v, insert f (Levenshtein distance 3).

Each insertion, deletion and substitution costs 1 (identity substitution costs 0). In the alternative version substitutions are disallowed, equivalently cost 2 (a deletion plus an insertion).

Many edit paths reach the same intermediate string, and the optimal path to the target must include the optimal path to every intermediate string on it. So we store the best solution for each subproblem in a table instead of searching all paths.

A class of table-driven algorithms (Bellman, 1957) that solve problems by combining solutions to subproblems. In NLP: minimum edit distance, Viterbi, CKY parsing.

The edit distance between the first \(i\) characters of the source and the first \(j\) characters of the target. Base cases: \(D[i,0] = i\) deletions, \(D[0,j] = j\) insertions. The answer is \(D[n,m]\).

\(D[i,j] = \min\{D[i-1,j] + \text{del}(x_i),\; D[i,j-1] + \text{ins}(y_j),\; D[i-1,j-1] + \text{sub}(x_i, y_j)\}\), with \(\text{sub}(x,x) = 0\).

Store backpointers in each cell to the neighbor(s) the minimum came from, then backtrace from \(D[n,m]\) to \(D[0,0]\). Each complete path is a minimum-cost alignment: a horizontal step is an insertion, a vertical step a deletion, a diagonal step a match or substitution.

Computing word error rate in speech recognition, matching sentences in a parallel corpus for MT, and spelling correction.

Some errors are more likely, e.g. substitutions between letters that are adjacent on the keyboard, so the algorithm allows letter-specific weights.

It is a probabilistic extension: instead of the minimum-cost alignment of two strings it computes the maximum-probability alignment.

It was a text compression method (Gage, 1994), applied to subword tokenization for neural MT by Sennrich et al. (2016), then adopted as the default by OpenAI’s GPT-2 and included in SentencePiece.

Kleene (1951, 1956), along with finite automata, based on the McCulloch–Pitts neuron. Ken Thompson built regexes into editors; his ed command g/regular expression/p (Global Regular Expression Print) became Unix grep.

To hide that it was mathematical research from a Secretary of Defense who hated the word “research”: “dynamic” conveys multi-stage and is impossible to use pejoratively.