Inverted Indexes: A Step-by-Step Implementation Guide

Summary

Before we start with the implementation, let's talk about why would you actually need an inverted index in a real life.Why would anyone need inverted index at allImagine you need to create a system that would quickly look up a document, given several words from it - something like a wiki search. Simplest option I can think of would be to scan through each document, marking ones that have all the necessary words. That might work at first, but such solution wouldn't scale, as each new document increases time to answer any query.Can we do something better? Actually, we can! If user wants to search by words - then words should be keys in our "database" (index). What would the values be in that case? Document ids, or any other unique references / pointers, that contain this word.How inverted indexes workImagine we have documents like:id: 1; Text: “In a hole in the ground there lived a hobbit.”id: 2; Text: “The sky above the port was the color of television, tuned to a dead channel.”id: 3; Text: "Hobbits Are Amazing Creatures"In this case, our index would look something like that:{ "hobbit": [1, 3], "television": [2], "hole": [1], ... }Seems quite obvious how we got here, right? Now if user queries system for "hobbit" - we look up this key (in O(1) time), and return document 1 and 3. This structure also solves case when we need to do queries like NOT, AND and OR - we get sets of documents by each key, and then do usual set operations, like intersect in case of AND, or diff in case of NOT. Hence for query like "hobbit AND hole" we will look up sets [1, 3] and [1], their intersection would be [1], and we would return document with id=1.Obviously all this is just a tip of the iceberg, the most naive implementation - real-word document indexing / querying systems could rank results based on relevance, do different sorts of fuzzy search, faceted search etc, but still, naive implementation is a great place to start.So - let's start, and implement it.ImplementationI would start ...