liveBook · Manning

Inverted index

As explained in Build an Advanced RAG Application (From Scratch)

An inverted index is a lookup data structure that maps terms or tokens to identifiers of documents containing them.

An inverted index is a lookup structure that maps each term or token to the identifiers of documents containing it. Keyword search uses this reverse mapping to find matching documents without scanning every document's text. section 3.2

Build a basic inverted index by:

  • Starting with a collection of searchable text documents. section 3.2
  • Tokenizing each document into words or other meaningful chunks. section 3.2 section 3.2.1
  • Creating an empty mapping from tokens to document identifiers. section 3.2
  • Appending each document identifier to the list associated with every token it contains. section 3.2.1

Small Python index

For the sentences "Machine learning is based on algorithms" and "Deep learning uses neural networks", the index contains entries such as {'learning': [0, 1], 'neural': [1]}. A query can then retrieve candidate documents directly from the postings for its terms. section 3.2.1

The index supplies candidates for keyword search; TF-IDF can then score them. Term frequency counts occurrences in a document, while inverse document frequency uses the number of documents containing the term. section 3.2.1

Keyword query ranking

For the query "machine learning", the sample search tokenizes the query, accumulates TF-IDF scores for documents found through the index, and ranks the results. "Machine learning is based on algorithms" ranks first with a score of 1.791759469228055.

How Build an Advanced RAG Application (From Scratch) covers it

How deep it goes
Explains tokenization, index construction, TF-IDF scoring, and ranking through incremental Python examples.
Examples
Uses toy sentences, token lists, printed index mappings, and a machine-learning query with ranked results.
What it assumes
Assumes basic text documents and token concepts while teaching index construction and scoring from first principles.
What you can do after
Build a basic Python inverted index and use it with TF-IDF to rank keyword-search results.
How it connects
Connects keyword search with tokenization, TF-IDF, document retrieval, and ranking.

Also explained in

Compare how 6 books explain inverted index →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Build an Advanced RAG Application (From Scratch). The section links point to the parts of the book it draws on.