Trie Serialization Algorithm
Relevant source files
The following files were used as context for generating this wiki page:
The Trie Serialization Algorithm in the entities library is designed to convert high-level trie structures representing character entities into a highly compact binary format, typically a Uint16Array. The primary goal is to minimize memory consumption and maximize traversal speed during decoding. This approach reduces character reference data from approximately 8.5MB to 250KB.
The algorithm utilizes several optimization techniques, including node deduplication, value inlining, compact runs for linear paths, and multiple branch encoding strategies (jump tables vs. sparse dictionaries) based on key density.
Sources: scripts/trie/README.md:1-15, scripts/trie/encode-trie.ts:20-25
Binary Node Layout
Every node in the serialized trie begins with a single 16-bit header word. This header uses specific bit fields to store metadata about values, flags, and branch structures.
Header Bit Fields
| Bits | Field | Description |
|---|---|---|
| 15..14 | Value Length | Encoded length: 0 (None), 1 (Inline), 2 (1 code unit out-of-line), 3 (2 code units out-of-line). |
| 13 | Dual-use Flag | If Value > 0: Semicolon-required flag. If Value == 0: Compact run flag. |
| 12..7 | Branch Length | Meaning depends on mode: Run length, Branch count, or Jump table span. |
| 6..0 | Branch Data | Jump table offset, first character of a run/single branch, or packed info. |
Sources: scripts/trie/README.md:40-52, scripts/trie/encode-trie.ts:37-45
Value Encoding Logic
The encoder determines how to store the character value (if any) associated with a node.
- Inline (Value Length 1): If a value is a single code unit that fits within 14 bits and doesn't collide with flag bits, it is stored directly in the header.
- Out-of-line (Value Length 2 or 3): If the value is two code units or cannot be inlined, it is stored in the array elements immediately following the header.
Sources: scripts/trie/README.md:54-66, scripts/trie/encode-trie.ts:36-55
Branch Optimization Strategies
The algorithm dynamically chooses between three different branch encodings to optimize for space and speed based on the distribution of child keys.
Logic flow for determining the branch encoding strategy during serialization.
Sources: scripts/trie/encode-trie.ts:109-150, scripts/trie/README.md:92-110
1. Single Branch Inlined
If a node has exactly one child and that child is not yet cached, the branch character is stored in bits 6..0 of the current header. The child node header follows immediately after.
Sources: scripts/trie/README.md:95-99, scripts/trie/encode-trie.ts:117-122
2. Jump Table
Used when branch keys form a dense range (determined by maxJumpTableOverhead).
- Header: Bits 6..0 store the minimum key (offset); bits 12..7 store the span.
- Data: A table of
Uint16slots follows. Each slot containsdestinationIndex + 1. A0indicates no branch for that key.
Sources: scripts/trie/README.md:100-103, scripts/trie/encode-trie.ts:127-149
3. Sparse Dictionary
Used for sparse keys that would make a jump table inefficient.
- Keys: Sorted keys are packed two per 16-bit word (8-bit keys).
- Destinations: A raw array of destination indices follows the packed keys.
Sources: scripts/trie/README.md:104-108, scripts/trie/encode-trie.ts:151-177
Path Compression: Compact Runs
When a node has no value and leads into a linear chain of at least three single-child nodes, the encoder collapses the path into a "Compact Run". This prevents excessive pointer chasing for long entity names.
- Header: Bit 13 is set as the run flag. Bits 12..7 store the run length (up to 63). Bits 6..0 store the first character.
- Storage: The remaining characters are packed two per 16-bit word (low byte/high byte) immediately after the header.
- Termination: The final node in the run (which has branches or a value) is then encoded in normal form.
Sources: scripts/trie/README.md:78-87, scripts/trie/encode-trie.ts:65-98, scripts/trie/compact-run.spec.ts:13-33
Data Compression and Delta Encoding
For large tries, the library uses a secondary serialization layer involving a dictionary and delta-encoded value table to further reduce the size of the generated JavaScript files.
The encodeTrieData Process
- Frequencies: Value frequencies are counted to identify the most common trie entries.
- Dictionaries:
dict1: The 61 most frequent values (1-char codes).dict2: Remaining unique values (2-char codes).
- Delta/RLE Encoding: Values in the header are delta-encoded (storing the difference from the previous value) and use Run-Length Encoding (RLE) for consecutive increments of 1.
- Base-91: The resulting data is encoded into a string using 91 printable ASCII characters.
Sources: scripts/write-decode-map.ts:39-120, src/internal/decode-shared.ts:25-70
Process for converting the raw binary trie into a compressed base-91 string for distribution.
Sources: scripts/write-decode-map.ts:132-192, src/internal/decode-shared.ts:30-80
Node Deduplication
To ensure the smallest possible size, the algorithm uses a cache to identify identical subtrees. The mergeDuplicates function in the trie builder and the encodeCache in the encoder ensure that recursive or repeated structures point to the same indices in the final array.
Sources: scripts/trie/trie.ts:74-100, scripts/trie/encode-trie.ts:27-31, scripts/trie/encode-trie.spec.ts:51-68
Summary
The Trie Serialization Algorithm transforms complex entity maps into a compact binary format by combining structural optimizations (compact runs, jump tables, deduplication) with data-level compression (delta-encoded base-91). This multi-layered approach ensures that the resulting entities package remains lightweight and performant across different environments.