Query Segmentation into Phrases for Ranked Retrieval

The query new york pizza contains three terms and one phrase. A bag-of-words scorer treats new, york, and pizza as independent evidence, which means a document about new pizza in York scores about the same as a document about New York pizza. The information that new york is a unit is not in the query string and is not in any single term’s postings list; it has to be inferred, and then it has to be used.

Query segmentation is the inference step. It partitions a term sequence into contiguous segments, each of which is a phrase that should be scored as a unit, leaving the remaining single terms as they were.

What segmentation buys, mechanically

Two changes happen when a segment is treated as a unit.

The first is scoring. A phrase’s score can use a statistic over the phrase as a term: its own document frequency, its own length normalization, its own inverse document frequency. A document containing new york scores on the phrase’s IDF rather than on the sum of the two words’ IDFs, and since new york is far rarer than new, this concentrates weight on documents that contain the actual unit. Without segmentation, new is a common word with low IDF, and york carries nearly all the signal, which is close to the right answer by accident but wrong for the wrong reason.

The second is matching. A segment compiled as a phrase query requires adjacency, so a document with york and new in separate sentences no longer matches the segment. This is a precision gain and a recall loss at the same time, and which dominates depends on whether the segment is correct.

Segmentation also changes what proximity and phrase operators can be applied downstream. If the segmenter decides new york is a unit, a later rewriting step can expand it to NYC or to a synonym class as a unit; the expansion machinery operates on segments, not terms.

Two families of model

Statistical segmentation asks which partition is most probable under a language model over terms. For a query $q = t_1 \dots t_n$, a segmentation is a set of cut points, and the score of a candidate is usually a product of segment probabilities, where a segment’s probability is estimated from its frequency in a corpus of queries or documents. The partition maximizing the product is found by dynamic programming over the $2^{n-1}$ possible cut sets, which for $n \le 10$ is a trivial search and for longer queries is still linear in $n$ times the number of states.

The estimator is the crux. Segment frequencies come from a corpus, and the corpus is sparse at the segment level: new york is frequent, new york pizza less so, and most candidate segments have a count of zero. Estimating a zero as zero makes the model prefer the finest partition, since every singleton has a count. Estimating zeros with a smoothing term and combining unigram and bigram counts is the standard repair, and the choice of smoothing moves the boundary between aggressive and conservative segmentation.

The alternative family derives segments from document structure rather than frequency. A segmenter can be trained on click data: if a query’s terms appear together in a clicked document’s title, or in a clicked result’s snippet as a contiguous run, that run is evidence for a segment. The approach has an appealing property, that it learns the segmentation of the collection’s own content rather than of general language, and it needs no manually segmented corpus.

The two are often combined: frequency statistics propose segments, and document evidence filters them.

The over-segmentation failure

Every frequency-based segmenter will cut to be or not to be into as many pieces as its statistics prefer, and the result is a query that is a conjunction of common words. The failure is not in the algorithm but in the assumption that segmentation improves every query.

The symptoms are recognizable. Over-segmented queries return fewer results than the term-only version, because each phrase imposes an adjacency constraint that the collection does not satisfy. Under-segmented queries return too many, because a phrase that should have been split is scored as a rare unit and dominates the ranking. Both errors are invisible in aggregate metrics if the corpus of test queries is dominated by one shape.

The guard that matters is a fallback: if segmenting a query reduces its result count below a threshold, revert to the unsegmented form. The threshold can be expressed relative to the unsegmented count, so a query whose segmentation loses 90 percent of its matches is treated as a segmentation failure rather than as a precision win. This is the same conditional-rewrite pattern that spelling correction uses, applied at a coarser granularity.

Segments that are not adjacent in the index

A segment must correspond to consecutive token positions in the index, and that depends on what the analyzer did to the text. A document reading New-York style pizza tokenizes, under a hyphen-splitting analyzer, to new, york, style, pizza, so the segment new york matches. A document reading New York also matches. A document with a stop word between the two, such as new in york, does not, unless the stop-word filter closed the gap, which is precisely the behaviour that the stop-word discussion argues against.

Segmentation therefore cannot be designed independently of the analyzer. A segmenter that assumes adjacency in surface text will over-constrain queries against an index whose tokenization splits compounds.

def segment(terms, score_fn):
    """Best partition of terms into contiguous segments, maximizing total log score."""
    n = len(terms)
    best = [0.0] * (n + 1)
    cut = [0] * (n + 1)
    for end in range(1, n + 1):
        best[end] = float("-inf")
        for start in range(end):
            s = best[start] + score_fn(terms[start:end])
            if s > best[end]:
                best[end], cut[end] = s, start
    out, end = [], n
    while end:
        start = cut[end]
        out.append(terms[start:end])
        end = start
    return list(reversed(out))

The recurrence is $O(n^2)$ segment evaluations, each of which is a lookup. For the query lengths that occur in practice this is a few dozen dictionary probes, and the cost is dominated by cache behaviour rather than by the arithmetic.

Segments, units, and the ranking interaction

Turning a segment into a phrase changes the score in a way that is not simply additive. A phrase’s document frequency is at most the minimum of its constituent terms’ frequencies, and usually far smaller, so its IDF is larger. A document that contains the phrase gets a large contribution; a document that contains only the individual terms gets nothing from the segment. The ranking therefore becomes more binary: documents either have the unit or they do not.

Whether that helps depends on whether the unit is a real concept or an accident of adjacency. new york is a concept. the who is a concept. of the is not, and segmenting it produces a phrase whose IDF is high enough to dominate the score while carrying no topical information. Stop-word segments are the clearest case where segmentation must be suppressed rather than tuned.

A workable policy is to score segments as phrases only when the segment’s corpus frequency exceeds a floor and its constituent terms are not all stop words. Both conditions are cheap to check against statistics already available to the scorer.

Longer queries and the combinatorial edge

Queries of one to four terms are the bulk of the workload, and the dynamic program handles them exactly. Longer queries, which occur in voice input and in copy-pasted sentences, have more cut sets and more room for a segmenter to be confidently wrong. For those, restricting segments to at most three or four terms bounds both the search and the damage, and it matches the length distribution of genuine multi-word units: most named entities and fixed phrases are short.

The interaction with correction is worth pinning down. Spelling correction should run before segmentation, because a misspelling inside what would otherwise be a unit prevents the unit from being recognized, and correcting after segmentation means the segmenter worked on a broken string. The ordering is: normalize, correct, segment, expand. Each step assumes the previous one produced plausible terms, and reversing any adjacent pair produces a specific class of silent failure.