DARTS: Double-Array Trie Strings

Classical Trie vs DARTS

Trie (Tree-based)

struct TrieNode {
    char ch;
    int value;
    map children;  // or array[256]
};

// Lookup: "hello"
node = root
for ch in "hello":
    node = node->children[ch]
    if node == null: return NOT_FOUND
return node->value

Problem: Each node is ~24 bytes (pointer overhead). 100K words = 2.4MB.

DARTS (Array-based)

int base[100000];   // 400KB
int check[100000];  // 400KB
int value[100000];  // 400KB

// Lookup: "hello"
state = 0
for ch in "hello":
    idx = base[state] + ch
    if check[idx] != state: return NOT_FOUND
    state = idx
return value[state]

Benefit: Memory drops to ~1.2MB. Dense arrays = cache-friendly. Lookup is still O(n).

DARTS Construction

Offline Build Phase

DARTS is constructed offline once, then used for read-only lookups:

1. Build a classical trie from dictionary (words.txt)
2. Assign base/check values to minimize array size
3. Serialize to binary format
4. mmap into process at startup

Base/Check Array Semantics

For each state s and character c:

idx = base[s] + c
if check[idx] == s:
    next_state = idx
    // transition valid
else:
    // no transition, string not in dict

base[s]: Offset in the arrays for this state's transitions.

check[idx]: Validation that idx actually belongs to state s (prevents false positives).

Example Construction

Dictionary: ["hi", "his", "has"]

Trie:
       root
      /  |
     h   ...
    / 
   i   s
  /   / 
end  end

Step 1: Assign base/check
state 0 (root): base[0] = 0
  transition on 'h' -> state 1, idx = 0 + 'h' = 104
  base[0] = 0, so idx = 0 + 104 = 104
  check[104] = 0

state 1 (after 'h'): base[1] = 200
  transition on 'i' -> state 2, idx = 200 + 'i' = 305
  check[305] = 1
  transition on 'a' -> state 3, idx = 200 + 'a' = 297
  check[297] = 1

Step 2: Serialize
base = [0, 200, ...]
check = [?, ?, ..., 0, ..., 1, ..., 1, ...]
value = [?, ?, ..., WORD_ID("hi"), ..., WORD_ID("his"), ..., WORD_ID("has")]

Lookup Algorithm

Pseudo-code

function lookup(trie, word):
    state = 0
    for i = 0 to len(word) - 1:
        ch = word[i]
        idx = trie.base[state] + ch
        
        if idx >= trie.size or trie.check[idx] != state:
            return NOT_FOUND
        
        if trie.value[idx] != NO_VALUE and i == len(word) - 1:
            return trie.value[idx]  // full word match at end
        
        state = idx
    
    return NOT_FOUND

Step-by-step Example

Looking up "his" in dictionary ["hi", "his", "has"]:

state = 0
ch = 'h' (104)
idx = base[0] + 104 = 0 + 104 = 104
check[104] == 0? YES
state = 104

ch = 'i' (105)
idx = base[104] + 105 = 200 + 105 = 305
check[305] == 104? YES
state = 305

ch = 's' (115)
idx = base[305] + 115 = 400 + 115 = 515
check[515] == 305? YES
state = 515
value[515] != NO_VALUE and i == 2? YES
return WORD_ID("his")

Space Optimization

Collision Resolution

Two states might want the same base offset. DARTS uses a clever packing algorithm to minimize collisions:

// Greedy: assign smallest available base
for state in states:
    for candidate_base in 0 to MAX:
        if canAssignBase(state, candidate_base):
            base[state] = candidate_base
            break

Suffix Compression

If two words share a suffix (e.g., "run" and "sunrun"), share their trie nodes:

Dictionary: ["running", "run", "sunrun", "sun"]

Trie without suffix compression:
     root
    / |    r  s  ...
  / \ /  u   u   u
 |   |   |
 n   n   n
...

Trie with suffix compression:
     root
    / |    r  s  ...
    \ | /
     u (shared node)
     |
     n (shared node)
     |
     (final states for "run", "sun", "sunrun")

Performance Characteristics

Time Complexity

• Lookup: O(m) where m = word length (~20-30 characters for Chinese)
• Per-character cost: ~20 nanoseconds (one array access + cache hit)
• For 1000-token tokenization: 1000 * 20 * 100 chars = 2 million operations = ~2ms

Space Complexity

• Dictionary size: 100K words typical for Chinese
• base array: 100K * 4 bytes = 400KB
• check array: 100K * 4 bytes = 400KB
• value array: 100K * 4 bytes = 400KB
• Total: ~1.2MB (vs 2.4MB for tree-based trie)

Cache Efficiency

Modern CPUs have L2 cache = 256KB-1MB. DARTS dictionary fits entirely, so lookups rarely miss cache. Trie-based approaches scatter pointer chasing across memory, causing cache misses.

Comparison: DARTS vs HashMap vs B-Tree

Winner for tokenization: DARTS. Worst-case O(m) guarantee, excellent cache locality, small memory footprint.

Real-World Integration

Tokenization Pipeline

Input: "今天天气很好"

Step 1: Loop over each position (greedy longest-match):
  pos=0: Check "今", "今天", "今天天", ... -> matches "今天" (DARTS lookup: 2 steps)
  pos=2: Check "天", "天气", "天气很", ... -> matches "天气" (2 steps)
  pos=4: Check "很", "很好" -> matches "很好" (2 steps)

Output: ["今天", "天气", "很好"]

Total DARTS lookups: ~3 successful
Each lookup: ~2 characters * 20ns = 40ns
Total time: 120ns per token (negligible in ~100ms search operation)

Implementation Notes

Value Array Encoding

The value array stores word IDs, not strings. An external ID->string map provides the actual words:

word_to_id["今天"] = 42
id_to_word[42] = "今天"

DARTS lookup returns 42
Service looks up id_to_word[42] to get actual string

Memory-Mapped Binary Format

At startup, mmap the DARTS binary file into memory instantly (no parsing overhead):

File format: [magic(4)] [version(2)] [base(4*n)] [check(4*n)] [value(4*n)]

mmap("darts_dict.bin", read_only) -> get base[], check[], value[] pointers
Cost: O(1), instant access

Building DARTS from a Dictionary

Input Preparation

Start with a dictionary file (one word per line, optionally with frequency):

今天,100
天气,90
天空,50
很,10
好,100
开心,70
...

Build Process

Step 1: Sort by prefix (lexicographically)
好
开心
天,100
天气,90
天空,50
很,10
今天,100

Step 2: Build trie
       root
      / |      好 开 天...
        |  /         心 气 空...

Step 3: Assign base/check values (minimize array size)
- Reserve space for transitions
- Reuse unused array slots

Step 4: Serialize
[base array] [check array] [value array]

Tools

Use existing DARTS implementations:

• darts-clone: Fast C++ builder, produces binary format
• darts-python: Python bindings for querying existing DARTS
• fugashi: Japanese tokenizer using DARTS (example integration)

Advanced Optimization: Suffix Compression

Many words share suffixes. A compressed trie merges them:

Words: "running", "run", "sunrun", "sun"

Standard trie (8 nodes):
         r
        /        u   ...
       |
       n
       / \
      n   ...
      |
      i
      |
      n
      |
      g

Suffix-compressed (5 nodes):
      r
     /     u   ...
    |
    n (shared with "sun" via merging)
    |
    {"ing", ""}  (both words end here)

RAGFlow's DARTS dictionary uses suffix compression to save ~30% memory.

Real-World Example: Chinese Tokenization

Scenario

Tokenize "今天天气很好很开心"

Greedy Longest-Match Algorithm

Text: "今天天气很好很开心"
Pos:   0

Pos=0: Try "今", "今天", "今天天"
  "今" -> not in dict (skip)
  "今天" -> FOUND in dict (base[0] + '今天') -> value=ID1
  "今天天" -> not in dict
  Emit token "今天" (ID1), move to pos=2

Pos=2: Try "天", "天气", "天气很"
  "天" -> not in dict
  "天气" -> FOUND in dict (value=ID2)
  "天气很" -> not in dict
  Emit token "天气" (ID2), move to pos=4

Pos=4: Try "很", "很好", "很好很"
  "很" -> not in dict
  "很好" -> FOUND in dict (value=ID3)
  "很好很" -> not in dict
  Emit token "很好" (ID3), move to pos=6

Pos=6: Try "很", "很开", "很开心"
  "很" -> not in dict
  "很开" -> not in dict
  "很开心" -> FOUND in dict (value=ID4)
  Emit token "很开心" (ID4), move to pos=9

Pos=9: End of string

Result: [今天, 天气, 很好, 很开心]
Total DARTS lookups: 3 successful + some misses = ~10 lookups
Time: 10 * 20ns = 200ns (negligible)

Handling Unknown Words

When DARTS lookup fails (word not in dict), two strategies:

Strategy 1: Character-by-Character Fallback

If no word match, emit single character
This keeps the text flowing but loses semantic boundaries

Strategy 2: Morphological Analysis

If "今天天" not found, try:
- "今天" (found) -> emit, restart from "天"
- Backtracking to longest prefix

Strategy 3: Hybrid (RAGFlow's Approach)

Combine DARTS with a fallback statistical model. DARTS handles 99% of known words; for unknowns, use a smaller fallback classifier.

Testing & Validation

Unit Tests

test_cases = [
    ("今天天气很好", ["今天", "天气", "很好"]),
    ("hello world", ["hello", "world"]),  // English
    ("你好", ["你好"]),  // Chinese
    ("café", ["cafe"]),  // Unicode
]

for text, expected in test_cases:
    result = darts.tokenize(text)
    assert result == expected, f"Failed: {text}"

Performance Testing

import time

text = "今天天气很好" * 1000  // 1000x repetition
start = time.now()
tokens = darts.tokenize(text)
elapsed = time.since(start)

print(f"Tokenized {len(text)} chars in {elapsed}ms")
// Expected: ~2ms for 10,000 chars = 200ns per char (matches theory)

Integration Checklist

• Load DARTS binary at startup (mmap, O(1))
• Test with diverse languages (CJK, Latin, emoji)
• Measure latency tail (p99) to catch worst-case
• Cache tokenization results per query string
• Version the dictionary file (update notes required)
• Have fallback tokenizer if DARTS unavailable

Further Reading

• Tokenizer" href="../../index.html">Internal Module Overview
• C++ Text Analysis