How a search box answers so fast
An inverted index is a table that lists, for every word, the documents that contain it. It is how a search box answers in a fraction of a second instead of reading every page.
By the end of this lesson you will build one in Python and answer queries with AND, OR and NOT.
By the end of this lesson
Note
I can find documents for a word with an inverted index.
Key words
| Word | What it means | Example |
|---|---|---|
| Document | one piece of text that can be found | a web page, an email |
| Query | the words a person types to search | |
| Inverted index | a table from each word to the documents that hold it | |
| Posting list | the list of document numbers for one word | [1, 3] |
| Boolean search | a search that combines words with AND, OR and NOT |
The cells students fill in are left blank in this preview.
Why not read every document each time?
The simplest search reads every document and checks for the word. That is called a scan. With a million documents, one query means a million reads.
An inverted index does the reading once, in advance. After that, a query is a lookup in a table, and a lookup is fast however many documents there are.
What is stored in an inverted index?
A book has an index at the back: a word, then the pages it is on. An inverted index is the same idea. It is called inverted because a document normally holds its words, and the index turns that round: each word holds its documents.
The list of document numbers for one word is its posting list.
Worked example: four documents and their index
| Word | Posting list | Meaning |
|---|---|---|
| bus | [1, 2] | in documents 1 and 2 |
| cheap | [1, 3] | in documents 1 and 3 |
| tickets | [1, 3] | in documents 1 and 3 |
| timetable | [2, 4] | in documents 2 and 4 |
| train | [3, 4] | in documents 3 and 4 |
| monday | [2, 3] | in documents 2 and 3 |
| for | [2, 3] | in documents 2 and 3 |
The cells students fill in are left blank in this preview.
Build an index in Python
docs = {
1: "cheap bus tickets",
2: "bus timetable for monday",
3: "cheap train tickets for monday",
4: "train timetable",
}
index = {}
for doc_id in docs:
for word in docs[doc_id].split():
if word not in index:
index[word] = []
if doc_id not in index[word]:
index[word].append(doc_id)
print(index["cheap"])
print(index["train"])
# Look up "monday". Which documents are in its list?
How do you build an index?
Go through the documents one at a time. Split each into words. For each word, add the document number to that word's posting list, unless it is already there.
Because you visit the documents in order, every posting list ends up in order too. Keeping them in order makes combining them easy.
Look up one word in the documents
docker exec jupyter python3 -c "d={1:'cheap bus tickets',2:'bus timetable for monday',3:'cheap train tickets for monday',4:'train timetable'}; print([k for k in d if 'bus' in d[k].split()])"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
How do AND, OR and NOT work?
A query often has more than one word. AND keeps the documents that are in both lists. OR keeps the documents that are in either list. NOT removes the documents that are in a list.
Each is a short loop over two lists of numbers. No document text is read.
Worked example: combining two lists
| Query | Lists used | Result |
|---|---|---|
| cheap AND train | cheap [1, 3] and train [3, 4] | [3] |
| bus OR train | bus [1, 2] and train [3, 4] | [1, 2, 3, 4] |
| all documents NOT bus | [1, 2, 3, 4] without bus [1, 2] | [3, 4] |
The cells students fill in are left blank in this preview.
Combine two lists with AND
cheap = [1, 3]
train = [3, 4]
both = []
for doc_id in cheap:
if doc_id in train:
both.append(doc_id)
print(both)
# Change the loop so it keeps documents that are in cheap but NOT in train.
Run AND, OR and NOT on the lists
docker exec jupyter python3 -c "print(sorted(set([1,3]) & set([3,4])), sorted(set([1,2]) | set([3,4])), sorted(set([1,2,3,4]) - set([1,2])))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think the index holds the documents. It holds only words and document numbers. The text stays where it was, and the search engine fetches it after the index says which documents to show.
Where Boolean search is still used
Library catalogues, email search and file search all use word lookups like this. A Boolean query is exact: a document either matches or it does not.
That is the weakness. With a big collection, thousands of documents may match, and there is no order. The next lessons add a score so the best come first.
Going further
Write five one-line documents about your own week and build an index for them by hand. Then answer two AND queries and one NOT query from the posting lists alone.
Then explain why a word such as "the", which is in every document, makes a poor query word.