PII Detection Algorithms Compared: Regex, KMP, Rabin-Karp, Aho-Corasick

Dean Jain

Senior Staff Software Engineer · Enterprise AI, Data & Cloud Architect

February 17, 2018 · 6 min read

PrivacyAlgorithmsSecurityPII

---
config:
  theme: dark
  fontSize: 17
  themeVariables:
    fontFamily: "Comic Sans MS, Comic Neue, Chalkboard SE, cursive"
---
flowchart TD
    PII["🔎 PII detection"]:::gov
    PII --> RX["🧩 Regex<br/>structured formats"]:::obs
    PII --> CL["🔤 KMP / Rabin-Karp<br/>classic string search"]:::gate
    PII --> AC["🌲 Aho-Corasick<br/>multi-pattern, one pass"]:::server
    PII --> ML["🧠 ML / NLP<br/>context-aware"]:::good
    classDef gov fill:#E0D6F5,stroke:#9B7EDE,stroke-width:2px,color:#0F172A
    classDef obs fill:#AED6F1,stroke:#2E86C1,stroke-width:2px,color:#0F172A
    classDef gate fill:#D7C3F2,stroke:#8E5BD0,stroke-width:2px,color:#0F172A
    classDef server fill:#A8E6D0,stroke:#2FA37C,stroke-width:2px,color:#0F172A
    classDef good fill:#BFEFC8,stroke:#3FA34D,stroke-width:2px,color:#0F172A

Figure 1: Four families of PII-detection algorithm, each trading off speed, multi-pattern support, and context-awareness.

As privacy regulation tightens and AI pipelines ingest everything, finding the PII in your data has gone from nice-to-have to mandatory. And it’s fundamentally a text pattern-matching problem.

The catch is that no single algorithm wins. Each trades precision, recall, performance and context-awareness differently. Regex nails structured formats but is blind to context. Aho-Corasick scans thousands of patterns in one pass but doesn’t understand meaning. ML reads context but costs compute. Knowing the trade-offs, and that the real answer is a hybrid, is how you build PII detection that’s both accurate and fast enough to run at scale.

TL;DR

PII detection is pattern matching across structured, semi-structured, and unstructured text and the algorithm choice is a real trade-off.
Regex is great for well-structured PII like emails and phone numbers. It misses odd formats and has no context awareness.
KMP & Rabin-Karp classic string search. KMP is linear single-pattern; Rabin-Karp uses rolling hashes and suits multiple patterns.
Aho-Corasick is the multi-pattern champion. Build one automaton from all patterns and match them all in a single linear pass, O(n + m + z).
ML/NLP (NER) the only approach with context awareness, for PII that breaks formatting rules at higher compute cost.
The winner is hybrid: regex + Aho-Corasick for the fast structured pass, ML/NLP for the ambiguous, context-dependent cases.

1. The problem, and the regex baseline

PII is any data that could identify a person, whether direct like a name or SSN, or indirect through combinable clues. It hides everywhere: databases, JSON, XML, documents, emails, free-floating text. A good detector must balance precision and recall against performance while handling diverse formats and context.

Regex is the natural starting point and the most common approach. You define patterns matching specific PII formats, so an email is “@ between words, then a dot and more letters”, and then you scan.

Its strengths are real: highly customizable, simple, low overhead, and easy to update by anyone who can read a pattern. On text that follows a predictable shape it does the overwhelming majority of the work on its own, which is why almost every pipeline starts here.

But the limits are exactly where PII gets dangerous. Regex is blind to context. It matches form, not meaning, so it misses PII in unexpected formats. A lowercase name mid-sentence isn’t a recognizable pattern. And complex patterns become brittle, hard-to-maintain monsters. Regex is the right tool for structured PII: emails, phone numbers, SSNs with known formats, anything whose shape is fixed and predictable.

It is the wrong tool for everything else, and that gap between what has a fixed shape and what only has a meaning is exactly what drives you to the other algorithms.

2. Classic string search: KMP and Rabin-Karp

When you’re searching for known literal PII strings (a specific SSN, a phone number), classic string-matching algorithms beat naïve scanning:

Knuth-Morris-Pratt (KMP) precomputes a table of partial matches so that on a mismatch it skips characters it already knows match, avoiding redundant comparisons. Result: linear time, O(n + k) (text length + pattern length), O(k) space. Best for single-pattern search in large texts.
Rabin-Karp uses hashing. Compute a hash of the pattern and a rolling hash of each text window, then compare character by character only when the hashes match. It “filters the characters that don’t match” before comparing. Average O(n + m), worst case O(nm), O(1) extra space. Its hashing approach extends naturally to multiple patterns making it a stepping stone to the real multi-pattern champion.

Neither was built for PII specifically, but both are solid for known, fixed-format identifiers. Their shared limitation: like regex, zero context awareness, and KMP handles only one pattern at a time.

3. Aho-Corasick: many patterns, one pass

Here’s the algorithm worth knowing for PII at scale. You rarely search for one pattern you search for hundreds (every PII keyword, every known format). Running KMP once per pattern is wasteful. Aho-Corasick matches all patterns in a single linear pass:

---
config:
  theme: dark
  fontSize: 17
  themeVariables:
    fontFamily: "Comic Sans MS, Comic Neue, Chalkboard SE, cursive"
---
flowchart LR
    PAT["📋 All patterns<br/>(ssn, passport, …)"]:::obs --> TRIE["🌲 Trie<br/>(quick lookup)"]:::gate
    TRIE --> FL["🔗 Failure links<br/>(longest matching prefix)"]:::server
    FL --> OUT["📤 Output links<br/>(detect all matches in one pass)"]:::good
    classDef obs fill:#AED6F1,stroke:#2E86C1,stroke-width:2px,color:#0F172A
    classDef gate fill:#D7C3F2,stroke:#8E5BD0,stroke-width:2px,color:#0F172A
    classDef server fill:#A8E6D0,stroke:#2FA37C,stroke-width:2px,color:#0F172A
    classDef good fill:#BFEFC8,stroke:#3FA34D,stroke-width:2px,color:#0F172A

Figure 2: Aho-Corasick. Build a trie of all patterns, add failure links and output links, then match every pattern in one linear scan.

It builds a finite-state machine, a trie, from all patterns. On a mismatch, a failure link jumps to the state for the longest proper suffix of the text matched so far that is also a prefix of some pattern. Output links report every pattern that matches at a given position. The payoff is its complexity: O(n + m + z), which is text length plus total pattern length plus number of matches. The cost barely grows as you add more patterns. The same algorithm powers spam filters, intrusion-detection systems like Snort and Suricata, and antivirus signature scanning. ClamAV’s matcher is literally matcher-ac.c. All for the same reason.

Scan once, and match thousands of patterns in that single pass.

For detecting many PII keyword and format types across large datasets, it’s the efficient backbone.

4. When format isn’t enough: ML/NLP

Every algorithm so far matches form. But a lot of PII is context-dependent. “Paris” is a city or a person, and “Jordan” is a country or a name, and no pattern in the world can tell them apart. That’s where ML/NLP comes in, the only family with real context awareness:

Named Entity Recognition (NER) identifies entities (names, organizations, locations) by their role in the sentence, not their shape.
NLP matchers and deep-learning models (PyTorch/TensorFlow) detect sophisticated, context-dependent PII that breaks formatting rules.

The cost is compute and complexity, and accuracy depends on training which is why you don’t run ML on everything. You run it where pattern matching fails.

5. The answer is hybrid

No single algorithm wins; the best systems layer them in a tiered pipeline that spends cheap compute first and expensive compute only where needed:

---
config:
  theme: dark
  fontSize: 17
  themeVariables:
    fontFamily: "Comic Sans MS, Comic Neue, Chalkboard SE, cursive"
---
flowchart LR
    T1["⚡ Pass 1: fast match<br/>regex + Aho-Corasick"]:::server --> T2["🧠 Pass 2: ML/NLP<br/>on ambiguous cases"]:::gate
    T2 --> V["✅ Validate<br/>reduce false positives"]:::obs
    V --> C["🏷️ Classify<br/>for handling"]:::good
    classDef server fill:#A8E6D0,stroke:#2FA37C,stroke-width:2px,color:#0F172A
    classDef gate fill:#D7C3F2,stroke:#8E5BD0,stroke-width:2px,color:#0F172A
    classDef obs fill:#AED6F1,stroke:#2E86C1,stroke-width:2px,color:#0F172A
    classDef good fill:#BFEFC8,stroke:#3FA34D,stroke-width:2px,color:#0F172A

Figure 3: The tiered hybrid. Fast pattern matching catches the clear PII; ML/NLP handles the ambiguous; then validate and classify.

Algorithm	Time	Multi-pattern	Context
Regex	Varies (can blow up)	Limited	None
KMP	`O(n + k)`	No	None
Rabin-Karp	Avg `O(n + m)`, worst `O(nm)`	Yes (limited)	None
Aho-Corasick	`O(n + m + z)`	Excellent	None
ML/NLP	Varies (high)	Yes	High

Figure 4: The trade-off at a glance. Speed and multi-pattern scale on the left, context-awareness only on the right.

A production pipeline runs in stages. The first pass is regex plus Aho-Corasick, catching clear structured PII fast, and the second pass is ML and NLP on the ambiguous cases. Then validate matches to cut false positives, and classify them for handling: mask, encrypt or drop. Choose the entry point by your constraints. Data volume favours linear algorithms, PII diversity favours Aho-Corasick, and accuracy-critical work needs ML. Real-time work needs the fast pass up front.

“Detect PII” sounds like one task with one tool. So teams either over-rely on brittle regex and miss context-dependent PII, or reach straight for expensive ML and can’t run it at scale. The mature design matches algorithm to job. Fast pattern matching for the structured majority, ML for the contextual rest, validation to keep precision high.

Get that layering right and you protect sensitive data thoroughly, while keeping the pipeline fast enough to run on everything. With privacy regulation and AI data flows, you increasingly must.