40 · Inverted indexes, Boolean retrieval, and positional constraints

Units: S07. Prerequisites: 39.

Sources: Wang Shusen’s pinned outline; Manning et al., Introduction to Information Retrieval (supplementary original textbook, chapters 1, 2, 6, and 8). This is a Lab-authored exercise. Wang's last four modules have a public outline only; this is not presented as the author's complete lecture material.

Evidence boundary: a four-document index checked against enumeration, not a distributed engine.

Learning method: predict each comparison, change one variable, run, and explain the difference.

English companion. All instructional Markdown is translated. Experiment code, Chinese language examples, execution counts, and saved outputs remain as in the source edition; historical output text may therefore be Chinese. The initial setup cell anchors the working directory and Python import path for this companion's deeper folder; it does not change the experiment. Saved outputs are historical evidence, not a new run. Run from the top after preparing the required data and models.

PYTHON · 01

# English companions live one directory deeper; keep the original experiment code unchanged.
from pathlib import Path as _TranslationPath
import os as _translation_os
import sys as _translation_sys
_translation_root = next((p for p in [_TranslationPath.cwd(), *_TranslationPath.cwd().parents]
                          if (p / "reclab").is_dir()), None)
if _translation_root is None:
    raise RuntimeError("Open this notebook from inside the Search Recommendation Ads Lab checkout.")
_translation_os.chdir(_translation_root)
if str(_translation_root) not in _translation_sys.path:
    _translation_sys.path.insert(0, str(_translation_root))

PYTHON · 02

import numpy as np
import pandas as pd
from IPython.display import display
from reclab.learning.search_curriculum import *

Postings

Keys are (field,term); values map doc→positions. Positions are token offsets within each field. A phrase cannot span title and body.

PYTHON · 03

idx=PositionalIndex(DOCUMENTS)
print(dict(idx.postings[('title','repair')]))
assert idx.postings[('title','repair')]['a']==[1]

Saved notebook output · not executed on this page

{'a': [1], 'c': [2], 'd': [1]}

AND / OR

Fix the query and change only the Boolean operator; verify exact agreement with document-by-document enumeration.

PYTHON · 04

for mode in ['AND','OR']:
    got=idx.retrieve('apple battery',mode=mode)
    expected=sorted(d for d,f in DOCUMENTS.items() if (set(terms('apple battery'))<=set(terms(f['title'])) if mode=='AND' else bool(set(terms('apple battery'))&set(terms(f['title'])))))
    assert got==expected
    print(mode,got)

Saved notebook output · not executed on this page

AND []
OR ['a', 'b', 'c', 'd']

Phrases and fields

Matching two terms does not imply adjacency. Compare title/body and AND/phrase conditions.

PYTHON · 05

for field in ['title','body']:
    print(field,'AND',idx.retrieve('apple repair',field,mode='AND'),'phrase',idx.retrieve('apple repair',field,phrase=True))
for q in ['apple repair','battery repair','repair apple']:
    assert idx.retrieve(q,phrase=True)==sorted(d for d,f in DOCUMENTS.items() if any(terms(f['title'])[i:i+len(terms(q))]==terms(q) for i in range(len(terms(f['title'])))))

Saved notebook output · not executed on this page

title AND ['a', 'd'] phrase ['a', 'd']
body AND ['d'] phrase []

Updates and deletion

This mechanism rebuilds a new generation; it does not claim incremental merging. After deleting a, the old index still returns it, exposing a cache-consistency prerequisite. Continue to BM25 in chapter 26 afterward.

PYTHON · 06

updated={d:f for d,f in DOCUMENTS.items() if d!='a'}
new=PositionalIndex(updated)
assert 'a' in idx.retrieve('apple') and 'a' not in new.retrieve('apple')
print('old',idx.retrieve('apple'),'new',new.retrieve('apple'))

Saved notebook output · not executed on this page

old ['a', 'b', 'd'] new ['b', 'd']

Interpreting the saved run

AND and OR results match document-by-document enumeration. Phrase checks additionally require adjacent positions, with body and title matches kept separate. The rebuilt index excludes a while the old index still contains it, establishing a version boundary for the cache lesson.

After changing parameters, interpret the new outputs. This fixed commentary is not a new measurement.

Review and exercise

Write down inputs, outputs, what stayed fixed, and conclusions this chapter cannot support. Predict and rerun one single-variable comparison above; retain failures. Return to the search learning path for the next semantic unit.

40 · Inverted indexes, Boolean retrieval, and positional constraints