Before smart search engines, people used a command called Grep.
It searched every word in every file. Line by line. Word by word for information retrieval. It was slow.
As data grew, Grep couldnโt keep up. We needed a faster way.
Thatโs where the Inverted Index came in.
๐๐ก๐๐ญ ๐ข๐ฌ ๐๐ง ๐๐ง๐ฏ๐๐ซ๐ญ๐๐ ๐๐ง๐๐๐ฑ?
An inverted index is a list that tells you which words appear in which documents.
Instead of reading every document to find a word, you start with the word and go directly to the documents that contain it.
๐๐ญ ๐ก๐๐ฌ ๐ญ๐ฐ๐จ ๐ฉ๐๐ซ๐ญ๐ฌ:
๐๐ก๐ ๐๐ข๐๐ญ๐ข๐จ๐ง๐๐ซ๐ฒ โ a list of all the words
๐๐ก๐ ๐๐จ๐ฌ๐ญ๐ข๐ง๐ ๐ฌ ๐๐ข๐ฌ๐ญ โ where each word appears
Letโs see how itโs created.
๐๐ญ๐๐ฉ ๐: ๐๐จ๐ฅ๐ฅ๐๐๐ญ ๐๐จ๐๐ฎ๐ฆ๐๐ง๐ญ๐ฌ
We start with some text. For example:
๐๐จ๐ ๐: I did enact Julius Caesar. Brutus killed me.
๐๐จ๐ ๐: So let it be with Caesar. The noble Brutus told you Caesar was ambitious.
๐๐ญ๐๐ฉ ๐: ๐๐จ๐ค๐๐ง๐ข๐ณ๐๐ญ๐ข๐จ๐ง
We break the text into words (called tokens):
๐๐จ๐ ๐ ๐๐จ๐ค๐๐ง๐ฌ: I, did, enact, Julius, Caesar, Brutus, killed, me
๐๐จ๐ ๐ ๐๐จ๐ค๐๐ง๐ฌ: So, let, it, be, with, Caesar, noble, Brutus, told, you, ambitious
๐๐ญ๐๐ฉ ๐: ๐๐จ๐ซ๐ฆ๐๐ฅ๐ข๐ณ๐๐ญ๐ข๐จ๐ง
We clean the words:
โ Convert to lowercase
โ Remove punctuation
โ Sometimes, simplify words (like โkillingโ โ โkillโ)
Now we have:
brutus, caesar, kill, noble, tell, ambitious...
๐๐ญ๐๐ฉ ๐: ๐๐ฌ๐ฌ๐ข๐ ๐ง ๐๐จ๐๐ฎ๐ฆ๐๐ง๐ญ ๐๐๐ฌ
We give each document a number:
Doc 1 โ 1
Doc 2 โ 2
๐๐ญ๐๐ฉ ๐: ๐๐๐ค๐ ๐๐จ๐ซ๐โ๐๐จ๐ ๐๐๐ข๐ซ๐ฌ
We link each word to its document:
(โbrutusโ, 1)
(โcaesarโ, 1)
(โkilledโ, 1)
(โbrutusโ, 2)
(โcaesarโ, 2)
(โambitiousโ, 2)
๐๐ญ๐๐ฉ ๐: ๐๐จ๐ซ๐ญ ๐ญ๐ก๐ ๐๐จ๐ซ๐๐ฌ
Now we sort them by word (Alphabetically):
(โambitiousโ, 2)
(โbrutusโ, 1)
(โbrutusโ, 2)
(โcaesarโ, 1)
(โcaesarโ, 2)
โฆ
๐๐ญ๐๐ฉ ๐: ๐๐ซ๐จ๐ฎ๐ฉ ๐๐ฒ ๐๐จ๐ซ๐
We group the documents for each word:
ambitious โ [2]
brutus โ [1, 2]
caesar โ [1, 2]
This is the postings list.
๐๐ญ๐๐ฉ ๐: ๐๐ฎ๐ข๐ฅ๐ ๐ญ๐ก๐ ๐๐ง๐ฏ๐๐ซ๐ญ๐๐ ๐๐ง๐๐๐ฑ
We now have:
๐๐ข๐๐ญ๐ข๐จ๐ง๐๐ซ๐ฒ:
ambitious, brutus, caesar...
๐๐จ๐ฌ๐ญ๐ข๐ง๐ ๐ฌ:
ambitious โ [2]
brutus โ [1, 2]
caesar โ [1, 2]
๐๐จ๐ฐ ๐๐ญโ๐ฌ ๐๐ญ๐จ๐ซ๐๐
The dictionary stays in memory (itโs small).
The postings lists are stored on disk (theyโre bigger).
We can use lists or arrays to save space and improve speed.
๐๐๐ง๐๐๐ข๐ญ๐ฌ
โ Inverted index makes search fast.
โ We no longer check every document.
โ We go straight to the ones that matter.
๐๐๐๐จ ๐๐จ ๐๐ค๐ฌ ๐จ๐๐๐ง๐๐ ๐๐ฃ๐๐๐ฃ๐๐จ, ๐ก๐๐ ๐ ๐๐ค๐ค๐๐ก๐, ๐ฌ๐ค๐ง๐ ๐๐๐๐๐ฃ๐ ๐ฉ๐๐ ๐จ๐๐๐ฃ๐๐จ.
Want to understand SEO instead of imitating? ๐ฟ๐ค ๐๐ค๐ก๐ก๐ค๐ฌ!
SemanticSEO InformationRetrieval Indexing
This post was originally shared by on Linkedin.