Build an Inverted Index from Scratch in Python

In this tutorial, you will build a complete, functioning positional inverted index from scratch using Python standard library tools. By the end of this guide, you will have a working script that tokenizes text, builds in-memory posting lists, and executes single-term, boolean, and exact phrase queries. You will also implement disk persistence to save and reload your index.

What you need

To follow this tutorial, you need Python 3.10 or later installed on your system. We use exclusively the Python standard library, meaning you do not need to install third-party packages from PyPI or configure virtual environments. If you want to review the theoretical concepts behind inverted indices before writing code, explore our guide to the search engine indexing pipeline.

Our implementation relies on four built-in Python modules: re for regular expression text parsing, json for saving the index to disk, collections.defaultdict for clean nested dictionary structures, and typing for clear type annotations. These modules provide all the primitives required to construct an industrial data structure.

import re
import json
from collections import defaultdict
from typing import Dict, List, Set

Step 1: a corpus to index

Every search engine begins with a collection of documents known as a corpus. For this tutorial, we define a small dictionary where integer keys serve as unique document identifiers and string values represent document text. Using a controlled corpus allows you to verify your query results manually at every step.

corpus = {
    1: "Crawlers discover links on web pages.",
    2: "Search engines index web pages.",
    3: "Crawlers request pages and follow links.",
    4: "Ranking algorithms score indexed pages.",
    5: "Search engines rank relevant web documents."
}

print(f"Loaded {len(corpus)} documents into corpus.")

Running this code produces the following output in your terminal. It confirms that all five documents were stored with sequential integer identifiers:

Loaded 5 documents into corpus.

In a full-scale search engine, these documents would be delivered by an autonomous crawler fetching HTML over HTTP. You can learn how crawlers collect documents in our tutorial on what a web crawler is.

Step 2: tokenize and normalize

Before text can be entered into an index, continuous character strings must be broken down into individual vocabulary units called tokens. Our tokenizer function converts all text to lowercase to ensure case-insensitive matching and uses regular expressions to extract alphanumeric words while stripping punctuation.

def tokenize(text: str) -> List[str]:
    """Tokenize and normalize text into lowercase alphanumeric tokens."""
    return re.findall(r"\b[a-z0-9]+\b", text.lower())

sample_text = corpus[1]
sample_tokens = tokenize(sample_text)
print("Original:", sample_text)
print("Tokens:  ", sample_tokens)

Executing this snippet yields a clean list of lowercase word tokens. Notice that the period at the end of the sentence was automatically discarded:

Original: Crawlers discover links on web pages.
Tokens:   ['crawlers', 'discover', 'links', 'on', 'web', 'pages']

The regular expression \b[a-z0-9]+\b matches word boundaries around alphanumeric sequences. This simple function ensures that punctuation marks like periods and commas do not become part of your indexed vocabulary terms.

Step 3: build the term to postings map

The core data structure of an inverted index maps each unique word to a dictionary of document IDs. In our initial step, we map each term to the set of document IDs containing it. Using defaultdict(set) ensures that new vocabulary terms automatically initialize an empty set when first encountered.

# term -> set of doc_ids
basic_index: Dict[str, Set[int]] = defaultdict(set)

for doc_id, text in corpus.items():
    tokens = tokenize(text)
    for token in tokens:
        basic_index[token].add(doc_id)

print("Indexed terms count:", len(basic_index))
print("Postings for 'crawlers':", sorted(basic_index["crawlers"]))
print("Postings for 'pages':   ", sorted(basic_index["pages"]))

The output confirms that the terms map directly to document identifiers. Each unique vocabulary word points to a set containing the IDs of documents where it occurs:

Indexed terms count: 18
Postings for 'crawlers': [1, 3]
Postings for 'pages':    [1, 2, 3, 4]

Notice how the term pages points to documents 1, 2, 3, and 4. When a user queries for pages, the search engine does not scan the corpus; it performs a dictionary lookup that resolves in $O(1)$ time.

Step 4: query a single term

Querying a single word against the index requires tokenizing the user query and fetching the corresponding posting set from the dictionary. If the term does not exist in the index, the query returns an empty set.

def search_term(index: Dict[str, Set[int]], term: str) -> Set[int]:
    """Return document IDs matching a single term."""
    tokens = tokenize(term)
    if not tokens:
        return set()
    clean_term = tokens[0]
    return index.get(clean_term, set())

print("Query 'search':", sorted(search_term(basic_index, "search")))
print("Query 'python':", sorted(search_term(basic_index, "python")))

Executing single-term lookups produces the matching document identifiers. You can test existing and non-existent words to verify lookup safety:

Query 'search': [2, 5]
Query 'python': []

The query search instantly returns documents 2 and 5, while an unknown term like python returns an empty result set without errors. This predictable behavior prevents missing keys from raising unhandled exceptions in your search application.

Step 5: boolean AND, OR and NOT

Real-world search engines support boolean operations that allow users to combine keywords. In Python, boolean logic translates directly into native set operations: intersection for AND, union for OR, and difference for NOT.

def search_and(index: Dict[str, Set[int]], terms: List[str]) -> Set[int]:
    """Return document IDs containing all specified terms."""
    if not terms:
        return set()
    result = search_term(index, terms[0]).copy()
    for term in terms[1:]:
        result = result.intersection(search_term(index, term))
    return result

def search_or(index: Dict[str, Set[int]], terms: List[str]) -> Set[int]:
    """Return document IDs containing at least one specified term."""
    result: Set[int] = set()
    for term in terms:
        result = result.union(search_term(index, term))
    return result

def search_not(index: Dict[str, Set[int]], all_docs: Set[int],
               include_terms: List[str], exclude_terms: List[str]) -> Set[int]:
    """Return document IDs matching include_terms but excluding exclude_terms."""
    base = search_and(index, include_terms) if include_terms else all_docs.copy()
    exclude = search_or(index, exclude_terms)
    return base.difference(exclude)

all_ids = set(corpus.keys())
print("AND ('search', 'engines'):", sorted(search_and(basic_index, ["search", "engines"])))
print("OR  ('ranking', 'crawlers'):", sorted(search_or(basic_index, ["ranking", "crawlers"])))
print("NOT ('pages' NOT 'crawlers'):", sorted(search_not(basic_index, all_ids, ["pages"], ["crawlers"])))

Running these boolean queries returns the appropriate document sets. Each operation combines candidate lists according to standard set algebra:

AND ('search', 'engines'): [2, 5]
OR  ('ranking', 'crawlers'): [1, 3, 4]
NOT ('pages' NOT 'crawlers'): [2, 4]

The AND query finds documents containing both terms, while the OR query aggregates documents containing either term. Finally, the NOT query filters out documents 1 and 3 because they contain the word crawlers.

Step 6: store positions

While set-based indexes handle boolean retrieval, they cannot support phrase searches like "web pages". To verify that words appear next to each other in exact order, the index must record the numerical word position of every occurrence.

# term -> {doc_id: [position_0, position_1, ...]}
positional_index: Dict[str, Dict[int, List[int]]] = defaultdict(dict)

for doc_id, text in corpus.items():
    tokens = tokenize(text)
    for position, token in enumerate(tokens):
        if doc_id not in positional_index[token]:
            positional_index[token][doc_id] = []
        positional_index[token][doc_id].append(position)

print("Positions for 'web' in Doc 1: ", positional_index["web"][1])
print("Positions for 'pages' in Doc 1:", positional_index["pages"][1])

The output reveals exact token offsets within the document. In Document 1, web appears at position 4 and pages appears immediately after at position 5:

Positions for 'web' in Doc 1:  [4]
Positions for 'pages' in Doc 1: [5]

In Document 1, web appears at position 4 and pages appears at position 5. Because $5 - 4 = 1$, the words occur consecutively.

Step 7: phrase queries

With positional data recorded, we can evaluate multi-word phrase queries. A phrase query first identifies candidate documents that contain all query terms using boolean AND logic, then inspects position arrays to verify that terms appear consecutively.

def search_phrase(pos_index: Dict[str, Dict[int, List[int]]], phrase: str) -> Set[int]:
    """Return document IDs where terms appear in exact consecutive sequence."""
    tokens = tokenize(phrase)
    if not tokens:
        return set()
    if len(tokens) == 1:
        return set(pos_index.get(tokens[0], {}).keys())

    # Candidate documents must contain all phrase terms
    candidate_docs = set(pos_index.get(tokens[0], {}).keys())
    for token in tokens[1:]:
        candidate_docs = candidate_docs.intersection(set(pos_index.get(token, {}).keys()))

    matching_docs: Set[int] = set()

    for doc_id in candidate_docs:
        # Check every starting position of the first term
        first_positions = pos_index[tokens[0]][doc_id]
        for start_pos in first_positions:
            match = True
            for offset, next_token in enumerate(tokens[1:], start=1):
                expected_pos = start_pos + offset
                if expected_pos not in pos_index[next_token][doc_id]:
                    match = False
                    break
            if match:
                matching_docs.add(doc_id)
                break

    return matching_docs

print("Phrase 'web pages':    ", sorted(search_phrase(positional_index, "web pages")))
print("Phrase 'web documents':", sorted(search_phrase(positional_index, "web documents")))
print("Phrase 'pages web':    ", sorted(search_phrase(positional_index, "pages web")))

The phrase query execution output demonstrates precision across candidate documents. It confirms adjacency by evaluating positional gaps:

Phrase 'web pages':     [1, 2]
Phrase 'web documents': [5]
Phrase 'pages web':     []

The phrase "web pages" matches documents 1 and 2, while "pages web" returns an empty set because the words do not appear in that order. This positional verification eliminates false positive phrase matches across your corpus.

Step 8: save and load the index

An inverted index built entirely in volatile RAM is lost when the Python process exits. Writing the index and document store to disk allows your application to start instantly without re-parsing the entire corpus. We use the json module to serialize the dictionary into human-readable text.

def save_index(filepath: str, documents: Dict[int, str],
               index: Dict[str, Dict[int, List[int]]]) -> None:
    """Save the index and document store to a JSON file."""
    data = {"documents": documents, "index": index}
    with open(filepath, "w", encoding="utf-8") as f:
        json.dump(data, f, indent=2)

def load_index(filepath: str) -> tuple[Dict[int, str], Dict[str, Dict[int, List[int]]]]:
    """Load the index and document store from disk."""
    with open(filepath, "r", encoding="utf-8") as f:
        data = json.load(f)
    docs = {int(k): v for k, v in data["documents"].items()}
    loaded_idx = defaultdict(dict)
    for term, postings in data["index"].items():
        loaded_idx[term] = {int(doc_id): pos for doc_id, pos in postings.items()}
    return docs, loaded_idx

Serializing to JSON ensures that the data can be inspected or imported into other languages like JavaScript or Go. It also allows developers to verify index structures using standard command-line tools like jq.

The complete script

Here is the complete, self-contained Python script. You can save this code as search_engine.py and run it directly with Python 3.10 or later without any external dependencies.

#!/usr/bin/env python3
"""
A complete, standalone positional inverted index implementation in pure Python.
Requires Python 3.10+ and standard library only.
"""

import re
import json
from collections import defaultdict
from typing import Dict, List, Set


def tokenize(text: str) -> List[str]:
    """Tokenize and normalize text into lowercase alphanumeric tokens."""
    return re.findall(r"\b[a-z0-9]+\b", text.lower())


class InvertedIndex:
    def __init__(self):
        # term -> {doc_id: [positions]}
        self.index: Dict[str, Dict[int, List[int]]] = defaultdict(dict)
        # doc_id -> raw document text
        self.documents: Dict[int, str] = {}

    def add_document(self, doc_id: int, text: str) -> None:
        """Add a document to the index, tracking token positions."""
        self.documents[doc_id] = text
        tokens = tokenize(text)
        for position, token in enumerate(tokens):
            if doc_id not in self.index[token]:
                self.index[token][doc_id] = []
            self.index[token][doc_id].append(position)

    def search_term(self, term: str) -> Set[int]:
        """Return the set of document IDs containing a single term."""
        tokens = tokenize(term)
        if not tokens:
            return set()
        clean_term = tokens[0]
        return set(self.index.get(clean_term, {}).keys())

    def search_and(self, terms: List[str]) -> Set[int]:
        """Return document IDs containing all specified terms."""
        if not terms:
            return set()
        result = self.search_term(terms[0])
        for term in terms[1:]:
            result = result.intersection(self.search_term(term))
        return result

    def search_or(self, terms: List[str]) -> Set[int]:
        """Return document IDs containing at least one specified term."""
        result: Set[int] = set()
        for term in terms:
            result = result.union(self.search_term(term))
        return result

    def search_not(self, include_terms: List[str], exclude_terms: List[str]) -> Set[int]:
        """Return document IDs matching include_terms but lacking exclude_terms."""
        base_set = self.search_and(include_terms) if include_terms else set(self.documents.keys())
        exclude_set = self.search_or(exclude_terms)
        return base_set.difference(exclude_set)

    def search_phrase(self, phrase: str) -> Set[int]:
        """Return document IDs where terms appear in exact consecutive order."""
        tokens = tokenize(phrase)
        if not tokens:
            return set()
        if len(tokens) == 1:
            return self.search_term(tokens[0])

        candidate_docs = self.search_and(tokens)
        matching_docs: Set[int] = set()

        for doc_id in candidate_docs:
            first_positions = self.index[tokens[0]][doc_id]
            for start_pos in first_positions:
                match = True
                for offset, next_token in enumerate(tokens[1:], start=1):
                    expected_pos = start_pos + offset
                    if expected_pos not in self.index[next_token][doc_id]:
                        match = False
                        break
                if match:
                    matching_docs.add(doc_id)
                    break

        return matching_docs

    def save_json(self, filepath: str) -> None:
        """Save the inverted index to disk in JSON format."""
        data = {
            "documents": self.documents,
            "index": self.index
        }
        with open(filepath, "w", encoding="utf-8") as f:
            json.dump(data, f, indent=2)

    @classmethod
    def load_json(cls, filepath: str) -> "InvertedIndex":
        """Load an inverted index from disk."""
        instance = cls()
        with open(filepath, "r", encoding="utf-8") as f:
            data = json.load(f)
        instance.documents = {int(k): v for k, v in data["documents"].items()}
        instance.index = defaultdict(dict)
        for term, postings in data["index"].items():
            instance.index[term] = {int(doc_id): pos_list for doc_id, pos_list in postings.items()}
        return instance


if __name__ == "__main__":
    corpus = {
        1: "Crawlers discover links on web pages.",
        2: "Search engines index web pages.",
        3: "Crawlers request pages and follow links.",
        4: "Ranking algorithms score indexed pages.",
        5: "Search engines rank relevant web documents."
    }

    idx = InvertedIndex()
    for doc_id, text in corpus.items():
        idx.add_document(doc_id, text)

    print("Single term 'crawlers':", sorted(idx.search_term("crawlers")))
    print("Boolean AND 'search', 'engines':", sorted(idx.search_and(["search", "engines"])))
    print("Boolean OR 'ranking', 'crawlers':", sorted(idx.search_or(["ranking", "crawlers"])))
    print("Boolean NOT 'pages' NOT 'crawlers':", sorted(idx.search_not(["pages"], ["crawlers"])))
    print("Phrase 'web pages':", sorted(idx.search_phrase("web pages")))
    print("Phrase 'web documents':", sorted(idx.search_phrase("web documents")))
    print("Phrase 'engines rank':", sorted(idx.search_phrase("engines rank")))

    idx.save_json("search_index.json")
    loaded_idx = InvertedIndex.load_json("search_index.json")
    print("Loaded phrase search:", sorted(loaded_idx.search_phrase("web pages")))

What this does not do

While our Python implementation delivers working boolean and phrase retrieval, commercial search engines incorporate significant engineering layers that this tutorial intentionally omits. Understanding these limitations clarifies the difference between educational prototypes and industrial search platforms.

First, this implementation performs matching rather than ranking. It returns boolean sets of matching document IDs without ordering them by relevance. Adding a ranking function like BM25 requires calculating term frequencies and document lengths. You can study the mathematical principles behind relevance ordering in our guide on how search engines rank pages.

Second, the index resides entirely in memory. Storing document IDs and positions in Python dictionaries consumes substantial RAM. When collections exceed several gigabytes, production engines like Apache Lucene write immutable disk segments using variable-byte integer compression and memory-mapped files.

Third, the tokenizer lacks linguistic stemming and synonym expansion. A search for crawler will not match crawlers because the strings differ. Addressing this requires integrating stemming algorithms like the Porter Stemmer or lemmatizers during the tokenization stage.

Fourth, this script has no typo tolerance or fuzzy matching. If a user types serach instead of search, our dictionary lookup fails immediately. Commercial search engines implement trigram indexes and Levenshtein distance calculations to suggest spelling corrections.

Where to take it next

Now that you have constructed a functional inverted index, you can expand this foundation into a full-featured search engine. Continue your implementation journey by visiting our dedicated search engine development hub. From there, you can learn how to build an autonomous web crawler, implement BM25 relevance ranking, or integrate vector embeddings for semantic search. To explore our broader curriculum of search engine engineering guides, return to the Search Engine Basics homepage.

Frequently asked questions

How many documents can this handle?

This in-memory Python implementation can comfortably index tens of thousands of typical web documents before exhausting system memory. Because it holds both the term dictionary and document store in RAM, memory consumption scales with corpus size. Handling millions of documents requires transitioning from in-memory dictionaries to disk-backed index segments and delta compression.

Why not just use a database?

Relational databases require full-table scans to find arbitrary substrings within unstructured text fields, which becomes excessively slow as table rows grow into millions. An inverted index isolates vocabulary terms as primary lookup keys, enabling instant hash lookups. Inverted indexes also store word positions necessary for phrase queries and proximity scoring.

Do I need NLTK or spaCy for this?

You do not need third-party natural language processing libraries to build a functioning inverted index. Python standard library regular expressions handle basic word tokenization, casing normalization, and punctuation removal efficiently. While libraries like NLTK or spaCy provide advanced lemmatizers and part-of-speech taggers, they add dependency overhead that is unnecessary for understanding core retrieval.

How do I add stemming?

You can add stemming by passing extracted tokens through an algorithm like the Porter Stemmer before inserting them into the index. Stemming strips suffixes so that running and runs map to run. If you use a stemmer during index construction, you must apply the identical stemmer to all user search queries before lookup.

How is this different from what Elasticsearch does?

Elasticsearch is a distributed, production-grade search server built on Apache Lucene. While it uses the same inverted index principles implemented here, Elasticsearch partitions indexes across multi-node server clusters, writes immutable segment files, and compresses postings using delta bit-packing. It also provides automatic failover, real-time replication, and REST APIs for enterprise scale.

How do I rank the results instead of just matching?

To rank matching documents by relevance, implement a scoring algorithm like BM25 or TF-IDF. Instead of returning raw sets of document IDs, compute a numerical relevance score for each candidate document based on term frequency, inverse document frequency, and document length. Sort the candidates in descending order based on their calculated scores.

Should I store the index as JSON or pickle?

JSON is ideal for educational projects because it creates human-readable, cross-platform files that you can inspect in any text editor. Python pickle provides faster binary serialization for native objects, but pickled files cannot be read by other programming languages and pose severe security vulnerabilities if loading untrusted files from external networks.

Can I use this for a real website search?

You can use this implementation for small personal blogs, static documentation sites, or local desktop applications containing several thousand pages. However, for public production websites with high traffic, specialized client-side libraries like Pagefind or server-based engines like Meilisearch provide optimized WebAssembly runtimes, instant typo tolerance, and superior snippet highlighting.