Lesson 16 · Difference of postings - Build a Search Engine

Difference of postings

Today you compute the documents in one postings list but not another - the difference. It completes your boolean toolkit and is exactly what AND NOT needs.

The goal

Compute the documents present in the first postings list but absent from the second.

Start here - the target

TO DO

Scenario: Documents in one term but not another

Giventhe postings ["d1", "d2", "d3"] and ["d2"]

Whenthe second is subtracted from the first

Thenthe result is ["d1", "d3"]

Andsubtracting an empty list returns the first list unchanged

Background

The last boolean operation is difference: the documents in a that are not in b, which is what cat AND NOT dog asks for. Like the others it is a linear merge over two sorted lists - emit an id from a only when b has moved past it without matching, and skip any id the two lists share.

With intersection, union, and difference in hand, you can evaluate any AND / OR / NOT combination by composing these three over postings lists. The query chapter will parse boolean expressions and lean entirely on the primitives you finished today; the retrieval math underneath is already done.

Make it work

def difference(a, b):
    i = j = 0
    out = []
    while i < len(a):
        # emit a[i] unless it also appears in b; advance b to keep up
        ...
    return out