Part 9 · 6 chapters · ~40 min

Text And Encoding

A string has four lengths and the user means the one JavaScript does not give you directly. This part is bytes, code units, code points and graphemes, UTF-8 decoding as a state machine, grapheme and word segmentation by rule, the bidirectional algorithm and Liang hyphenation in outline, fuzzy matching by dynamic programming and by bits with the cheap filters that make it fast, a table of every text algorithm with its unit and API, and the course in one page.

52

Bytes, code units, code points, graphemes

the question

"The input has a 20-character limit. The user typed 12 emoji and it rejected them. Which length is right?"

There are four lengths for one string, and the one the user means is the one JavaScript does not give you directly. Bytes (UTF-8 on the wire), code units (UTF-16, what .length counts), code points (what [...str] iterates), and grapheme clusters (what the user perceives as characters, from Intl.Segmenter). A family emoji is 25 bytes, 11 code units, 7 code points and 1 grapheme. Every text algorithm in this part starts by choosing the unit.

the four
  1. Bytes (UTF-8): 1 to 4 per code point. What fetch delivers, what files hold, what Buffer.byteLength and TextEncoder count. Self-synchronising; ASCII is one byte each.
  2. UTF-16 code units: what JavaScript strings are made of. One unit for the Basic Multilingual Plane; a surrogate pair (two units, D800 to DFFF) for everything above U+FFFF (most emoji, many CJK extension characters, historic scripts). .length, indexing, slice, charCodeAt operate on units and can split a pair.
  3. Code points: Unicode scalar values. codePointAt, String.fromCodePoint, the string iterator (for...of, spread) work in code points. A combining mark is its own code point.
  4. Grapheme clusters: UAX #29's "user-perceived characters": base plus combining marks, emoji sequences, Hangul jamo sequences, regional indicator pairs. Intl.Segmenter with granularity: 'grapheme'. The unit for cursor movement, backspace, visible counts, truncation, and reversal.
the operations and their right unit
  1. Storage limits (database columns, protocol fields): bytes.
  2. User-facing limits ("20 characters"): graphemes, with the byte limit enforced separately and explained.
  3. Truncation with an ellipsis: graphemes, or you cut a flag in half.
  4. Searching and comparison: code points, after normalisation (NFC), so that é as one code point equals e + combining acute as two.
  5. Indexing into a string for editing: code units are what the DOM's selectionStart gives you; convert to graphemes for cursor logic.
  6. Sorting: Intl.Collator (locale rules: case, accents, digits), never code unit order.
the sizes
Intl.Segmenter runs ICU's UAX #29 implementation at tens of MB/s; segmenting a 10 KB field is microseconds. Creating the segmenter is the expensive part (locale data); make one and reuse it.
UTF-8 DECODING AS A STATE MACHINE
bytes to code points, with the invalid cases
swipe the figure sideways, or tap expand for full screen
1/6
the patterns
The byte patterns: 0xxxxxxx is one byte (ASCII, 7 bits). 110xxxxx 10xxxxxx is two bytes (11 bits: U+0080 to U+07FF). 1110xxxx 10xxxxxx 10xxxxxx is three (16 bits: the rest of the BMP). 11110xxx + three continuations is four (21 bits: U+10000 to U+10FFFF). Every continuation byte is 10xxxxxx.
53

UTF-8 decoding as a state machine

UTF-8 is a variable-length encoding designed so that a decoder is a small automaton and a corrupt byte loses at most one character. The decoder every fetch runs is that automaton, vectorised; knowing it explains the replacement characters, the stream chunk boundary problem, and why the encoding is safe to scan backwards.

the encoding
  1. Lead bytes carry the length in their leading bits: 0xxxxxxx (1 byte), 110xxxxx (2), 1110xxxx (3), 11110xxx (4). Continuation bytes are 10xxxxxx, six payload bits each.
  2. Self-synchronising: a continuation byte can never be mistaken for a lead byte or ASCII; a decoder dropped at any offset finds the next character boundary within three bytes. Byte-oriented tools (grep, split on \n) work on UTF-8 text without decoding.
  3. Shortest form only: a code point must use the fewest bytes possible; overlong encodings (C0 80 for U+0000) are invalid. Historically a security hole: filters checked for / after decoding while attackers sent its overlong form.
  4. Range: U+0000 to U+10FFFF, excluding surrogates D800 to DFFF (which are UTF-16 artefacts and invalid as code points in UTF-8).
the decoder
  1. A DFA (Hoehrmann's is the reference): a 256-entry table classifies each byte into about a dozen classes; a transition table maps (state, class) to the next state; the accumulator shifts in six bits per continuation. One table lookup per byte, no branches in the loop; invalid sequences land in a reject state.
  2. Error handling: on reject, emit U+FFFD and resume at the next lead byte (the "maximal subpart" rule decides how many bytes one replacement covers). TextDecoder does this by default; { fatal: true } throws instead.
  3. Vectorised: validation and transcoding at several GB/s with SIMD (simdutf, used by Node and by browsers): check 16 to 64 bytes per instruction for the ASCII fast path, then classify lead bytes in bulk.
  4. Streaming: a chunk may end mid-sequence; new TextDecoder().decode(chunk, { stream: true }) keeps the partial bytes for the next call. Decoding chunks independently produces replacement characters at every chunk boundary that split a character.
the other encodings you will meet
  1. UTF-16: JavaScript strings, Windows APIs, Java. Surrogate pairs for the astral planes; byte order marks for files.
  2. Latin-1 / Windows-1252: legacy; one byte per character; what a server without a charset header may be sending. TextDecoder('windows-1252').
  3. Base64: not a text encoding; a binary-to-ASCII transport. 4 characters per 3 bytes; atob/btoa operate on Latin-1 "binary strings", so btoa of a UTF-8 string needs TextEncoder first (or Uint8Array.toBase64(), now shipping).
  4. Percent-encoding: URLs; UTF-8 bytes as %XX; encodeURIComponent encodes everything but unreserved characters.
54

Grapheme cluster segmentation

The segmentation algorithm (UAX #29) decides where one user-perceived character ends and the next begins. It assigns each code point a break property and applies a short ordered list of "do not break here" rules; everything else is a boundary. The rules are few; the data (which code point has which property) is large and locale-independent for graphemes, locale-dependent and dictionary-based for words.

the algorithm
  1. Property lookup: each code point maps to a Grapheme_Cluster_Break value: Control, CR, LF, Extend (combining marks, variation selectors, emoji modifiers), ZWJ, Regional_Indicator, Prepend, SpacingMark, the Hangul types L, V, T, LV, LVT, Extended_Pictographic (emoji bases), Other. Stored as range tables or a two-level trie.
  2. The rules, applied between each pair of adjacent code points, in order: GB3 CR × LF (do not break); GB4/5 break around controls; GB6 to GB8 keep Hangul syllable sequences together; GB9 do not break before Extend or ZWJ; GB9a/b SpacingMark and Prepend; GB11 do not break within an emoji ZWJ sequence (an Extended_Pictographic, Extend*, ZWJ, then another Extended_Pictographic); GB12/13 do not break between pairs of regional indicators (but do between pairs); GB999 otherwise break.
  3. Lookback: GB11 and GB12/13 need to know how the current sequence started (is this ZWJ preceded by an emoji base; is this the odd or even regional indicator), so implementations track a small state while scanning. Still O(n).
words and sentences
  1. Word boundaries (UAX #29 WB rules): letters, numbers, apostrophes within words, and for scripts without spaces (Thai, Lao, Khmer, Burmese, Japanese, Chinese) a dictionary-based segmenter that finds the most likely word sequence (a dynamic programming over a lexicon, like line breaking's). Intl.Segmenter with granularity: 'word' exposes it; isWordLike on each segment separates words from punctuation.
  2. Sentence boundaries: terminators, closers and the following space, with abbreviation handling via locale data.
  3. Line break opportunities are a separate algorithm (UAX #14) with its own classes; part 3's line breaking consumes it.
what to do with it
  1. Backspace deletes a cluster, not a code unit; the browser's inputs do this; a custom editor must.
  2. Counts shown to users are clusters. Limits enforced in bytes should say so.
  3. Truncation: segment, take N clusters, add the ellipsis.
  4. Reversal, column alignment, character-level animation: clusters.
  5. Normalise before comparing (str.normalize('NFC')) so composed and decomposed forms match; segment either form.
GRAPHEME CLUSTER SEGMENTATION
what a user calls one character
swipe the figure sideways, or tap expand for full screen
1/6
Yoruba
The string "Ẹ̀kọ́" (Yoruba): code points E (U+0045), combining dot below (U+0323), combining grave (U+0300), k, ọ as o (U+006F) + dot below, then combining acute (U+0301). 8 code points; the user sees 3 characters: Ẹ̀, k, ọ́.
55

Bidi and hyphenation

code
// the Unicode Bidirectional Algorithm (UAX #9), in outline: how "Hello مرحبا 123 world" is laid out
// 1. classify: each code point gets a bidi class: L (Latin), R (Hebrew), AL (Arabic letter), EN (European number), WS, ON (punctuation)…
// 2. paragraph level: 0 (LTR) if the first strong character is L; 1 (RTL) if R/AL. dir="auto" on an element does exactly this; dir="rtl" forces 1
// 3. explicit embeddings: LRE/RLE/LRO/RLO/PDF and the isolates LRI/RLI/FSI/PDI (or CSS unicode-bidi: isolate / bidi-override) push/pop levels
// 4. resolve weak types: numbers take direction from context (EN after AL becomes AN-ish; "123" after Arabic displays within the RTL run)
// 5. resolve neutrals: spaces and punctuation between two runs of the same direction take that direction; otherwise the embedding direction
// 6. implicit levels: L in an RTL paragraph → level 2; R/AL in LTR → level 1; numbers one level above their context
// 7. reorder: for each line, reverse every contiguous run at level ≥ k, for k from the highest level down to 1
// the result for level 0 paragraph: [Hello ] [ابحرم] [ 123] [ world] → the Arabic run is reversed for display; "123" sits to its visual left
// cost: O(n) classification + O(n × levels) reordering per line, after line breaking (part 3). the browser does it per inline formatting context.
// the bugs it explains: punctuation jumping sides (neutral resolution), numbers in the "wrong" place (weak types), and why dir="auto" + unicode-bidi: isolate
// on user-generated snippets keeps a mixed-direction UI stable (the browser course part 11)
the bidirectional algorithm
  1. Classify each code point (strong L, R, AL; weak EN, ES, ET, AN, CS, NSM, BN; neutral B, S, WS, ON; explicit formatting characters).
  2. Paragraph direction from the first strong character (or forced by dir).
  3. Explicit embeddings and isolates adjust levels; isolates (unicode-bidi: isolate, the default for dir) keep a run from influencing its neighbours' neutral resolution, which is the fix for punctuation jumping sides around user-generated text.
  4. Weak and neutral resolution: numbers take their surroundings' direction with special rules; spaces and punctuation between same-direction runs join them, otherwise take the paragraph direction.
  5. Implicit levels and reordering: compute an embedding level per character; per line (after line breaking), reverse runs from the deepest level outward. O(n) per line.
  6. In the browser: run per inline formatting context during layout (part 3); the browser course part 11 has where it sits. CSS: direction, unicode-bidi, logical properties (margin-inline-start) so layout follows direction.
code
// Liang's hyphenation algorithm (TeX, 1983): what hyphens: auto runs
// patterns: a few thousand per language, each a letter sequence with odd/even digits between letters: "hy3ph", "1na", "n2at", "he2n"
//   odd digit = a hyphen is allowed here; even = forbidden; higher wins. patterns were derived by machine from a dictionary (patgen)
// algorithm: for the word ".hyphenation." (dots mark edges), find every pattern that occurs as a substring (a trie walk from each position: O(n × max pattern length)),
//   superimpose their digits onto the inter-letter positions taking the max at each position; a hyphen is allowed where the final digit is odd
//   (and not within the first lefthyphenmin / last righthyphenmin letters)
// "hyphenation" → h y3p h e2n a1t i o n → hy-phen-ation
// cost: microseconds per word; the pattern set is 20 to 60 KB per language (why browsers ship them per locale and need lang= to pick one)
// the output feeds line breaking (part 3): extra break opportunities with a penalty, which lets greedy and optimal breakers make tighter lines
hyphenation
  1. Liang's patterns: a few thousand letter patterns per language with digits marking allowed (odd) and forbidden (even) break points, derived by machine from dictionaries. A word is matched against all patterns that occur in it (a trie walk from each position); the maximum digit at each position decides.
  2. Cost: O(word length × pattern length) per word; microseconds. The pattern files are 20 to 60 KB per language, which is why hyphens: auto needs a lang attribute to pick one and why browsers ship them lazily.
  3. Effect: extra break opportunities with a penalty, consumed by line breaking (part 3). Justified text and narrow columns go from ragged to even; the greedy breaker benefits as much as the optimal one.
  4. Limits: patterns are not a dictionary; rare words and names can be hyphenated wrongly (­ soft hyphens override per word). Compound words in German and Dutch need the language's specific patterns.
56

Fuzzy matching: edit distance and bitap

Typo-tolerant search means scoring candidates by how far they are from the query. The exact measure, Levenshtein edit distance, is a dynamic programme over a grid and costs O(m × n) per candidate: fine for a shortlist, too slow for a whole collection per keystroke. Fast search uses a cheap filter to make the shortlist, then the exact measure on it.

edit distance
  1. Definition: the minimum number of single-character insertions, deletions and substitutions turning one string into the other (Damerau adds adjacent transpositions, the most common typo).
  2. The table: D[i][j] is the distance between the first i characters of A and the first j of B. D[0][j] = j, D[i][0] = i; D[i][j] = min(D[i−1][j] + 1, D[i][j−1] + 1, D[i−1][j−1] + (A[i] ≠ B[j])). Fill row by row; the corner is the answer; backtrack for the edits.
  3. Cost: O(m × n) time; O(min(m, n)) space for the distance only. A banded version (only cells within k of the diagonal) is O(k × n) when only distances up to k matter, which for search is always (nobody wants matches at distance 5).
  4. In code units or graphemes? Graphemes, for user-facing matching (one wrong accent is one edit); normalise first.
bitap
  1. Precompute a bitmask per alphabet character for the query: bit p set if the query's character at position p is that character.
  2. Scan the candidate with a state register R: R = ((R << 1) | 1) & mask[c] per character; bit m−1 set means the query ends here. O(n) per candidate, a handful of instructions per character.
  3. With k errors: k+1 registers; each level ORs in the previous level's substitutions, insertions and deletions. Still O(n × k). Limited to queries that fit a machine word (32 characters in JavaScript's bitwise ops; libraries split longer ones).
  4. Where: agrep, Fuse.js (with a scoring function over the match position and error count), many editor "fuzzy finders" (which also weight consecutive matches and word starts).
candidate generation
  1. N-gram index: map each trigram to the candidates containing it; a query's trigrams union to a shortlist that shares at least one; score the shortlist. Index size is linear in total text; query cost is linear in the shortlist.
  2. SymSpell: precompute every deletion variant (up to k deletions) of every dictionary word into a Map; a query's deletion variants hit the Map in O(1) each; verify hits with the real distance. Index is large (×100 for k = 2); queries are microseconds. The structure behind modern spell checkers.
  3. BK-trees (a metric tree over edit distance) and Levenshtein automata (a DFA accepting all strings within k of the query, intersected with a trie of the dictionary) are the other classic options; the trie intersection is what Lucene uses.
  4. The pattern: the same as the bloom filter before the ancestor walk (part 2) and culling before raster (part 4): a cheap conservative filter, then the expensive exact check on survivors.
FUZZY MATCHING
edit distance by dynamic programming, and the faster bitap
swipe the figure sideways, or tap expand for full screen
1/6
the table
Distance between "kitten" and "sitting". The table: rows for prefixes of "kitten", columns for prefixes of "sitting". Cell (i, j) = the distance between the first i letters of one and the first j of the other. Row 0 and column 0 are 0, 1, 2, … (deleting or inserting everything).
57

Text algorithms: the table, and the course's end

ProblemAlgorithmComplexityUnitAPI / tool
Bytes → stringUTF-8 DFA (Hoehrmann), vectorisedO(bytes)Bytes → code unitsTextDecoder (stream, fatal)
String → bytesUTF-8 encoding with surrogate pairingO(units)Code units → bytesTextEncoder; Buffer.from
User-perceived charactersUAX #29 grapheme rules over break propertiesO(n)GraphemesIntl.Segmenter('grapheme')
Words (incl. no-space scripts)UAX #29 word rules + dictionary DPO(n) / O(n × dict)WordsIntl.Segmenter('word')
Line break opportunitiesUAX #14 classes + pair tableO(n)OpportunitiesThe layout engine (part 3)
HyphenationLiang patterns via a trieO(word × pattern)Lettershyphens: auto + lang; Hypher in JS
BidiUAX #9: classify, levels, reorder per lineO(n × levels)Code pointsThe layout engine; dir, unicode-bidi
Equality under compositionNormalisation (NFC/NFD/NFKC/NFKD): decompose, reorder marks, composeO(n)Code pointsString.prototype.normalize
Case mappingLocale-aware tables (Turkish i, German ß, Greek sigma)O(n)Code pointstoLocaleUpperCase; Intl
OrderingUCA collation: multi-level keys (base, accent, case)O(n) key + sortCollation elementsIntl.Collator (reuse one)
Exact substringBoyer-Moore-Horspool / two-way; memchr fast pathsO(n) typicalCode unitsindexOf, includes
Pattern matchingBacktracking regex (Irregexp) or linear-time automatonExponential worst / O(n) linearCode units (u flag: code points; v flag: sets)RegExp; the l flag for linear
Fuzzy matchingLevenshtein DP; bitap; n-gram or SymSpell candidatesO(mn) / O(n) / O(1) per lookupGraphemes or code pointsFuse.js, MiniSearch, SymSpell ports
Diffing textMyers O(nd) on lines or words; cleanup passesO((n+m) d)Lines / words / graphemesdiff, diff-match-patch
Format numbers, dates, plurals, listsCLDR data tablesO(1) per valueLocaleIntl.NumberFormat, DateTimeFormat, PluralRules, ListFormat, RelativeTimeFormat
the course, in one page
  1. Sizes: a UI's n makes linear free and quadratic fatal; the line is one table; the fix is a lookup, a batch, a key, or a boundary. (P0)
  2. You write: timers for rate limiting; prefix sums and binary search for windows; keyed diffs with LIS for lists; Map-ordered LRU; inverted indexes for search; TimSort with cheap comparators; topological order for derived state; heaps for schedulers. (P1)
  3. The platform runs: right-to-left matching with buckets and a bloom filter, and invalidation sets (P2); one-pass block, greedy lines, flex clamp loops, grid fixpoints (P3); seven paint phases, culled display lists, tiled damage (P4); priority queues in the loop and bits in React (P5); tries, inline caches, Cheney, tri-colour (P6); two heuristics and a resumable walk (P7); state machines, Pratt, SSA, linear scan, reachability (P8); DFAs, UAX #29, UAX #9, Liang, Levenshtein (P9).
  4. The shapes that recur: scan → lookup (Map, index, trie); expensive check behind a cheap filter (bloom, culling, n-grams); recompute only dependents (damage, dirty marks, bailouts, DCE); dynamic programming where greed fails (LCS, Knuth-Plass, edit distance) and greed where it is good enough (line breaking in browsers, React's diff).
what to do next
Take the slowest interaction in something you own. Find n. Scale it. Name the shape. Then find which of parts 2 to 9 is running underneath, and read that part again with the profiler open.