The occurrences that cross a boundary

An occurrence of a pattern lies somewhere in the text. Either it fits inside a single phrase of the parse, or it straddles at least one phrase boundary. There is no third case, and the two cases have completely different costs.

Measured on a collection of thirty-two copies with an eight-character pattern: one occurrence of the first kind and thirty-one of the second. The search looks for the one.

The argument, which is a definition rather than a heuristic #

A phrase is the longest piece of what remains that has already occurred earlier in the text. So the characters of a phrase are, by construction, a copy of characters that appeared before it.

An occurrence lying entirely inside one phrase is therefore a copy of a string that occurred earlier — specifically at the position the phrase’s source points to, offset by however far into the phrase the occurrence sits. That earlier string is an occurrence too, of the same pattern, and it is either primary or itself a copy of a still earlier one.

Following that chain down terminates, because each phrase’s source is strictly earlier than the phrase. So every occurrence is reachable from a primary one by following copies forwards, and a search that finds every primary occurrence and then propagates has found everything.

This is the reason the structure can be proportional to $z$ at all. Searching $n$ positions would need something proportional to $n$; searching $z$ boundaries needs something proportional to $z$, and the argument above is what says that is enough.

Finding the primaries #

A primary occurrence crosses a boundary, so it can be located by asking, for each boundary and each way of splitting the pattern, whether the left part ends there and the right part starts there.

There are $m-1$ split points and the two questions are answered by two binary searches — one over the boundaries sorted by the suffix that begins there, one over the boundaries sorted by the reversed text that ends there. The result is two ranges, and a boundary in both is a primary occurrence.

The cost of that is $m-1$ pairs of binary searches, each comparison producing characters from the parse, plus the work of intersecting the two ranges. On the collection above the whole primary stage examines three candidates and performs 272 character comparisons, and it examines the same three candidates at two copies and at thirty-two.

Producing the secondaries #

Given an occurrence at position $p$, every phrase whose source region contains $[p, p+m)$ produces an occurrence at that phrase’s own start plus the offset. That is not a search: it is an addition, once the phrase is known.

Finding the phrases is a range query over the sources, and the queue is run to fixpoint because a copy can itself be copied. A collection of thirty-two copies produces its occurrences in a chain thirty-one long, each one discovered from the one before it.

The published structures answer that range query with a second two-dimensional grid. This one walks the phrases in source order and counts what it examines, which is 4,352 phrases to produce 31 occurrences at thirty-two copies and 242 to produce one at two copies. The ratio is what a grid is for, and reporting it is how a plate says which structure it drew.

What the split says about where a search’s cost goes #

The two stages are so different in shape that a single “search cost” for this structure would be misleading in both directions.

The primary stage’s cost depends on $z$, on $m$ and on the copy depths the binary searches happen to land in. It does not depend on how many occurrences there are — a pattern with one occurrence and a pattern with a thousand cost the same to search for.

The secondary stage’s cost is per occurrence produced and depends on nothing else. It is the analogue of the r-index’s $\varphi$ step, which is also one operation per answer, and the two structures are closer here than anywhere: both have separated the question “does this occur” from the question “where”, and both charge the second per answer.

The difference is that the r-index gets its first occurrence free, out of the search, as the occurrence carried through the search measures, while the parse-based index has to search for every primary and there may be many.

Two costs that are not comparable, drawn on one plate anyway #

The stages’ costs are in different units — character comparisons for the search, phrases examined for the propagation — and this collection’s rule is that such things are not summed. The plate that shows both draws them as one bar split into two parts and names each, which is the compromise, and it is worth saying why the compromise is acceptable here.

Both quantities are candidates: things the machinery looked at and mostly discarded. A candidate boundary in the intersection and a candidate phrase in the propagation are the same kind of act at the same level of the structure, and neither of them is a text read or a bit-vector rank. Summing them gives the number of times the structure examined something, which is a quantity a reader can use.

What is not summed anywhere is those candidates and the chain walks they cost. A comparison during a binary search examines one candidate and follows a chain of whatever depth that position has, and the depths run from two to thirty-eight on this collection. So the plates report candidates and chain steps separately, in the way one run, two counts established for this collection’s first pair of counters.

The failure this invites #

There is a specific way to get this wrong that no ordinary check catches, and it is the reason the gate for this structure compares against exhaustion.

Report only the primaries. They are all genuine occurrences: every one of them was found by matching the pattern’s two halves against real text. Nothing about them is wrong except that there are far too few — one against eight on a collection of eight copies, measured, and one against thirty-two on a collection of thirty-two.

A check asking “is every reported position an occurrence” passes. A check asking “does the count match the interval width” has nothing to compare against, because there is no interval. A check comparing against another index catches it, and a check comparing against a scan of the text catches it, and nothing else does.

This collection has met that shape before in a filter rather than an index: the filter that proposes everything is about a stage whose output is correct and useless, and the rejection test there is the same one — feed the machinery a version that skips a stage and require the gate to notice.

Why the primary count is flat and not merely slow-growing #

The plate at the top shows a line that does not move, and it is worth checking whether that is a property or a coincidence of this pattern.

The primaries are the occurrences crossing a boundary. When a text is copied, its parse gains one phrase — a single reference covering the whole copy — so the copy contributes no new boundaries inside itself. Every occurrence inside the second copy therefore lies inside one phrase, and is secondary.

That is exact rather than approximate: at two copies, four, eight, sixteen and thirty-two the primary count is one, one, one, one and one, and the secondary count is one, three, seven, fifteen and thirty-one. The pattern is $2^k - 1$ because each copy’s occurrence is produced from the previous copy’s, which is the chain the propagation queue walks.

Drift breaks it. At one substitution per hundred characters per copy the copies are no longer single phrases, boundaries appear inside them, and some of the occurrences become primary — which is measurable and is what makes the flat line a claim about identical copies rather than about repetitiveness in general.

The two kinds are checked as a definition #

The classification is not a label attached by the code that produced each occurrence; it is checked against the parse.

For every occurrence the search stage reports, the check finds the phrase containing its start position and requires the occurrence to run past that phrase’s end — that is, to cross the boundary. For every occurrence the propagation produces, it requires the opposite.

That matters because “primary” and “secondary” are otherwise just names for “found by the first stage” and “found by the second”, which would make the classification true by construction and worth nothing. Checked against the parse, it is a claim: the search stage finds exactly the crossing occurrences and the propagation finds exactly the contained ones.

On a six-character pattern in a collection of six copies the counts are six primary and thirty secondary, all classified correctly. A single misclassification would mean either that the search had missed a crossing occurrence — a correctness bug — or that the propagation had produced one it should have found, which is a slower but still correct structure.

A reduction is not a filter, and the difference is a stage #

It is worth being exact about what has been removed, because “search fewer places” describes both this and a filter, and they are not the same construction.

A filter proposes candidate positions and hands them to an expensive stage that decides. The proposal may be wrong; the verification is what makes the answer correct; and the filter’s worth is the ratio between what it proposes and what survives — its selectivity, which is a filter has a selectivity in this collection’s vocabulary and is measured for two filters in this same phase.

The parse’s reduction proposes nothing. An occurrence lying inside a phrase is an occurrence of the pattern, because the phrase’s characters are a copy, so the propagation produces answers rather than candidates. There is no verification step, no false positive and no selectivity to report.

That is a stronger construction and it has a matching cost. A filter’s guarantee is one-sided and cheap to establish — a pigeonhole argument, in the case of the filter that feeds the table. The reduction’s guarantee needs the parse to be exactly what it claims, and a parse with one phrase whose source is wrong produces occurrences that are not occurrences, silently and in quantity.

Where the shape comes from in other structures #

The split has an analogue in this collection’s other search machinery and it is worth naming, because it is not a coincidence of parses.

The filter that feeds the table splits a pattern into $k+1$ pieces and searches for each of them exactly, on the grounds that one piece must survive $k$ errors intact. That is the same move: an argument that reduces a search over many places to a search over few, followed by a cheap stage that recovers the rest.

One pass for every pattern at once does it differently — a single automaton over all patterns, with no reduction at all — and the difference is exactly whether a structural property of the input is available to exploit.

What is unusual here is that the reduction is exact rather than a filter. A pigeonhole filter proposes candidates that must be verified; this proposes nothing and verifies nothing. An occurrence inside a phrase is an occurrence, by the definition of a phrase, and the propagation is arithmetic rather than a check.

What this costs in the worst case #

The flat primary count is a property of collections of copies, and the worst case runs the other way.

A text with no repetition at all has $z$ near $n/\log_\sigma n$ and phrases of a few characters each, so almost every occurrence of a pattern longer than a phrase crosses a boundary and almost everything is primary. The propagation then produces nothing and the search does all the work, over $z$ boundaries which is nearly $n$ positions.

That is the same degeneration a sampling that costs more than the array records for the run-based structure, arriving at the query rather than at the size. Both structures are built on a measure, and on a text where the measure is $\Theta(n)$ the structure is a slow version of something simpler.

What the two stages do to a query’s shape #

Put the pieces together and a query against this structure has a cost with two terms and no dial in it.

The first term is $m-1$ pairs of binary searches over $z$ boundaries, each comparison costing a chain walk. That term depends on the pattern’s length, on the parse’s size, and on where in the text the binary searches happen to land — and it is paid whether the pattern occurs once or a thousand times.

The second is one range query per occurrence produced. On this implementation that is a linear scan of the phrases whose sources could contain it; on a published one it is a logarithmic range query. Either way it is per answer.

So the structure is at its best on queries with many answers over a collection with few phrases, and at its worst on queries with no answers over a text with many. Both extremes are measured in this strand, and the second is the one a reader is more likely to have.

That shape — a fixed cost for the question and a marginal cost per answer — is the same one an index larger than what it indexes drew for a suffix array and a search that runs backwards drew for a transform. Three structures, three mechanisms, one shape, and the constants are where they differ.

The unmeasured case has an arithmetic #

The last of the limits below — a pattern whose occurrences all cross boundaries on a collection that repeats — is named as unmeasured, and it can be bounded without measuring it.

On a collection of $k$ copies of a base of length $L$, every copy after the first is one phrase. So a pattern of length $m \le L$ lying wholly inside a copy lies inside that phrase and is secondary, always. The only way an occurrence in a later copy can be primary is for it to straddle a junction — the seam where one copy ends and the next begins.

And every junction is the same text: the end of the base followed by its start. So the pattern either straddles a junction or it does not, and the answer is the same at all $k-1$ of them.

The primary count therefore takes exactly two values on a collection of exact copies: one, or $k$. Not a smooth rise — a step. The flat line at $m = 8$ is the first case; the rise at $m = 12$ is the second, and it rises linearly because a junction match is one match per junction.

That makes the bad case sharp rather than vague. If the pattern straddles the junction, every occurrence is primary, the propagation produces nothing at all, and the search does the whole job over $z$ boundaries — on a collection whose $z$ is 156 and whose answer is thirty-two. The structure’s entire advantage is gone on a collection that looks maximally favourable by every measure this field quotes.

How likely is it? A pattern of $m$ characters drawn from a uniform position straddles a junction at $(k-1)(m-1)$ of the $kL$ positions, which for large $k$ is

$$\frac{m-1}{L}.$$

The collection’s size cancels. More copies means more junctions and proportionally more text, so the risk is decided by the pattern length against the base document’s length and by nothing else. At $m = 8$ on a 512-character base it is 1.4%; at $m = 64$ it is 12%; at $m = 128$ it is a quarter.

Which turns the unmeasured case into a stated condition. This structure is safe for patterns short against the repeating unit and degrades as the pattern approaches it — a query for a phrase inside a document is fine, and a query for something as long as the document is where the reduction stops reducing. That is a different axis from the one the phrases a text copies from itself sweeps, which varies the collection while holding the pattern short.

It also explains the drifting sweep without appealing to anything new. One substitution per hundred characters breaks each copy into many phrases, so the junctions stop being the only seams and the two-valued step becomes a spread — which is what that plate shows, and what makes the flat line a claim about identical copies rather than about repetition, exactly as this page says. An index with z in its size prices the structure on the assumption that the flat case is the usual one, and $(m-1)/L$ is how often it is not.

The honest limit #

The propagation here is a queue over phrases sorted by source, examined linearly within a source range. A published structure answers the same question with a two-dimensional range query and the counts on these plates are what that query would replace — so the search costs in this essay are upper bounds for a structure nobody here built, and every plate carries the candidate count for that reason.

The classification check runs on one pattern per collection rather than on many, because it requires the parse and the occurrence set together and the exhaustive comparison is quadratic. The counts quoted are therefore exact for the patterns measured and are not a distribution.

What is not here is a pattern longer than a phrase in a repetitive collection — a query where every occurrence crosses a boundary even though the collection repeats. That is the case where this structure’s advantage disappears while the collection still looks favourable, and it is not measured.