FINDING NEEDLES · CHAPTER 01
A search engine does not read every document when you type a word. It has already stored, for each word, the list of documents that contain it.
A shelf of books is a forward list. Each book points at the words inside it. Finding every book that says “cedar” means opening all of them. A card catalog does the opposite. The card for “cedar” already names the books.
That flipped list is an inverted index. The word is the key. The value is a posting list: the document ids, kept in order. Lookup is one hop to the list. Scanning the whole corpus is what you no longer do.
Search starts by deciding which documents are even candidates. Ranking, which asks which candidate is better, comes after. This chapter stops at the candidate step: yes or no.
Small enough to finish by hand. The same three strings are in search_index.py.
catalog · pipeline · invert · latency
| Id | Text | Terms that get stored |
|---|---|---|
| 1 | cedar shingles shed rain | cedar, shingles, shed, rain |
| 2 | slate tiles shed snow | slate, tiles, shed, snow |
| 3 | cedar beams hold the roof | cedar, beams, hold, roof |
Document 3 contains the word “the”. The index does not. “the” is a stop word: so common that a list of every document containing it is almost the whole corpus, and it rarely changes which document you wanted. The tokenizer lowercases, splits on spaces, and drops stop words. Document 3 contributes four terms, not five.
Across the three documents that is 10 terms. Each term is stored once per document, even if a note had repeated it.
| Term | Posting list |
|---|---|
| cedar | [1, 3] |
| shed | [1, 2] |
| roof | [3] |
| shingles, rain | [1] |
| slate, tiles, snow | [2] |
| beams, hold | [3] |
The lists are sorted by document id. That order is the whole trick in the next section. A forward index would have been “document 1 contains cedar, shingles, shed, rain”. Useful if you are displaying the note. Useless if the question is “who said cedar?”.
Interactive · Look up a term
Which documents mention this word?
A Boolean query has no score. A document matches or it does not. AND is the intersection of two posting lists. OR is the union. NOT is everything except a list, which needs a list of all document ids.
Take “cedar AND shed”. The lists are [1, 3] and [1, 2].
each step throws away one id, so you never look at an id twice. Here |A| and |B| are both 2.
Document 3 has cedar and not shed, so it falls out. Document 2 has shed and not cedar, so it falls out too. Ranking would ask whether document 1 is a good match. Boolean retrieval refuses that question. The next chapter starts it.
A real posting list is millions of ids long. Sorted ids are turned into gaps: keep the first id, then how far to the next one. The list [8, 11, 14] becomes the gaps 8, 3, 3. The jumps are smaller integers than the raw ids, and smaller integers compress. You add the jumps back up when a query needs the real ids. Compression here is a way to make the walk faster, not a way to archive the index.
"""A three-document inverted index and a Boolean AND.
The corpus is a roofing workshop, not a textbook fox sentence.
"the" is a stop word, so it never gets a posting list.
"""
# Three short documents. Ids are 1, 2, 3 so the lists stay easy to read.
DOCS = {
1: "cedar shingles shed rain",
2: "slate tiles shed snow",
3: "cedar beams hold the roof",
}
# Dropped before anything is written into the index.
STOP = {"the"}
# A longer sorted list, used only to show gap encoding.
GAP_IDS = [8, 11, 14]
def tokenize(text):
"""Lowercase, split on spaces, drop stop words.
The same function must run on documents and on queries.
A query that keeps "the" will look up a term the index never stored.
"""
return [word for word in text.lower().split() if word not in STOP]
def build_index(docs=None):
"""Map each term to the sorted document ids that contain it.
One posting per document, even if the word is repeated.
Lists stay sorted by id so intersection can walk them once.
"""
docs = DOCS if docs is None else docs
postings = {}
for doc_id in sorted(docs):
seen = set()
for term in tokenize(docs[doc_id]):
if term in seen:
continue
seen.add(term)
postings.setdefault(term, []).append(doc_id)
return postings
def intersect(left, right):
"""Documents in both sorted lists. One pass, no nested scan."""
i = 0
j = 0
hits = []
while i < len(left) and j < len(right):
if left[i] == right[j]:
hits.append(left[i])
i += 1
j += 1
elif left[i] < right[j]:
i += 1
else:
j += 1
return hits
def gaps(doc_ids):
"""Store the first id, then the jumps between sorted ids.
[8, 11, 14] becomes [8, 3, 3]. The jumps are smaller than the
raw ids, which is why posting lists compress.
"""
if not doc_ids:
return []
jumps = [doc_ids[0]]
for previous, current in zip(doc_ids, doc_ids[1:]):
jumps.append(current - previous)
return jumps
A different tokenizer at query time. If the documents dropped “the” and the query keeps it, AND looks up a term with no list and returns nothing. The analyzer is part of the index, not a cosmetic step.
Expecting a “best” document. [1] means “mentions both words”. It does not mean the note answered you. A document that says “cedar” once and one that says it in the title look the same to Boolean AND.
Unsorted lists. The one-pass merge is wrong if either list is out of order. You would miss matches or have to fall back to scanning every id against every other id.
Document 1 is the only id that sits in both lists. Document 3 has cedar but not shed. Document 2 has shed but not cedar.
“roof” would hit [3]. “the” hits nothing, because it was never stored. AND of a missing list is empty, so you lose document 3.
So intersection advances the smaller id and never goes backwards. Two lists of length n and m cost n + m steps.
No. It means both words occur. How well they match is a score, which this chapter does not compute.