darts

DARTS Trie

Project: DARTS — Double-ARray Trie System Repository: https://github.com/trevor‑m/darts‑clone

Overview

DARTS Trie is a static double‑array trie implementation in C++, designed for efficient storage and fast lookup of English string dictionaries. It uses a double‑array structure to represent the trie compactly, enabling high performance in exact match and common prefix search without dynamic updates.

The double‑array design separates base and check arrays, providing memory locality and fast transition operations during search. DARTS is suitable for large key sets and read‑only workloads.

---

Key Features

• Static and compact: space‑efficient representation for large English vocabularies.
• Fast lookup: supports exact match and prefix search at high throughput.
• Memory locality: double‑array structure improves cache behavior.
• Offline construction: build once, deploy with minimal overhead.

---

Typical Use Cases

• English keyword lookup for search indexing
• Autocomplete / prefix matching in query engines
• Static dictionary access with low memory footprint
• Text classification using preassembled token sets

---

Not Suitable For

• Online or dynamic updates
• High‑concurrency write‑heavy workloads
• Non‑English or Unicode‑heavy applications

---

Industrial Fit

Requirement	DARTS Support
mmap‑able & serializable dictionary	✔️
Fast prefix & exact search	✔️
Dynamic update	❌
Attaching payload (bitmap / counts)	❌

Conclusion: DARTS Trie is suited for static English dictionary lookup and prefix search in production systems where build‑once, read‑many access is required.

---

C++ Example

Build Clone (Typical)

git clone https://github.com/trevor-m/darts-clone
cd darts-clone
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build

Construct a Double‑Array Trie

#include "darts.h"
#include <iostream>
#include <vector>

int main() {
    std::vector<std::string> keys = {
        "apple",
        "application",
        "banana",
        "band"
    };

    Darts::DoubleArray trie;
    trie.build(keys);

    trie.save("darts.dict");

    return 0;
}

Load and Query a Trie

#include "darts.h"
#include <iostream>

int main() {
    Darts::DoubleArray trie;
    trie.open("darts.dict");

    std::string query = "app";
    size_t result = trie.exactMatchSearch(query.c_str());
    if (result != static_cast<size_t>(-1)) {
        std::cout << "Exact match found at index: " << result << "\n";
    }

    // Common prefix search
    trie.commonPrefixSearch(query.c_str(),
        [&](size_t id, const char* key) {
            std::cout << "Prefix found: " << key << "\n";
        });

    return 0;
}