ccac

Aho-Corasick multi-pattern keyword matching library — header-only C implementation.

Language:中文 | English

Features

• O(n) search time — independent of dictionary size, linear in text length only
• Native UTF-8 — UCS-4 codec (via ccalg submodule), correct handling of CJK, emoji, and all Unicode planes
• Two backends — hash-map (ccac.h) or red-black tree (ccac1.h), ABI-compatible drop-ins
• Two search modes — record mode (collect all matches) and test mode (existence-only check)
• Incremental build — batch ccac_build plus dynamic ccac_add for live updates
• Custom delimiters — word lists accept any delimiter (newline, comma, pipe, etc.)
• Zero external dependencies — only the C standard library; required containers are bundled
• Cross-platform — C99+ / C11 / C++ / MSVC, -Wall -Wextra clean

Quick Start

git clone --recurse-submodules https://github.com/CandyMi/ccac.git

#include"ccac.h"intmain() {
ccac_tac;
ccac_init(&ac);
// Build from a delimited word listconstchar*dict="hello\nworld\ntest\nsensitive\n";
ccac_build(&ac, dict, strlen(dict), '\n');
// Search textconstchar*text="This text contains a sensitive word.";
ccac_match_tmatches[16];
intn=16;
ccac_match(&ac, text, strlen(text), matches, &n);
for (inti=0; i<n; i++) {
printf("match [%zu, %zu): %.*s\n",
matches[i].s, matches[i].e,
(int)(matches[i].e-matches[i].s),
text+matches[i].s);
}
ccac_destroy(&ac);
return0;
}

Build & Test

CMake (recommended)

# Configure + build
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j4
# Run all tests
ctest --test-dir build --output-on-failure
# One-shot: build + test
cmake --build build --target check -j4
ctest --test-dir build --output-on-failure
# Benchmark (needs PCRE2)
cmake --build build --target bench
# Install headers
cmake --install build --prefix /usr/local

All intermediate artifacts stay inside build/.

Manual

INC="-I. -I3rd/ccalg/include"# Codec tests
cc -std=c99 -Wall -Wextra $INC -o test_unicode tests/test_unicode.c && ./test_unicode
# Unit tests
cc -std=c99 -Wall -Wextra $INC -o test_ccac tests/test_ccac.c && ./test_ccac
# Robustness tests
cc -std=c99 -Wall -Wextra $INC -o test_ccac_robust tests/test_ccac_robust.c && ./test_ccac_robust
# Stress test (needs generated data)
python3 scripts/gen_words.py
python3 scripts/gen_stress_text.py words.zh.txt stress_text.txt 3
cc -std=c99 -O2 -Wall -Wextra $INC -o test_ccac_stress tests/test_ccac_stress.c
./test_ccac_stress words.zh.txt stress_text.txt stress_text.txt.pos

API

Function	Description
ccac_init(ac)	Initialize the automaton
ccac_destroy(ac)	Release all resources
ccac_build(ac, words, len, delim)	Bulk-build from a delimited word list
ccac_add(ac, word, len, &dup)	Add a single word dynamically
ccac_match(ac, text, len, matches, &nmatch)	Search text for dictionary words

ccac_match modes:

matches	Behavior
!= NULL	Record mode — writes up to *nmatch results into the buffer
== NULL	Test mode — returns on first match; *nmatch = 1 if found, 0 if not

Match result

Uses the standard [start, end) half-open interval:

• s = first byte of the matched word
• e = one past the last byte (so e - s = word length)

typedefstructccac_match {
size_ts; // start byte offset in the original UTF-8 textsize_te; // one-past-the-end byte offset (e - s = byte length)
} ccac_match_t;

// Example: matching "he" in "ushers"
// u s h e r s
// 0 1 2 3 4 5 6
// [2 4) s=2, e=4 → text[2..3] = "he" ✓
printf("%.*s\n", (int)(match.e - match.s), text + match.s);

ccac vs ccac1

	ccac.h	ccac1.h
Child container	cchashmap (hash map)	ccmap (red-black tree)
Lookup complexity	O(1) average	O(log n)
Memory	Bucket array (auto-resize)	Zero internal allocation
Best for	Large alphabets, raw speed	Memory-constrained, small node counts

Both headers expose identical types and function signatures — swap one #include to switch.

File Layout

ccac/
├── ccac.h # Variant A: hash-map backend
├── ccac1.h # Variant B: red-black tree backend (ABI-compatible)
├── 3rd/ccalg/ # [git submodule] containers + unicode codec
├── CMakeLists.txt # Build system
├── AGENTS.md # Canonical reference for AI coding agents
├── tests/ # Test suite
│ ├── test_ccac.c
│ ├── test_ccac_robust.c
│ ├── test_ccac_stress.c
│ └── test_unicode.c
├── bench/ # Benchmarks
│ └── bench_ccac.c
└── scripts/ # Data generation
├── gen_words.py
└── gen_stress_text.py

Performance

50,000 Chinese words / 3 MB text (Apple M1):

Metric	Value
Build speed	469,867 words/sec
Search throughput	63.2 MB/s
Recall	100%
vs naive (strstr) projected	2,357× faster
vs PCRE2 capped	1.6× faster

How It Works

Architecture

flowchart LR
A["UTF-8 Text"] --> B["ccunicode.h<br/>codec"]
B -->|"UCS-4"| C["AC Automaton"]
D["Dictionary"] --> E["Build Trie"]
E --> F["Failure Links<br/>(BFS)"]
F --> C
C --> G["Matches<br/>(offsets)"]

Loading

Trie & Failure Links

Example: dictionary {he, she, his, hers}

flowchart TD
R(("root"))
R -->|"h"| H(("h"))
R -->|"s"| S(("s"))
H -->|"e ●"| HE(("he"))
H -->|"i"| HI(("hi"))
HI -->|"s ●"| HIS(("his"))
S -->|"h"| SH(("sh"))
SH -->|"e ●"| SHE(("she"))
HE -->|"r"| HER(("her"))
HER -->|"s ●"| HERS(("hers"))
H -.->|"fail"| R
S -.->|"fail"| R
HE -.->|"fail"| R
SH -.->|"fail"| H
SHE -.->|"fail"| HE
HIS -.->|"fail"| S
HI -.->|"fail"| R
HER -.->|"fail"| R
HERS -.->|"fail"| S
style HE fill:#e44,stroke:#333,color:#fff
style SHE fill:#e44,stroke:#333,color:#fff
style HIS fill:#e44,stroke:#333,color:#fff
style HERS fill:#e44,stroke:#333,color:#fff

Loading

● = terminal node (end of a dictionary word). Dashed lines = failure links.

Search Example

Scanning "ushers" against the trie above:

sequenceDiagram
participant T as Text
participant AC as AC Automaton
participant M as Matches
T->>AC: pos=0 'u'
AC-->>AC: root → no 'u' → stay at root
T->>AC: pos=1 's' → root child 's'
T->>AC: pos=2 'h' → s→h (node sh)
T->>AC: pos=3 'e'
AC-->>AC: sh→'e' ✦ she (terminal!)
M-->>M: ✅ [1,4) = "she"
AC-->>AC: she→fail→he (terminal!)
M-->>M: ✅ [2,4) = "he"
T->>AC: pos=4 'r' → he→r (node her)
T->>AC: pos=5 's'
AC-->>AC: her→'s' ✦ hers (terminal!)
M-->>M: ✅ [2,6) = "hers"
AC-->>AC: hers→fail→s (non-terminal, stop)

Loading

Trie structure

Each node stores a single UCS-4 codepoint. Terminal nodes record the original UTF-8 byte length of the dictionary word, enabling O(1) match-start computation. Child lookup uses either a chained hash map or a red-black tree.

Failure links

Built in one BFS pass from the root: for each node v with child c on codepoint x, follow v->fail until a node with child x is found (or root), then set c->fail accordingly. Total time: O(number of nodes).

ccunicode.h codec (from ccalg)

UTF-8 ↔ UCS-4 implementation from the ccalg submodule (3rd/ccalg/include/ccunicode.h):

Function	Direction
ccunicode_to_codepoint(str, len, &val)	UTF-8 → UCS-4
ccunicode_from_codepoint(val, str, &len)	UCS-4 → UTF-8

Performance design: ASCII fast path, 256-byte first-byte classification table, unrolled continuation-byte processing via fall-through switch.

License

BSD 3-Clause © CandyMi