1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

class TrieNode {
  children: Map<string, TrieNode>;
  isTerminal: boolean;
  // Store the complete word at terminal nodes for easy retrieval
  word: string | null;
  // Metadata for ranking (frequency, score, etc.)
  metadata: {
    frequency: number;
    lastUpdated: number;
  } | null;
 
  constructor() {
    this.children = new Map();
    this.isTerminal = false;
    this.word = null;
    this.metadata = null;
  }
}
 
class Trie {
  private root: TrieNode;
 
  constructor() {
    this.root = new TrieNode();
  }
 
  /**
   * Insert a word into the trie
   * Time: O(m) where m = word length
   * Space: O(m) worst case (no shared prefix)
   */
  insert(word: string, frequency: number = 1): void {
    let current = this.root;
    
    for (const char of word.toLowerCase()) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char)!;
    }
    
    current.isTerminal = true;
    current.word = word;
    current.metadata = {
      frequency,
      lastUpdated: Date.now(),
    };
  }
 
  /**
   * Find the node corresponding to a prefix
   * Time: O(m) where m = prefix length
   */
  private findPrefixNode(prefix: string): TrieNode | null {
    let current = this.root;
    
    for (const char of prefix.toLowerCase()) {
      if (!current.children.has(char)) {
        return null;
      }
      current = current.children.get(char)!;
    }
    
    return current;
  }
 
  /**
   * Get all words with the given prefix
   * Time: O(m + k) where m = prefix length, k = results
   */
  getWordsWithPrefix(prefix: string, limit: number = 10): string[] {
    const prefixNode = this.findPrefixNode(prefix);
    if (!prefixNode) {
      return [];
    }
    
    const results: { word: string; frequency: number }[] = [];
    this.collectWords(prefixNode, results, limit * 2); // Collect extra for sorting
    
    // Sort by frequency and return top results
    return results
      .sort((a, b) => b.frequency - a.frequency)
      .slice(0, limit)
      .map(r => r.word);
  }
 
  /**
   * Recursively collect all terminal words under a node
   */
  private collectWords(
    node: TrieNode,
    results: { word: string; frequency: number }[],
    limit: number
  ): void {
    if (results.length >= limit) return;
    
    if (node.isTerminal && node.word) {
      results.push({
        word: node.word,
        frequency: node.metadata?.frequency ?? 0,
      });
    }
    
    for (const child of node.children.values()) {
      this.collectWords(child, results, limit);
    }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Corpus: 1 billion suggestions
Average suggestion length: 25 characters
Raw string storage: 25 GB
 
Naive trie (Map-based, no optimization):
- Each node: ~100 bytes (Map overhead, pointers)
- Estimated nodes: 10B (due to prefix sharing ~10 nodes/word)
- Total: ~1 TB (unacceptable)
 
Optimized trie (array-based, compressed):
- Each node: ~16-32 bytes
- Compressed paths: ~5B effective nodes
- Total: ~80-160 GB (fits in modern server RAM)
 
With radix compression:
- Merge single-child chains
- Further reduce to ~50-100 GB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Standard Trie for ["romane", "romanus", "romulus"]:
 
        (root)
          |
         'r'
          |
         'o'
          |
         'm'
        / | \
      'a' 'a' 'u'
       |   |    |
      'n' 'n'  'l'
       |   |    |
      'e'●'u'  'u'
            |    |
           's'● 's'●
 
Radix Trie (compressed):
 
        (root)
          |
        "rom"
        /    \
      "an"   "ulus"●
      /  \
   "e"●  "us"●
 
Reduction: 11 nodes → 6 nodes (45% fewer)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

interface RadixTrieNode {
  // Edge label can be multiple characters
  edgeLabel: string;
  
  // Children indexed by first character of edge
  children: Map<string, RadixTrieNode>;
  
  isTerminal: boolean;
  word: string | null;
  metadata: SuggestionMetadata | null;
}
 
interface RadixTrie {
  root: RadixTrieNode;
  
  insert(word: string, metadata: SuggestionMetadata): void {
    // On insert, may need to split existing edges
    // Example: inserting "roman" when "romane" exists
    // requires splitting "romane" into "roman" + "e"
  }
  
  search(prefix: string): RadixTrieNode | null {
    // Navigate by matching edge labels
    // A single edge match can consume multiple characters
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

interface TSTNode {
  char: string;              // The character at this node
  left: TSTNode | null;      // Characters < char
  middle: TSTNode | null;    // Continuation (next char of same word)
  right: TSTNode | null;     // Characters > char
  isTerminal: boolean;
  word: string | null;
}
 
// Search in TST
function searchTST(node: TSTNode | null, word: string, index: number): TSTNode | null {
  if (!node || index >= word.length) return null;
  
  const char = word[index];
  
  if (char < node.char) {
    return searchTST(node.left, word, index);
  } else if (char > node.char) {
    return searchTST(node.right, word, index);
  } else {
    // char === node.char
    if (index === word.length - 1) {
      return node; // Found the prefix
    }
    return searchTST(node.middle, word, index + 1);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

const ALPHABET_SIZE = 128; // ASCII
 
interface AMTNode {
  // Fixed-size array indexed by character code
  // children[65] = child for 'A' (ASCII 65)
  children: (AMTNode | null)[];
  isTerminal: boolean;
  word: string | null;
  metadata: SuggestionMetadata | null;
}
 
function createNode(): AMTNode {
  return {
    children: new Array(ALPHABET_SIZE).fill(null),
    isTerminal: false,
    word: null,
    metadata: null,
  };
}
 
function insert(root: AMTNode, word: string): void {
  let current = root;
  
  for (const char of word) {
    const index = char.charCodeAt(0);
    if (!current.children[index]) {
      current.children[index] = createNode();
    }
    current = current.children[index]!;
  }
  
  current.isTerminal = true;
  current.word = word;
}
 
// Benefits:
// 1. O(1) child lookup vs O(log k) for Maps
// 2. Better cache locality (contiguous memory)
// 3. Simpler memory layout for serialization
//
// Tradeoffs:
// 1. Wastes space for sparse nodes
// 2. Fixed alphabet size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class StringInterner {
  private pool: Map<string, string> = new Map();
  
  intern(s: string): string {
    const existing = this.pool.get(s);
    if (existing) {
      return existing; // Return the canonical instance
    }
    this.pool.set(s, s);
    return s;
  }
}
 
// Usage: Store only one instance of common substrings
const interner = new StringInterner();
 
// Instead of each node storing its own "the" string:
node.edgeLabel = interner.intern(rawLabel);
 
// Memory impact: If "the" appears in 1M edge labels,
// we store it once instead of 1M times
// Savings: ~3 bytes × 1M = 3 MB per common substring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

interface CompactNode {
  // Bitmap indicating which characters have children
  // For ASCII 128 chars, need 2 × 64-bit integers
  childBitmap: [bigint, bigint];
  
  // Compact array containing only non-null children
  // Position in array determined by popcount of bitmap
  children: CompactNode[];
  
  isTerminal: boolean;
  metadata: number; // Index into separate metadata array
}
 
function getChild(node: CompactNode, char: string): CompactNode | null {
  const charCode = char.charCodeAt(0);
  const bitmapIndex = charCode < 64 ? 0 : 1;
  const bitPosition = charCode % 64;
  
  // Check if child exists
  const mask = 1n << BigInt(bitPosition);
  if ((node.childBitmap[bitmapIndex] & mask) === 0n) {
    return null;
  }
  
  // Calculate position in children array using popcount
  let position = 0;
  if (bitmapIndex === 1) {
    position += popcount(node.childBitmap[0]);
  }
  position += popcount(node.childBitmap[bitmapIndex] & (mask - 1n));
  
  return node.children[position];
}
 
function popcount(n: bigint): number {
  // Count number of 1 bits (CPU has dedicated instruction)
  let count = 0;
  while (n > 0n) {
    count += Number(n & 1n);
    n >>= 1n;
  }
  return count;
}
 
// Memory savings: 
// Standard: 128 pointers × 8 bytes = 1024 bytes/node
// Bitmap: 16 bytes bitmap + (avg 3 children × 8 bytes) = 40 bytes/node
// 25× reduction!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Standard trie:
       (root)
       /  |  \
      A   B   C
     /|       |
    D E       F
    |
    G
 
LOUDS encoding (bit sequence):
Level 0 (root): 1110   (3 children: A, B, C)
Level 1 (A,B,C): 110 0 10   (A:2 children, B:0, C:1)
Level 2 (D,E,F): 10 0 0   (D:1 child, E:0, F:0)
Level 3 (G): 0   (G:0 children)
 
Full sequence: 1110 110 0 10 10 0 0 0
 
Space: 2 bits per node (vs ~100+ bytes per node in naive impl)
Navigation uses rank/select operations on bit vectors

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

interface TrieNodeWithTopK {
  children: Map<string, TrieNodeWithTopK>;
  isTerminal: boolean;
  
  // Pre-computed top-K for this prefix
  topK: {
    word: string;
    score: number;
  }[];
  
  // K value (typically 10-20)
  static readonly K = 15;
}
 
class TrieWithTopK {
  private root: TrieNodeWithTopK;
  
  insert(word: string, score: number): void {
    let current = this.root;
    
    for (const char of word.toLowerCase()) {
      // Update top-K at every node along the path
      this.updateTopK(current, word, score);
      
      if (!current.children.has(char)) {
        current.children.set(char, this.createNode());
      }
      current = current.children.get(char)!;
    }
    
    this.updateTopK(current, word, score);
    current.isTerminal = true;
  }
  
  private updateTopK(node: TrieNodeWithTopK, word: string, score: number): void {
    // Check if this word should be in top-K
    const existingIndex = node.topK.findIndex(e => e.word === word);
    
    if (existingIndex !== -1) {
      // Update existing entry
      node.topK[existingIndex].score = score;
    } else if (node.topK.length < TrieNodeWithTopK.K) {
      // Add new entry
      node.topK.push({ word, score });
    } else if (score > node.topK[node.topK.length - 1].score) {
      // Replace lowest entry
      node.topK.pop();
      node.topK.push({ word, score });
    }
    
    // Keep sorted by score
    node.topK.sort((a, b) => b.score - a.score);
  }
  
  getSuggestions(prefix: string): string[] {
    const node = this.findPrefixNode(prefix);
    if (!node) return [];
    
    // O(1) retrieval - just return pre-computed list!
    return node.topK.map(e => e.word);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import { MinPriorityQueue } from '@datastructures-js/priority-queue';
 
function getTopKSuggestions(
  prefixNode: TrieNode,
  k: number
): Suggestion[] {
  // Max-heap to track top-K during traversal
  const topK = new MinPriorityQueue<Suggestion>(
    (s) => -s.score // Negate for max-heap behavior
  );
  
  // Priority queue for DFS - explore high-score subtrees first
  const toExplore = new MaxPriorityQueue<{
    node: TrieNode;
    maxPossibleScore: number;
  }>((item) => item.maxPossibleScore);
  
  toExplore.enqueue({
    node: prefixNode,
    maxPossibleScore: prefixNode.maxDescendantScore ?? Infinity,
  });
  
  while (!toExplore.isEmpty()) {
    const { node, maxPossibleScore } = toExplore.dequeue()!;
    
    // Pruning: if best possible score in subtree is worse than
    // our worst top-K entry, skip this subtree entirely
    if (topK.size() >= k && maxPossibleScore <= topK.front()!.score) {
      continue;
    }
    
    // Process terminal node
    if (node.isTerminal && node.word && node.metadata) {
      const suggestion = {
        word: node.word,
        score: node.metadata.score,
      };
      
      if (topK.size() < k) {
        topK.enqueue(suggestion);
      } else if (suggestion.score > topK.front()!.score) {
        topK.dequeue();
        topK.enqueue(suggestion);
      }
    }
    
    // Add children to explore
    for (const child of node.children.values()) {
      toExplore.enqueue({
        node: child,
        maxPossibleScore: child.maxDescendantScore ?? 0,
      });
    }
  }
  
  return topK.toArray().sort((a, b) => b.score - a.score);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

class ImmutableTrieNode {
  readonly children: ReadonlyMap<string, ImmutableTrieNode>;
  readonly isTerminal: boolean;
  readonly word: string | null;
  readonly metadata: SuggestionMetadata | null;
  
  constructor(
    children: Map<string, ImmutableTrieNode>,
    isTerminal: boolean,
    word: string | null,
    metadata: SuggestionMetadata | null
  ) {
    this.children = children;
    this.isTerminal = isTerminal;
    this.word = word;
    this.metadata = metadata;
  }
  
  // Create new node with updated child
  withChild(char: string, child: ImmutableTrieNode): ImmutableTrieNode {
    const newChildren = new Map(this.children);
    newChildren.set(char, child);
    return new ImmutableTrieNode(
      newChildren,
      this.isTerminal,
      this.word,
      this.metadata
    );
  }
}
 
class COWTrie {
  private root: ImmutableTrieNode;
  
  insert(word: string, metadata: SuggestionMetadata): void {
    // Build path of new nodes from leaf to root
    const path: { char: string; node: ImmutableTrieNode }[] = [];
    let current = this.root;
    
    for (const char of word) {
      path.push({ char, node: current });
      current = current.children.get(char) ?? new ImmutableTrieNode(
        new Map(),
        false,
        null,
        null
      );
    }
    
    // Create terminal node
    let newNode = new ImmutableTrieNode(
      current.children,
      true,
      word,
      metadata
    );
    
    // Walk back up, creating new nodes along the path
    for (let i = path.length - 1; i >= 0; i--) {
      const { char, node } = path[i];
      newNode = node.withChild(char, newNode);
    }
    
    // Atomic swap of root reference
    this.root = newNode;
  }
}
 
// Benefits:
// 1. Zero contention on reads - readers see consistent snapshot
// 2. Readers never block writers, writers never block readers
// 3. Easy snapshots for backup/replication
//
// Costs:
// 1. Memory churn from creating new nodes
// 2. GC pressure in managed languages
// 3. Higher write latency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

const NUM_STRIPES = 64; // Power of 2 for fast modulo
 
class StripedTrie {
  private root: TrieNode;
  private locks: RWLock[];
  
  constructor() {
    this.root = new TrieNode();
    this.locks = Array.from(
      { length: NUM_STRIPES },
      () => new RWLock()
    );
  }
  
  private getLockIndex(prefix: string): number {
    // Hash first few characters to determine stripe
    const hashChars = prefix.slice(0, 3).padEnd(3, '\0');
    const hash = hashChars.charCodeAt(0) * 31 * 31 +
                 hashChars.charCodeAt(1) * 31 +
                 hashChars.charCodeAt(2);
    return hash & (NUM_STRIPES - 1); // Fast modulo for power of 2
  }
  
  async search(prefix: string): Promise<Suggestion[]> {
    const lockIndex = this.getLockIndex(prefix);
    await this.locks[lockIndex].acquireRead();
    
    try {
      return this.searchInternal(prefix);
    } finally {
      this.locks[lockIndex].releaseRead();
    }
  }
  
  async insert(word: string, metadata: SuggestionMetadata): Promise<void> {
    const lockIndex = this.getLockIndex(word);
    await this.locks[lockIndex].acquireWrite();
    
    try {
      this.insertInternal(word, metadata);
    } finally {
      this.locks[lockIndex].releaseWrite();
    }
  }
}
 
// Benefits:
// 1. Parallel writes to different prefixes
// 2. Lower memory overhead than COW
// 3. In-place updates
//
// Costs:
// 1. Risk of lock contention on popular prefixes
// 2. Readers must acquire locks (even if read-only)
// 3. Careful deadlock prevention needed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

interface SerializedTrie {
  // Header
  magic: number;            // 4 bytes: Format identifier
  version: number;          // 2 bytes: Format version
  nodeCount: number;        // 4 bytes: Total nodes
  stringTableOffset: number;// 4 bytes: Offset to string table
  
  // Node array (fixed-size entries for random access)
  nodes: SerializedNode[];
  
  // String table (variable-length strings)
  stringTable: Uint8Array;
}
 
interface SerializedNode {
  childBitmap: bigint;        // 16 bytes: Which children exist
  childrenOffset: number;     // 4 bytes: Offset in nodes array
  flags: number;              // 1 byte: isTerminal, etc.
  wordOffset: number;         // 4 bytes: Offset in string table
  score: number;              // 4 bytes: Suggestion score
}
 
// Serialization
function serializeTrie(root: TrieNode): ArrayBuffer {
  const nodes: SerializedNode[] = [];
  const strings: string[] = [];
  const stringOffsets = new Map<string, number>();
  
  // BFS traversal to assign node indices
  function traverse(node: TrieNode): number {
    const index = nodes.length;
    
    // Intern the word string
    let wordOffset = -1;
    if (node.word) {
      if (!stringOffsets.has(node.word)) {
        stringOffsets.set(node.word, strings.join('').length);
        strings.push(node.word + '\0');
      }
      wordOffset = stringOffsets.get(node.word)!;
    }
    
    // Create serialized node
    const serialized: SerializedNode = {
      childBitmap: computeBitmap(node.children),
      childrenOffset: -1, // Filled after processing children
      flags: node.isTerminal ? 1 : 0,
      wordOffset,
      score: node.metadata?.score ?? 0,
    };
    nodes.push(serialized);
    
    // Process children
    if (node.children.size > 0) {
      serialized.childrenOffset = nodes.length;
      for (const child of node.children.values()) {
        traverse(child);
      }
    }
    
    return index;
  }
  
  traverse(root);
  
  // Pack into ArrayBuffer
  return packToBuffer(nodes, strings);
}
 
// Deserialization: Memory-map the file for zero-copy access
function loadTrie(path: string): MemoryMappedTrie {
  const buffer = mmap(path);
  return new MemoryMappedTrie(buffer);
}
 
class MemoryMappedTrie {
  private buffer: ArrayBuffer;
  private nodeView: DataView;
  private stringTable: Uint8Array;
  
  search(prefix: string): Suggestion[] {
    // Navigate using offsets directly into buffer
    // No deserialization needed - read nodes in-place
  }
}