Matching patterns over ranked trees

In this article I describe a top down approach to matching ranked ordered trees in which each pattern is reduced to a collection of root to leaf obligations recognized by a shared Aho-Corasick automaton.

1. Pattern language

Let \(\Sigma\) be a finite ranked alphabet and let every symbol carry a fixed arity, which makes a \(\Sigma\)-term an ordered tree whose children are determined by the rank of its root symbol. A pattern extends that alphabet with a wildcard \(\_\) which matches an arbitrary subject subtree, and separate wildcard occurrences impose no equality constraint on the subtrees they consume. A pattern matches at a subject node when replacing each wildcard with the corresponding subject subtree makes the pattern identical to the complete subtree rooted at that node. The matcher therefore reports roots rather than the leaves at which enough evidence happened to accumulate.

Consider the pattern a(a(b, _), c) against f(a(a(b, a(a(b, d), c)), c), z), where the outer occurrence of a and the nested occurrence inside its wildcard position are both match roots. The green region satisfies the pattern while treating the amber subtree as the first wildcard substitution, and the amber region independently satisfies the same pattern with d as its wildcard substitution. Child positions remain significant throughout the construction because a(b, c) and a(c, b) denote different ordered trees even when they contain the same multiset of labels. Arity is carried with each label so an unmentioned child can't be accepted accidentally. The pattern and both matching regions are shown below:

2. Path language

Each root to leaf path becomes a token string whose alphabet contains ranked labels and child indices, which preserves both the symbols encountered along the path and the branch selected at every internal node. Wildcards contribute no label token because they terminate the structural obligation at that position, although the child index leading into a wildcard remains part of the path. The example pattern produces three strings, with a/2 denoting a binary symbol and b/0 or c/0 denoting nullary symbols:

a/2  1  a/2  1  b/0
a/2  1  a/2  2
a/2  2  c/0

The shared trie for those obligations is:

Materializing every path independently can duplicate a common prefix once for every leaf beneath it, which gives a quadratic total path length for suitably shaped patterns despite the pattern itself remaining linear in size. A direct trie construction avoids that duplication by sharing the prefix represented by each pattern node and splitting label transitions from child index transitions. The resulting trie contains one state for every distinct path prefix and accepting states carry the length of each completed path measured in tree labels rather than raw tokens. Ignoring child index tokens in that length is what later permits an accepting state to index the subject traversal stack by tree depth.

3. Failure automaton

The trie becomes an Aho-Corasick automaton once every state receives a failure transition to the state representing its longest proper suffix that is also a trie prefix. Missing transitions follow failure links until a valid transition is found or the root state is reached, while accepting outputs propagate through the same failure relation. Solid transitions consume ranked labels or child indices, whereas dashed edges are nontrivial failure transitions and double outlines mark accepting states. Failure transitions which return directly to state 0 are omitted from the drawing because they obscure the trie without adding another suffix relation. State 6 fails to state 7 because the proper suffix a/2 2 is itself a prefix of the path ending in c/0.

The resulting failure automaton is:

4. Subject traversal

The subject is traversed in preorder with a stack containing the current subject node, the automaton state reached at that node and the index of the next child to visit. Entering a node feeds its ranked label into the automaton, while descending through child \(i\) first feeds the token \(i\) and then feeds the ranked label of the child. Returning from a subtree restores the state saved in its parent frame instead of retaining a state derived from the completed sibling path. Each subject edge is therefore traversed at most twice and every automaton state remains local to one active root to node path.

When an accepting state emits a path length \(\ell\), the path began at stack[top - length + 1] because the stack contains one entry for every ranked label but none for child index tokens. A counter attached to that origin is incremented for each distinct pattern path recognized from the same node, and the origin becomes a complete match when its counter reaches the number of pattern leaves. This counter join is the tree operation that has no counterpart in ordinary string matching because independently recognized paths must agree on a common root before they constitute one tree match. Failure outputs can increment several candidate roots at one accepting state when one pattern path is a suffix of another.

The central traversal can be expressed directly in OCaml once step implements the Aho-Corasick transition function and each state exposes its output lengths:

let tabulate top current =
  List.iter
    (fun length ->
      let origin = stack.(top - length + 1) in
      let count = 1 + Option.value ~default:0 (Hashtbl.find_opt counts origin) in
      Hashtbl.replace counts origin count;
      if count = required then matches := origin :: !matches)
    (get automaton current).output
in
let rec visit incoming top (Node (id, label, children)) =
  stack.(top) <- id;
  let current = step automaton incoming (Label (label, List.length children)) in
  tabulate top current;
  List.iteri
    (fun index child ->
      let edge_state = step automaton current (Child (index + 1)) in
      tabulate top edge_state;
      visit edge_state (top + 1) child)
    children
in
visit 0 0 subject

5. Ranked and unranked trees

Ranked tree semantics make arity part of the constructor identity, so encoding a label as Label(name, arity) preserves exact subtree matching without an additional terminal marker. An unranked representation that emits only Label name recognizes the required path set but doesn't reject extra children whose indices never occur in the pattern. That weaker semantics is useful for partial structural queries but it isn't the same relation as substitution into a ranked term. Exact matching over an unranked representation can be recovered by incorporating the observed arity into each node token before it enters the automaton.

A wildcard terminates only the path on which it occurs and places no restriction on the size or shape of the consumed subtree. Repeated wildcard syntax doesn't introduce repeated variables because every occurrence is independent, so a pattern such as a(_, _) doesn't require its two subject children to be equal. Equality constrained variables require an additional binding environment and structural comparison after the automaton has identified a candidate root. The path automaton should be treated as a structural filter in that extension rather than as a complete unifier.

6. Complexity

Let \(p\) be the pattern size and \(n\) the subject size, while \(z\) counts accepting path outputs produced during the complete subject traversal. Direct trie construction creates \(O(p)\) states because common path prefixes remain shared, and failure link construction is linear in those states when automaton transitions have constant time lookup. A total transition table instead requires \(O(p|\Gamma|)\) space for token alphabet \(\Gamma\), although it makes every automaton step a single indexed lookup. The subject contributes exactly one ranked label token per node and one child index token per edge, so matching takes \(O(n + z)\) time with constant time counter updates.

For one pattern let \(\mathit{suf}\) be the largest number of its path strings which occur as suffixes of any one path string, including that string itself. Then \(z = O(n\mathit{suf})\), which gives linear matching for a full pattern whose paths all have the same length but reaches \(O(np)\) for the worst shaped patterns. For a forest the \(O(n + z)\) output sensitive bound still applies after inserting every path into one shared automaton, while each output additionally carries the pattern identifier needed to select its completion count. The counter array can use subject node identifiers and the traversal stack can be a depth sized array, which keeps both root recovery and counter updates constant time. A different bit string formulation associates a height indexed word with each active subject node, intersects the words computed for its children and shifts the result by one level before testing the match bit. When the pattern height fits a machine word and those operations are constant time this removes the suffix dependent counter work and gives \(O(n + m)\) matching time, where \(m\) is the number of complete matches reported. Treating a DAG as its tree unfolding requires separate path contexts because suppressing revisits by node identity would discard distinct root to node paths and invalidate both the automaton state and the recovered origin.

7. Compiler use

Instruction selection can encode each machine rule as a ranked tree pattern whose wildcard positions capture operands and whose accepting pattern identifier names a candidate instruction at the recovered subject root. The matcher enumerates structurally applicable rules but doesn't choose a cover, so cost based selection still requires dynamic programming or another policy over the candidates attached to each IR node. Term rewriting uses the same match roots as rewrite sites and can retain the automaton across repeated subjects when the rule forest is fixed. Incremental mutation is possible by reprocessing the neighborhood within the longest pattern path of the modified node, although maintaining its saved states and counters is more involved than running the traversal over an unchanged subject.

8. Demo

With Strict selected, the matcher below accepts the same ranked prefix notation used throughout the article, assigns preorder identifiers to subject nodes and reports every root whose complete subtree satisfies the pattern: