The terms met only in the query

Consider two documents after the analyzer from Chapter 3 has produced token positions:

document 7:  new(4) york(5) hosted(6) the(7) meeting(8)
document 9:  new(3) evidence(4) arrived(5) ... york(91) hosted(92)

Both document identifiers occur in $P(\text{new})\cap P(\text{york})$. Only document 7 contains the phrase “new york.” Boolean retrieval remembers membership and forgets arrangement.

The smallest counterexample needs just three tokens:

new bright york

The document contains both terms. It does not contain the two-token phrase. No scoring adjustment can repair the lost fact with certainty; the index must retain or reconstruct position.

Shift the positions until equality means adjacency

For document $d$, let $P_i(d)$ be the strictly increasing positions of the $i$th phrase term. For the phrase

$$q=(t_1,t_2,\ldots,t_r),$$

a start position $s$ is valid exactly when

$$s+i-1 \in P_i(d)$$

for every $i$ from 1 to $r$.

Subtract each term's phrase offset from its stored positions:

$$Q_i(d)=\{p-(i-1):p\in P_i(d)\}.$$

Then all terms belong to one phrase beginning at $s$ exactly when the shifted lists agree on $s$:

$$\operatorname{Starts}(q,d)=\bigcap_{i=1}^{r} Q_i(d).$$

The phrase problem is the previous chapter's set intersection after a change of coordinates.

For “to be or not to be,” suppose one document has

to   [7, 11]
be   [8, 12]
or   [9]
not  [10]

Subtract offsets $0,1,2,3,4,5$ from the six term-occurrence lists. Every shifted list contains 7, so 7 is a phrase start. The repeated terms are not a special case; each phrase position contributes its own shifted list.

PHRASE-STARTS(P)
Input:  sequence P[1:r] of sorted position lists for one document
Output: sorted positions at which the r-term phrase begins

R ← positions in P[1]
for i ← 2 to r
    S ← empty sequence
    a ← 1
    b ← 1
    while a ≤ length(R) and b ≤ length(P[i])
        shifted ← P[i][b] - (i - 1)
        if R[a] = shifted
            append R[a] to S
            a ← a + 1
            b ← b + 1
        else if R[a] < shifted
            a ← a + 1
        else
            b ← b + 1
    R ← S
    if R is empty
        return R
return R

The merge invariant from Chapter 4 survives the translation: before each comparison, S is exactly the intersection of the consumed shifted prefixes, and a smaller current value cannot reappear in the opposing suffix. Therefore each pass computes

$$R_i=R_{i-1}\cap Q_i(d).$$

By induction,

$$R_i=\bigcap_{j=1}^{i}Q_j(d),$$

so $R_r$ is exactly the set of phrase starts.

No cursor retreats. On pass $i$, the work is $O(|R_{i-1}|+|P_i(d)|)$, and $|R_{i-1}|\le |P_1(d)|$. Across a fixed phrase, the standard positional merge is bounded by

$$O\!\left(\sum_{i=1}^{r}|P_i(d)|\right)$$

time and by the size of the surviving starts in working space. A streaming or in-place two-list evaluator can use $O(1)$ cursor space, but a reusable result sequence must store its output.

Find candidate documents before opening positions

Positions are nested under document identifiers. The query should first intersect document-only postings, beginning with a rare term, and open position lists only for surviving documents. That order avoids positional work in a document already disproved by membership.

There are now two different reasons to start with the shortest term list:

1. at the document level it minimizes the upper bound on candidate documents;
2. inside a candidate document, anchoring the phrase on a term with few occurrences minimizes proposed alignments.

The second reason needs care. Offsets are relative to the first term in the formula, but the algorithm need not physically begin there. Choose any anchor term $t_k$. A position $p\in P_k(d)$ proposes the phrase start $s=p-(k-1)$; every other list must contain $s+i-1$. The semantics stay fixed while the probe order follows occurrence counts.

Near is not the same relation

An exact phrase is a filter: either all required offsets exist or they do not. Proximity usually belongs in ranking. “distributed systems” might deserve more weight when its terms are adjacent, some weight when separated by two tokens, and no special weight when separated by a page.

Three predicates that interfaces often blur are:

For two terms with position lists $A$ and $B$, a forward two-pointer walk can enumerate ordered pairs satisfying

$$0 < B[j]-A[i] \le k.$$

For many terms, a minimum-covering-window algorithm tracks one current occurrence from each list in a min-heap and the maximum current position. The current minimum and maximum delimit a covering span; advancing the list that owns the minimum is the only move that can shrink its left boundary.

MINIMUM-COVERING-WINDOW(P)
Input:  nonempty sorted position lists P[1:r]
Output: a minimum-width interval containing one position from every list

H ← empty min-heap ordered by position
right ← negative infinity
for i ← 1 to r
    insert (P[i][1], i, 1) into H
    right ← max(right, P[i][1])
best ← [minimum position in H, right]
while H contains one entry from every list
    (left, list, offset) ← remove minimum from H
    if right - left < width(best)
        best ← [left, right]
    next ← offset + 1
    if next > length(P[list])
        return best
    position ← P[list][next]
    insert (position, list, next) into H
    right ← max(right, position)
return best

The heap holds $r$ entries. Every occurrence enters and leaves at most once, so for $T_d=\sum_i|P_i(d)|$ examined positions the time is $O(T_d\log r)$ and the auxiliary space is $O(r)$. Exact phrase evaluation is cheaper because fixed offsets collapse the admissible windows to equality.

Positions cost one fact per occurrence

A document-only index needs at most one membership fact for each distinct term–document pair. A positional index needs one position for every indexed token occurrence. If the corpus contains $T$ analyzed tokens, its positional payload has $\Theta(T)$ entries even when the vocabulary is small.

This is a different scaling variable from the number of documents $N$. One hundred thousand repetitions in one document add one document posting and one hundred thousand positions.

The exact byte ratio depends on gap coding, block structure, fields, term distribution, and document lengths. Manning, Raghavan, and Schütze give a historical rule of thumb: positional indexes were often two to four times the size of non-positional indexes, while compressed positions could occupy about one-third to one-half of the unmarked source text. Those are corpus-dependent measurements, not constants of the data structure.

Count the boundary you actually ship:

• dictionary bytes;
• document identifiers and term frequencies;
• position gaps and block metadata;
• restart points or skip samples;
• resident decoded state;
• bytes transferred before the first phrase result.

The network chapters will return to this bill. A phrase feature purchased in the index becomes decode and transfer work later.

Store adjacency instead

A biword index treats every consecutive pair as a vocabulary term:

friends romans countrymen

friends␠romans
romans␠countrymen

A two-term phrase becomes one exact dictionary lookup. Longer phrases can intersect overlapping biwords, but overlap alone can admit false positives. One document might contain “stanford university” and “university palo” in different places. Without positions or source verification, their conjunction does not prove “stanford university palo.”

A next-word index stores, for each term occurrence or term–document pair, which word follows and where. It can accelerate frequent phrase workloads but expands the relation being stored. Hugh Williams, Justin Zobel, and Dirk Bahle measured combined indexes that use ordinary inverted lists plus selected next-word or phrase indexes; their conclusion was a workload trade, not a replacement theorem.

The selection criterion is not merely popularity. A phrase made of common terms can be expensive to verify even when queried less often than an easy phrase made of rare terms. Materialize work avoided, not fashion.

Turn the analyzed tokens into one searchable text

There is another representation. Encode each analyzed token followed by a separator that can never occur inside a token:

␀new␀york␀hosted␀the␀meeting␀

Use a distinct document boundary marker, or build one stream per document, so a phrase cannot cross documents. Now an exact token phrase is a substring whose tokens are joined by the separator and anchored with separators at both ends:

␀new␀york␀

The leading separator matters. Searching only new␀york can begin inside a token and falsely match renew␀york. The trailing separator closes the last term. Omitting only that trailing separator intentionally changes the question to “exact preceding tokens, prefix final token.”

A suffix array stores the starting offsets of all suffixes of this stream in lexical order. Two boundary searches find the contiguous range of suffixes beginning with the phrase probe. With straightforward comparison, a probe of $p$ encoded units over a stream of length $T$ costs $O(p\log T)$; longest-common- prefix refinements can avoid rechecking shared prefixes.

This approach is sometimes described as “phrase search without positions.” That phrase is physically misleading. The suffix array itself stores one offset per suffix—$\Theta(T)$ offsets—and the encoded token stream must also remain available. It may require zero additional phrase metadata when a full-text suffix array is already justified by substring or prefix workloads. Built solely to avoid a positional index, it still pays a substantial index bill.

That correction records an important wrong turn: moving the relation to a different structure does not make it free.

The separator encoding changes semantics too. It searches analyzed-token adjacency, not raw-character adjacency. “new, York,” “new” at a line break, and terms split by markup can all become new␀york because punctuation, whitespace, and elements were removed before encoding. Usually that is the desired phrase contract. It must still be stated.

One relation, several physical answers

The designs now occupy an honest trade space.

Hybrid systems are normal. A small phrase cache or selected next-word index can accelerate expensive head queries while positional postings preserve generality. A suffix array may already exist for substring discovery and then serve exact token phrases cheaply. The correct comparison includes construction, update, artifact, transfer, residency, and query costs under one workload trace.

What not to conflate

• Containing all terms does not imply containing their phrase.
• Exact phrase filtering does not imply that proximity should be a hard filter.
• Character adjacency does not imply token adjacency, or vice versa.
• Intersecting overlapping biwords does not always prove a longer phrase.
• “No positional postings” does not mean “no position-like storage.”
• A historical size ratio is not a bound and does not transfer unchanged to a new corpus or encoding.

The reference implementation should remain the analyzed token stream itself: scan each candidate document for the exact token sequence and compare every accelerated representation against that oracle. Pin counterexamples at token, markup, and document boundaries.

From truth to evidence

We can now answer whether a document contains a term, every term, an exact phrase, or a bounded window. Several documents may pass all those tests. A Boolean result has no opinion about which one should appear first.

Counting occurrences seems like the obvious next step. It fails immediately: ten repetitions of “the” do not carry the same evidence as one occurrence of a rare technical term, and a short focused note should not lose merely because a long book has more places to repeat a word.

The next chapter turns rarity into log-odds, makes repetition saturate, and asks document length to explain itself.

Lessons

• A phrase start $s$ satisfies $s+i-1\in P_i(d)$ for every phrase term.
• Subtracting phrase offsets turns exact phrase matching into ordinary sorted intersection.
• Positional evaluation is linear in the total positions examined, after document-level intersection has removed impossible candidates.
• Exact phrase, ordered proximity, and unordered windows are distinct relations with different algorithms and product meanings.
• Positional payload scales with analyzed token occurrences, not merely with documents or vocabulary.
• Biword and next-word indexes materialize adjacency; they trade generality for narrow query speed.
• A separator-joined token stream makes token adjacency searchable as a substring, but boundary markers and document sentinels are correctness obligations.
• A suffix array can eliminate additional phrase metadata only when the full-text structure is already justified. Its offsets are not free storage.

Practice

1. For position lists [2, 10, 20], [3, 11, 40], and [4, 12, 41], compute every start of the three-term phrase by shifting and intersecting.
2. Give the smallest document in which the biwords “a b” and “b c” both occur but the phrase “a b c” does not.
3. Modify MINIMUM-COVERING-WINDOW to preserve every tied minimum interval. State the additional output-space cost.
4. Encode two documents with token and document separators. Write exact and open-final-token probes that cannot cross a document boundary.
5. Design a benchmark comparing positional postings and a suffix array. Name construction bytes, artifact bytes, transferred bytes, resident bytes, positions or suffixes touched, and an exact token-scan oracle.

References

1. Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. “Positional Postings and Phrase Queries.” In Introduction to Information Retrieval. Cambridge University Press, 2008.
2. Udi Manber and Gene Myers. “Suffix Arrays: A New Method for On-Line String Searches.” SIAM Journal on Computing 22, no. 5, 1993.
3. Hugh E. Williams, Justin Zobel, and Dirk Bahle. “Fast Phrase Querying with Combined Indexes.” ACM Transactions on Information Systems 22, no. 4, 2004.