skip to content

How can one automaton match hundreds of patterns against a record in a single pass over the input?

level: seniorimportance: nice to knowfreq 30%

answer

  1. one machine, not one scan each
  2. alternation over the whole rule set
  3. tag every accepting state
  4. cost follows combined pattern size
  5. one step per character, all rules live

basics

~20 s

Combine the patterns into one machine by alternation and tag every accepting state with the pattern it came from. One scan then advances the combined state set per character and reports each pattern whose accepting state is reached.

solid answer

~40 s

The naive filter loops over patterns and scans the record once per pattern, so cost grows with the pattern count. Instead, compile each pattern, join them under one start state as a single alternation, and label each pattern's accepting states with its identifier. Running the combined machine costs one step per character, and the tag on any accepting state in the live set says which pattern fired. Total cost then follows the **combined pattern size** rather than the number of scans, and with a demand-built transition cache it approaches one lookup per character. This works only on the one-pass architecture: a backtracking engine given the same alternation still tries the branches in turn at each starting position.

code

pseudocode · 13 lines
pseudocode
combined = new machine with a fresh start state
for each (id, pattern) in pattern_set:
    m = compile(pattern)
    combined.start.add_epsilon_edge_to(m.start)   // union
    for each a in m.accepting_states:
        tag(a, id)                                // remember whose accept this is

current = epsilon_closure({ combined.start })
for each c in record:
    current = step(current, c)
    for each s in current:
        if s is accepting:
            report(tag(s), position_of(c))

go deeper

for a junior

Know that applying many patterns to the same text does not have to mean reading that text many times; the patterns can be combined before the scan begins.

for a middle

Explain the union construction: one start state entering every compiled pattern, accepting states labelled with their pattern, and one live-set step per input character.

for a senior

Weigh the operational cost - rebuild granularity, lost per-rule attribution, larger state sets pressuring the transition cache - and know when splitting the set into several machines is the better shape.

for a principal

Decide the rule-set contract: how rules are admitted, how often the machine may be rebuilt, and what a rule author is allowed to write so that the union stays possible.

## The loop you start with The obvious implementation of a filter with a large rule set is a loop: for each pattern, scan the record. Its cost is the sum over patterns of record length times that pattern's size, so **doubling the rule set doubles the work**, and every scan re-reads the same bytes. For a filter on an ingest path where every record must pass every rule, that multiplication is the dominant cost long before any individual pattern is interesting. ## Union into one machine The one-pass architecture allows a different arrangement, because alternation is just another operator: 1. **Compile each pattern** to its own machine. 2. **Join them under a single start state**, so the combined machine's start can enter any pattern - an alternation over the entire rule set. 3. **Tag the accepting states** of each sub-machine with that pattern's identifier, so an accept still tells you which rule fired. 4. **Determinise on demand** as the scan proceeds, so repeated situations cost a lookup. The scan then advances the live set once per character. Whenever the live set contains a tagged accepting state, the corresponding pattern has matched, and the tag names it. ## What the single pass buys - **One traversal of the record**, so the input is read once and stays cache-resident while it is examined. - **Cost driven by combined pattern size, not by pattern count.** Adding a rule enlarges the machine; it does not add a pass. - **All matching rules found together**, since several accepting states can be live in the same set at the same character. - **Shared prefixes collapse.** Rules beginning alike share states in the combined machine, so the rule set is often much smaller than the sum of its parts. ## What it costs you The union is not free, and an interviewer will want the other side: - **Bigger live sets and more distinct ones**, which raises pressure on any transition cache the engine keeps - the failure mode is a throughput drop with correct output. - **Coarser build granularity**: the machine is one compilation unit, so adding or editing a single rule rebuilds it. - **No per-rule attribution**: you can no longer time the rules individually, because there is only one scan. You measure rules by removing them. - **Feature-restricted membership**: any rule needing something the one-pass engine cannot run has to stay outside the union on its own path. | | Loop over patterns | One combined machine | |---|---|---| | Passes over the record | One per pattern | One in total | | Cost driver | Pattern count times record length | Combined pattern size times record length | | Which rules matched | Naturally, one scan at a time | From the tag on each accepting state | | Adding a rule | Isolated | Rebuilds the machine | ## Practical shaping Two refinements come up in real filters. First, the union does not have to be a single machine: splitting a very large rule set into a handful of machines trades one extra pass for much smaller state sets, which can be a net win when a transition cache is thrashing. Second, a cheap literal prefilter in front of the machine can skip records that cannot possibly match any rule, so the full scan runs only where it might pay off - though every such prefilter must be **conservative**, never discarding a record that some rule would have matched. The architectural point underneath all of this is that a one-pass engine composes: because the machine represents every alternative simultaneously, adding alternatives is an operation on the machine rather than a repetition of the work. A backtracking engine does not compose this way. Handed the same giant alternation, it tries branch after branch at each starting position, so the pattern count keeps showing up in the runtime - which is why multi-rule filters and the one-pass architecture tend to appear together.

  • What does the combined machine cost that the separate scans did not?
    State-set size and cache pressure: the union is as large as all the rules together, so more distinct state sets are reachable and a demand-built transition table holds more of them. It also becomes one compilation unit - editing a single rule rebuilds the machine - and per-rule cost attribution disappears with the separate scans.
  • Can a backtracking engine get the same single-pass behaviour from one big alternation?
    Not in general. It commits to one branch at a time, so at each starting position it works through the branches in order and the rule count reappears in the runtime. And any branch using a feature only backtracking supports keeps the whole expression off the one-pass path, so the union stops being available at all.

saying these in an interview costs you the question

  • Thinks matching n rules must always cost n scans of the record.
  • Believes the combined machine is the size of its largest pattern.
  • Assumes a union machine cannot say which pattern matched.
  • Expects per-rule latency numbers from one combined scan.
  • Adds a backreference rule to the union and expects it to run.