first need to understand topics.

hashmap just a data structure - key -> value mapping - hash function - converting hash -> array index - O(1) average lookup - hash collisions and basic collision handling is done - insert / lookup / delete are ops performed - resizing / rehashing can also be done

so like search engines use hash map for mapping like for inverted index:

word -> document containing that word

ex: “python” –> [doc1, doc21, doc8] “dodo” –> [doc6, doc82, doc100]

basic file i/o and text encoding just input and output. input -> read data from somewhere output -> write data somewhere

in python we can do:

with open("something.txt", "r") as file:
    text = file.read()

print(text)

here, - open(): opens the file - "r": means read mode - read(): gets its contents - text : a python string

and for writing we can do:

with open("something.txt", "w") as file:
    file.write("foo foo foo")

some common modes to use are: - “r” -> read - “w” -> write (this one overwrites) - “a” -> append - “rb” -> read binary - “wb” -> write binary

for search engine we will usually just encounter “r” and “rb” initially

but but but. what actually exists in a file? a file ultimately stores bytes, not characters.

for example, ‘Hello’ in a file, is stored as bytes. we can see this in python using:

with open("document.txt", "rb") as file:
    data = file.read()

print(data)

in the output, we can see b'Hello'… here, the ‘b’ means you’re looking at bytes.

but we dont want bytes though. we want the string i.e. “Hello” itself. for this, we need encoding/decoding.

what is unicode? unicode is essentially a standard, someone defined, that assigns a unique number/code point to characters from different writing systems. so it is unique for every character.

example:

A → U+0041
B → U+0042
अ → U+0905
😀 → U+1F600

so unicode just says “which character are we talking about”

and also, unicode supports characters from ALL commonly used writing systems, symbols, emoji. but the characters as we saw in our previous ‘Hello’ example, those characters are not necessarily stored as bytes. this is where something called UTF-8 comes in.

UTF-8 is an encoding which converts unicode characters into bytes.

so:

unicode character –> UTF-8 –> bytes

example:

"A" --> UTF-8 --> 0x41

also, some characters might need multiple bytes.

A  --> 1 byte
अ  --> 3 bytes
😀  --> 4 bytes

so this is why a file containing english text, and a file containing maybe hindi/arabic/japanese/chinesse text can all be stored using utf-8.

so encoding and decoding. encoding means: string -> encode() -> bytes

in python:

text = "hello"
data = text.encode("utf-8")

and decoding means its opposite: bytes -> decode() -> string

in python:

data = b"hello"
text = data.decode("utf-8")

why do we need to understand this for building a search engine?

lets say we have a document.txt, and its contents are:

python is easy
python is used in machine learning

so our search engine might need to do something like:

document.txt –> read bytes –> decode utf-8 –> “python is easy..... –> tokenise –> [“python”, “is”, “easy”] –> inverted index –> X

X here would have: “python” –> [document1, document2…] “is” –> [document 4, document23…]

so essentially an inverted index.

tokenisation

next thing to understand is, tokenisation. it is just a name given to the process of breaking text into smaller searchable units called tokens, usually words.

example: if u have a sentence lets say “python is easy to learn”. it would be tokenised into something like: [“python”, “is”, “easy”, “to”, “learn”]

in pythoon we can just:

text = "python is easy to learn."
tokens = text.split()

print(tokens)

so it is just: converting raw text –> individual searchable tokens

normalisation

it means converting tokens into a consistent form. it is so that equivalent text is treated the same during search.

so it has 2 steps: 1. lowercasing: Python –> python 2. removing punctuation: hello! -> hello

an example of this would be something like:

“Python is great!” –> “python is great” –> [“python”, “is”, “great”]

in python we can do something like:

import string #to perform ops on strings

# read the data and put in 'data' variable as it is
with open("document.txt", "r") as file:
data = file.read()

print("our original text read from file: " + data)
print("----------------------")

# lowercase our text
text = data.lower()
print("step 01: lowercase text: " + text)

# remove punctuation from our text
punctuation = string.punctuation # this gets all punc. chars
print("step 02: got punctuation chars using string.punctuation: " + punctuation)
table = str.maketrans("", "", punctuation) # just creates a table to tell python to remove those chars
text = text.translate(table)

# tokenise
print("step 03: text after normalisation: " + text)
tokens = text.split() #split at spaces

print("step 04: after tokenisation: ")
print(tokens)

stop word removal

removing very common words that usually add little meaning to a search ex: the, is, a, an, of, to, in, etc.

so example: “python is a programming language” –> “python programming language”

why do we do this? cus it reduces index size and also unnecessary processing

so to revise, our pipeline would be like:

tokenise –> normalise –> stop word removal; –> inverted index

these days, modern search engines dont always remove stop words; sometimes they keep them cus they can affect meaning. (https://opensourceconnections.com/blog/2023/01/24/10-reasons-why-you-shouldnt-remove-stop-words/)

if need be, it can be done in python liek this:

stop_words = {"the", "is", "a", "an", "of", "to", "in"}
tokens = ["python", "is", "a", "programming", "language"]

new_tokens = [] # empty to store non-stopwords
for word in tokens: # for every word in our tokens
    if word not in stop_words: # if our word is not a stop word, 
        new_tokens.append(word) # append that word to new list

tokens = new_tokens
print(tokens)

stemming/lemmatisation: both of these reduce words to a common/base form. this is doe so that related words can match during a search.

1. stemming: crudely cuts the word down. “running” –> “run” “played” –> “play” “studies” –> “studi” it can produce words that are NOT real words.

2. lemmatisation: finds the actual linguistic base word. “running” –> run “better” –> good “studies” –> study

so, stemming is usually faster and simpler, but less accurate. whereas lemmatisation is slower but has high accuracy.

inverted index

before understanding inverted index, lets understand how naive search works. so there are two main things in a naive search : 1. corpus (set of documents) 2. search query (ex: “fish”) these are inputs. naive lookup would be:

example corpus:

1. So long and thanks for the fish. 
2. Nobody loves a pig wearing lipstick on the wall. 
3. Garlic ice cream was her favorite. 
4. The door slammed on the watermelon. 
5. Fish is climbing up the wall. 

• linear search
• accumulate the docs where “fish” appears

so you just go through each line/document to see if the word ‘fish’ exists, if it does, just add it to the result set. then at the end from the result set u perform some sort of ranking and give the results.

problem? toooooo slow. linear scan. check ALL documents. 10 docs? ok fine. 100? umm fine i guess? 1000? 10,000? 100,000? 1,00,000? billions? trillions? lol

so inverted index kinda solves this. what is it?

it essentially stores a term -> list of documents (or document ids) where it is present.

example corpus again:

1. So long and thanks for the fish. 
2. Nobody loves a pig wearing lipstick on the wall. 
3. Garlic ice cream was her favorite. 
4. The door slammed on the watermelon. 
5. Fish is climbing up the wall. 

inverted index would be:

the ----- [1, 2, 4, 5]
fish ---- [1, 5]
wall ---- [2, 5]

this is the inverted index :) the list of all unique terms, is called a dictionary (so basically a vocabulary) and the list of all document ids is called a ‘posting list’.

how do we build an inverted index?

1. break the doc into words/tokens
2. lowercase, remove punctuation, stemming/lematisation
3. remove common words (stopwords)
4. for each term, update the posting list

example python implementation:

index = defaultdict(list)

for doc_id, text in enumerate(docs):
    for term in tokenise(text): # for every term in token list
        index[term].append(doc_id) # append with doc id

what is inside a posting list? tl;dr, just a list of document ids.

we can store more info also (if advanced search engine) - term frequency - how many times the term occurs in the doc - positions - where in the doc does the term appear (to answer proximity queries. ) - offsets - character/byte positions for highlighting

example :

fish -> [1:1:7:28, 5:1:1:0]

so 
1 and 5 -> document id
1 and 1 -> frequency
7 and 1 -> 7th word
28 and 0 -> offset

• ranking - tf-idf
• proximity queries - “fish is climbing”
• snippet generation and highlighting

now, how does the lookup work? lets make a very very very * 1000 simple implementaion of a search engine.

assume query -> “fish AND wall”

what happens? 1. fetch posting lists for “fish” and “wall”

fish -- [1, 5]
wall -- [2, 5]

2. set intersection to get docs that have both.
   1. apply boolean algebra:
      1. OR
      2. NOT
      3. etc.
   2. other techniques with relaxed constraint

optimisations :

• keep posting list sorted – faster merges
  • merge of two sorted lists (O(n). unsorted would be worse. so keep in order)
• compression
  • delta encoding, varints
• tiered index
  • keep top-n in memory (most important / higher quality / higher hits docs first) lookups will be faster (refer champion list)
  • rest all on the disk
• a lot more ex: bi-word, positional, etc. just gpt

boolean retrieval for a basic boolean retrieval model, we can use three main operators for retrieving docs, from the inverted index.

let us assume we have corpus as :

python → [doc1, doc2, doc4]
java   → [doc2, doc3, doc5]

1. AND would mean ‘python AND java’ so documents containing both terms. so an intersection. so doc2.

2. OR would mean ‘python OR java’ means documents that contain either of them. a union then. for this example, it would result in doc1, doc2, doc3, doc4, doc5.

3. NOT would mean ‘python AND NOT java’ this means docs contain ‘python’ but not ‘java’ so since python exists in doc1, 2, 4. out of these which doc does not have java? doc1, doc4. thats it.

important: boolean retrieval operates directly on the posting lists using set operations: AND → intersection (∩) OR → union (∪) NOT → difference (−)

so pipeline would look something like: query –> boolean operators –> posting lists –> set operations –> matching documents

tf and df

term frequency and document frequency just measures how important (or) common a term is in a collection of docs.

1. term freq. - how many times a term appears in one particular document. example: doc1: “python is easy. python is powerful” . we can see that the word ‘python’ appears 2 times. so it can be represented as : TF(python, doc1) = 2 so TF is document specific.

2. doc freq. - how many different documents contain the term. assume:

   doc1 -> python doc2 -> python doc3 -> java doc4 -> python . then, DF(python) = 3 and DF(java) = 1. NOTE : DF counts documents. not occurences.

   if: doc1 → “python python python” doc2 → “python” then DF(python) = 2, not 4.

we will use these terms to understand an algorithm named TF-IDF

TF-IDF

references:

https://www.freecodecamp.org/news/what-is-a-hash-map/ https://en.wikipedia.org/wiki/Hash_table https://www.kaggle.com/code/kavyasreeb/stop-word-removal https://en.wikipedia.org/wiki/Unicode https://www.ibm.com/think/topics/tokenization https://youtu.be/JpxCt3kvbLk?si=N3Z5mGWrfBonHQHp https://www.youtube.com/watch?v=iHHqnyThrqE