1. Engineering Specifications for a Streaming Scanner
To make our Aho-Corasick engine suitable for intrusion detection, log redaction, or DLP (Data Loss Prevention) pipelines, we enforce four architectural invariants:
- Zero-Allocation Streaming State (
ScannerCursor): The compiledAhoCorasickAutomatonis immutable and thread-safe (const), so 64 worker threads can share a single compiled dictionary while each stream maintains a tiny 16-byteScannerCursor { int32_t state; uint64_t bytes_seen; }. - Constant-Size Node Layout via Intrusive Pattern Lists: Storing a
std::vector<int>inside every Trie node wastes 24 bytes of heap-vector header per state even when 95% of states are non-terminal. Instead, each node stores a singleint32_t first_pat = -1, and we storenext_pat_at_same_node[pat_id]in a flat array of size $K$. - Exact Start & End Offset Calculation: Because matches can span across chunk boundaries (e.g., $\texttt{" Drop"}$ at the end of Chunk 1 and $\texttt{"Table"}$ at the start of Chunk 2), the cursor tracks
bytes_seen, and when patternpidof length $L_{\text{pid}}$ matches at global byte indexpos, its exact start offset ispos + 1 - L_pid. - Compressed Output Links (
exit_link): During BFS, we setexit_link[u]tofail[u]ifnodes[fail[u]].first_pat != -1, and toexit_link[fail[u]]otherwise.
| Component / Operation | Time Complexity | Space Overhead | Thread-Safety / Streaming |
|---|---|---|---|
add_pattern(pat) |
$O(|P_i|)$ | $1$ int per pattern in linked list | Builder phase (mutable) |
freeze() (BFS DFA Build) |
$O(\text{states} \cdot |\Sigma|)$ | Zero heap pointers per node | Produces immutable DFA |
scan_chunk(cursor, bytes, cb) |
$O(|\text{chunk}| + Z_{\text{chunk}})$ | $O(1)$ ($16$-byte cursor) | Lock-free across threads & chunks |
Let $T = C_1 \mathbin{\|} C_2 \mathbin{\|} \dots \mathbin{\|} C_m$ be a stream partitioned into arbitrary byte chunks. Because $u_{i+1} = \text{go}[u_i][T[i]]$ depends only on $u_i$ and $T[i]$, carrying cursor.state and cursor.bytes_seen from the end of $C_k$ into the start of $C_{k+1}$ visits the exact same sequence of states $u_1, u_2, \dots, u_N$ and emits the exact same set of matches $(i_{\text{start}}, i_{\text{end}}, \text{pid})$ as scanning the concatenated string $T$ in one buffer.
A std::vector<int> inside every Node adds 24 bytes of struct overhead plus a separate heap allocation for every terminal state, scattering terminal pattern lists across memory pages. Storing int32_t first_pat in Node (4 bytes) and int32_t next_pat[K] in a single flat array of length $K$ eliminates all per-node heap allocations and cuts terminal match traversal to sequential array reads.
2. Architecture Diagram: Immutable DFA + Streaming Cursor
Scan text T = "ushers" in a single pass against dictionary {"he", "she", "his", "hers"} using BFS failure links and output links, or trace Manacher’s O(N) palindrome radius mirroring & Eertree dual roots.
Invariant & State
3. Complete Build Implementation: Streaming Aho-Corasick Engine
#include <array>
#include <cstdint>
#include <queue>
#include <string_view>
#include <vector>
struct MatchEvent {
uint64_t start_offset; // Inclusive global byte offset
uint64_t end_offset; // Exclusive global byte offset
int32_t pattern_id;
};
struct ScannerCursor {
int32_t state = 0;
uint64_t bytes_seen = 0;
};
class StreamingAhoCorasick {
public:
struct Node {
std::array<int32_t, 256> go{};
int32_t fail = 0;
int32_t exit_link = 0;
int32_t first_pat = -1; // Head of intrusive linked list of pattern IDs
};
StreamingAhoCorasick() { nodes_.emplace_back(); }
int32_t add_pattern(std::string_view pat) {
int32_t pid = static_cast<int32_t>(pat_len_.size());
pat_len_.push_back(static_cast<uint32_t>(pat.size()));
int32_t u = 0;
for (unsigned char c : pat) {
if (nodes_[u].go[c] == 0) {
nodes_[u].go[c] = static_cast<int32_t>(nodes_.size());
nodes_.emplace_back();
}
u = nodes_[u].go[c];
}
// Prepend pid to node u's intrusive pattern list
next_pat_.push_back(nodes_[u].first_pat);
nodes_[u].first_pat = pid;
return pid;
}
void freeze() {
std::queue<int32_t> q;
for (int c = 0; c < 256; ++c) {
int32_t v = nodes_[0].go[c];
if (v != 0) {
nodes_[v].fail = 0;
q.push(v);
}
}
while (!q.empty()) {
int32_t u = q.front();
q.pop();
int32_t f = nodes_[u].fail;
nodes_[u].exit_link = (nodes_[f].first_pat != -1) ? f : nodes_[f].exit_link;
for (int c = 0; c < 256; ++c) {
int32_t v = nodes_[u].go[c];
if (v != 0) {
nodes_[v].fail = nodes_[f].go[c];
q.push(v);
} else {
nodes_[u].go[c] = nodes_[f].go[c];
}
}
}
frozen_ = true;
}
template <typename Callback>
void scan_chunk(ScannerCursor& cursor, std::string_view chunk, Callback&& on_match) const {
int32_t u = cursor.state;
uint64_t pos = cursor.bytes_seen;
for (unsigned char c : chunk) {
u = nodes_[u].go[c];
++pos; // pos is now the exclusive end offset of any match ending here
int32_t term = (nodes_[u].first_pat != -1) ? u : nodes_[u].exit_link;
while (term != 0) {
for (int32_t pid = nodes_[term].first_pat; pid != -1; pid = next_pat_[pid]) {
on_match(MatchEvent{pos - pat_len_[pid], pos, pid});
}
term = nodes_[term].exit_link;
}
}
cursor.state = u;
cursor.bytes_seen = pos;
}
private:
std::vector<Node> nodes_;
std::vector<uint32_t> pat_len_;
std::vector<int32_t> next_pat_;
bool frozen_ = false;
};In C and C++, char is signed on x86_64 and ARM Linux/macOS targets ($-128..127$). Indexing nodes_[u].go[ch] directly with a signed char on UTF-8 or binary payloads causes out-of-bounds negative array indexing whenever a byte has its high bit set ($ge ext{0x80}$)! Always cast to unsigned char or uint8_t before indexing the transition table, and reject or handle empty patterns ($|P_i| = 0$) before insertion so root state $0$ never becomes a terminal state (since our output loop terminates on term != 0).