DEV Community: Mehmet Yüksel

Let's Implement Overloading/Multiple-Dispatch

Mehmet Yüksel — Tue, 20 Aug 2024 18:33:42 +0000

A couple years ago, I came across a language called Julia. It's multiple dispatch feature was very interesting; I wanted to know how it worked under the hood, but I didn't have the knowledge to do that yet. So here I am, finally giving it a try. Now that I have an implementation, I realized there is nothing tying this algorithm to runtime dispatch; I think it could be used in a language with static dispatch as well. If you're interested in learning about multiple dispatch, I left some links at the end of the post. So I guess this post is just about selecting the most specific function for a given set of arguments in a language with subtyping. Ok, let's get started.

Describing the Problem

I'm assuming you're familiar with the concept of subtyping and function overloading. For a brief explanation, subtyping is a way to relate types to each other. For example, if we have a type A and a type B and B is a subtype of A, we can say that B is an Aso we can use B anywhere we need an A. And function overloading is a way to define multiple functions with the same name but different arguments. The function that is called is the one that matches the arguments the "best".

Let's say we have a subtyping hierarchy like this:

abstract type Number
struct Complex <: Number
struct Real <: Complex

And function like this:

function foo(x::Number, y::Number)
    println("Number, Number")
end

function foo(x::Complex, y::Complex)
    println("Complex, Complex")
end

function foo(x::Real, y::Real)
    println("Real, Real")
end

We want to select the most specific function for the given arguments. For example, if we call it with foo(Real(), Real()) we call the last definition; if we call it with foo(Complex(), Number()) we call the first definition because we can't pass a Number where we need a Complex. The thing is, when we called foo(Real(), Real()) it would be totally fine to call the second definition; the code would work just fine. So we not only want to find a method that conforms to the arguments but also a way to rank them.

Modeling Subtyping

Let's start by modeling subtyping first. I want something like this:

any = Type.new("Any")
number = Type.new("Number", any)
complex = Type.new("Complex", number)
real = Type.new("Real", complex)
string = Type.new("String", any)

puts real.is?(number) # true
puts real.is?(complex) # true
puts real.is?(real) # true
puts real.is?(string) # false
puts real.is?(any) # true
puts string.is?(any) # true

All types are subtype of Any which has no supertype. This type is also called the top type. You'll notice that a type is a subtype of itself. Why? Well, if we return to the definition of subtyping, a type is a subtype of another if it can be used in place of the other. So if we have a function that takes a Real we can pass a Real to it. So Real is a subtype of Real. And Any is also a supertype of all types, which includes itself, which I think is quite nice.

We could implement this API like this:

class Type
  attr_reader :name, :supertype

  def initialize(name, supertype = nil)
    @name = name
    @supertype = supertype
  end

  def is?(type)
    return true if type == self
    return false if @supertype.nil?
    @supertype.is?(type)
  end

  def ==(type)
    @name == type.name
  end
end

We already talked about every type being a subtype of itself, so first return statements do that check. The second one accounts for the case where we call any.is?(real). The third return statement recursively traverses the subtyping hierarchy to find if type is in there.
I also overrode the == method to have value equality.

Modeling Function Signatures

A signature is just a list of types.

class Signature
  attr_reader :types

  def initialize(types)
    @types = types
  end

  def ==(signature)
    @types == signature.types
  end
end

We need a way to know if it is legal to call a signature with a given list of argument types. Let's look at a simple case:

function f(x::Real) end

We obviously shouldn't be able to call this function with f(Complex()) because Complex is not a subtype of Real.
This generalizes to multiple arguments as well. We should be able to call f(Real(), Real()) but not f(Complex(), Real()) which I mentioned before. There is nothing that makes the first argument special. So the gist of it is, we should be able to call a function with a list of types (t1, t2, ..., tn) where the signature of the function is (s1, s2, ..., sn) if every t is a subtype of the corresponding type s.
The implementation is quite simple:

class Signature
  # Other stuff...

  def conforms?(signature)
    # for a signature to conform to this one:
    # 1. it must have the same number of types
    return false if signature.types.length != @types.length
    # 2. each type must be a subtype of the corresponding type in this signature
    @types.zip(signature.types).all? { |a, b| a.is?(b) }
  end
end

Ranking Conforming Signatures

Now we come to the meat of the problem. How do we select the most specific function for a given list of argument types? We need a way to rank them. Let's look at the simplest case again.

function f(x::Number) end
function f(x::Complex) end
f(Real())

If I asked you which function should be called, you would say the second one, right? Why? Well, when we consider the subtype hierarchy Real <: Complex <: Number <: Any, the closest to type Real is Complex so you choose that. This is the main idea behind the ranking algorithm. We need to find the closest type to the given type in the signature.
We need a way to get the distance from the given type:

class Type
  # Other stuff...

  def distance(type)
    # We only want to consider the chain not the tree so we don't consider types from different branches. e.g. Real and String
    raise "Not a subtype" unless is?(type)
    # If we are at the same type, we are 0 distance away
    return 0 if self == type
    # We are whatever distance `type` away from our supertype + 1.
    # Example:
    #   real.distance(any) = 1 + complex.distance(any)
    #                      = 1 + 1 + number.distance(any)
    #                      = 1 + 1 + 1 + any.distance(any)
    #                      = 1 + 1 + 1 + 0
    #                      = 3
    1 + @supertype.distance(type)
  end
end

We can already rank functions with a single argument with this. One way to generalize this to multiple arguments is to find the distance between each corresponding type between signature type and argument type and sum them up.

class Signature
  # Other stuff...

  def distance(signature)
    @types.zip(signature.types).sum { |a, b| a.distance(b) }
  end
end

If you're a bit interested in math, this is a metric. A signature is like an n-dimensional point, and the distance between two points is the sum of the distances between each corresponding scalar(type) in the point. Honestly, you can even use Euclidean distance if you want, but I think this metric suffices. What we're using here is called Manhattan distance by the way.

If we put this to work:

any = Type.new("Any")
number = Type.new("Number", any)
complex = Type.new("Complex", number)
real = Type.new("Real", complex)

f1 = Signature.new([number, number])
f2 = Signature.new([complex, complex])
f3 = Signature.new([real, real])

call_signature = Signature.new([real, real])
puts [f1, f2, f3].min_by { |f| call_signature.distance(f) } == f3 # true

A function isn't just a signature though, it also has a name.

class Function
  attr_accessor :name, :signature

  def initialize(name, signature)
    @name = name
    @signature = signature
  end

  def to_s
    "#{@name}#{@signature}"
  end

  def ==(other)
    @name == other.name && @signature == other.signature
  end
end

And we'll have a table of functions that contains all the definitions and gives the most specific one for a given call.

class FunctionTable
  attr_accessor :functions

  def initialize()
    @functions = []
  end

  def add(function)
    raise "Function already exists" if @functions.include?(function)
    @functions << function
  end

  def find(function)
    # find all the signatures that conform to the given signature.
    candidates = @functions.select { |m| function.signature.conforms?(m.signature) && m.name == function.name }
    # sort them by distance from closest to furthest.
    sorted_by_distance = candidates.sort_by { |m| function.signature.distance(m.signature) }

    # find the closest one.
    # There may be more than one with the same distance, so we find all of them.
    distances = sorted_by_distance.map { |m| function.signature.distance(m.signature) }
    min_distance = distances.min
    closest_functions = sorted_by_distance.select { |m| function.signature.distance(m.signature) == min_distance }
    raise "Ambiguous function call between #{closest_functions}" if closest_functions.length > 1
    closest_functions.first
  end
end

The most interesting method is find.

It finds all the functions with the same name and conforming signature.
Sorts them by distance.
Finds the closest one.
If there are more than one with the same distance, it raises an error. I choose to raise an error but one thing you could also do is return the return the second closest method(I wonder if there is a metric where two different point can't have the same distance from a different third point).

If we put it all together:

any = Type.new("Any")
number = Type.new("Number", any)
complex = Type.new("Complex", number)
real = Type.new("Real", complex)

f1 = Function.new("f", Signature.new([number, number]))
f2 = Function.new("f", Signature.new([complex, complex]))
f3 = Function.new("f", Signature.new([real, real]))

table = FunctionTable.new
table.add(f1)
table.add(f2)
table.add(f3)

call_signature = Signature.new([real, real])
puts table.find(Function.new("f", call_signature)) == f3 # true

Full Code

Search Engine From Scratch

Mehmet Yüksel — Sun, 11 Aug 2024 18:57:28 +0000

Let's define the problem at a high level first.

User enters a query.
The search engine returns the most relevant document (this could be an HTML, PDF, or any other textual content) given this query.

How do we define relevance? We can say relevance is low if none of the terms appear in the document; it's obvious this document is irrelevant.
On the other hand, we could say that this document is relevant if the terms occur with high frequency. Of course, this is not a binary category; it's a spectrum, but we'll talk about this when we implement the relevance/ranking algorithm.

Before trying to build a full-fledged search engine, though, let's start simple and build it from there. The first and simplest idea that comes to mind is to just use a searching the query inside the document.

document = "The quick brown fox jumps over the lazy dog."
query = "..." # comes from the user
is_relevant = document.include?(query)

This fails if the user enters "Quick" instead of "quick". We can solve this by converting both the document and the query to lowercase.

document = "The quick brown fox jumps over the lazy dog.".downcase
query = "...".downcase # comes from the user
is_relevant = document.include?(query)

This one fails if the user enters the words in the 'wrong' order, like "dog lazy". We can solve this by splitting the query into words and checking if all of them are present in the document.

is_relevant = query
  .split
  .all? { |word| document.include?(word) }

This one seems like it works, but if the document only contains some of the words in the query and not others, then it won't be considered relevant.
Instead of using all? we can use any? to check if any of the words in the query are present in the document.

is_relevant = query
  .split
  .any? { |word| document.include?(word) }

Until now, we used a binary classification of relevance. If there are a large number of relevant documents (as in the case of the web), there is no way of sorting them. It would be nice if we could give documents a ranking based on how relevant they are to the query. We can't do a qualitative analysis of the document; that may be done via an AI model, but we won't be using it here. Instead, we can use a quantitative one. We can calculate the count of each word of the query in the document and sum them up.

relevance = query
  .split
  .map { |word| document.scan(word).count }
  .sum

We split the query into words with query.split, then we map each word to the number of times it appears in the document with document.scan(word).count. Finally, we sum them up with sum.

This version has the disadvantage of scoring big documents higher than small ones just because they contain more words. We can solve this by dividing the sum by the number of words in the document, and we get the frequency of the word. This is called term frequency.

number_of_words = document.split.count
relevance = query
  .split
  .map { |word| document.scan(word).count }
  .sum / number_of_words.to_f

Not all words are created equal

As you already intuitively know, not all words have the same importance. You can remove some words and still understand the meaning of the sentence. For example, we can remove "the" from the sentence "The quick brown fox jumps over the lazy dog." and still understand the meaning. But if we remove "fox" then the meaning of the sentence changes. We can use this information to give more importance to some words than others. The words like "the", "a", "an" are called stop words, and we can remove them from the query by maintaining a list of them. But this only works if we're only dealing with English. We can do something else; not only do words like "the" have less importance, but they also appear very frequently. If you search for 'Most Common Words in English' you'll find that words like "the", "a" will occur most frequently. We can use this information to give less importance to words that appear more frequently in all documents. The basic formula is as follows:

word\frac{\text{number of documents}}{\text{number of documents containing the word}}

As the number of documents containing the word increases, that means this word is not that unique or specific, so the whole fraction decreases. However, the word may not appear in any document at all; that'll lead to a division by zero. We can solve this by adding 1 to the numerator and denominator.

1\frac{\text{number of documents}\ +\ 1}{\text{number of documents containing the word}\ +\ 1}

Why do we add +1 to the numerator? Because in the extreme case that the word appears in all documents, the old formula would give 1, we could preserve this behavior by adding 1 to the numerator as well. It's not that important, though; in the limit, this +1 doesn't matter.

To calculate the importance of a word, we can use this fraction along with the TF we calculated before.

def importance(word, documents)
  number_of_documents = documents.count
  number_of_documents_containing_word = documents.count { |document| document.include?(word) }
  (number_of_documents + 1) / (number_of_documents_containing_word + 1).to_f
end

def relevance(query, document, documents)
  number_of_words = document.split.count
  query
    .split
    .map { |word| document.scan(word).count * importance(word, documents) }
    .sum / number_of_words.to_f
end

I extracted the importance calculation into a separate function to make it more readable. We pass the documents to the importance function to calculate the number of documents. We can use this function to calculate the importance of each word in the query and multiply it by the term frequency to get the relevance of the document.

The importance formula is almost something called IDF(Inverse Document Frequency) but not exactly. IDF takes the logarithm of the fraction. Why? If the word occurs too frequently or too rarely, it can dominate the scores. Using a logarithm dampens this effect. We can use the logarithm of the fraction instead of the fraction itself.

def importance(word, documents)
  number_of_documents = documents.count
  # count how many times the word appears in the documents.
  number_of_documents_containing_word = documents.count { |document| document.include?(word) }
  Math.log((number_of_documents + 1) / (number_of_documents_containing_word + 1).to_f)
end

def relevance(query, document, documents)
  number_of_words = document.split.count
  query_words = query.split
  query_words
    .map { |word| document.scan(word).count * importance(word, documents) }
    .sum / number_of_words.to_f
end

Partial Queries

Up until now, we only worked with whole words. But what if the user enters a partial query like "tes"? I would want the search engine to match words like "test", "testing", "tested" etc. We can solve this by working on smaller terms than a word. We can use something called stemming. Stemming allows us to reduce a word to its root form. For example, the stem of "fishing", "fished" and "fisher" is "fish".

This would require us to do this for every language we want to support. And it's not like a document has to be in a single language. How do we know which substrings are of certain languages? There is a simpler and more general approach, albeit a worse one. It's called n-grams. Instead of writing down the textbook definition, let me give you a couple examples. Let's say we want to find all 2-grams of the word "quick". We start from the beginning, take all the two-letter substrings, and move to the right, like this:
"qu", "ui", "ic," and "ck". If we want to find the 3-grams, then we'll have "qui", "uic", "ick". It's sort of like a moving window.
We're going to modify this a little bit. Instead of moving the window to the right, we're going to extend it to the right. For example, for the word "quick", we'll have "qu", "qui", "quic", "quick". Do you see how this is useful? People remember words by their first letters, not by their middle or last letters, so even if the user didn't enter the full word, we can still match it. We can use this to generate all the n-grams of the query and the document and check if any of them match.

The average length of a root word in European languages is roughly 5. I'm assuming there wouldn't be single-letter words, so I'm going to use a window size between 2 and 5. I'm generating all the n-grams between 2 and 5, not just 2 or 5, because as the user enters more and more letters, the n-grams will change. For example, if the user enters "tes" we can match "test" but if the user enters "test" we can match "test" as well. We can generate all the n-grams of the query and the document and check if any of them match.

def n_grams(document, min_n: 2, max_n: 5)
  words = document.split
  # This will store the n-gram and the number of times it appears in the document.
  terms = []
  words.each do |word|
    # the word can be smaller than the max window size so we take the minimum.
    max_window_size = [max_n, word.length].min
    # for every window size take a substring and add it to the terms.
    (min_n..max_window_size).each do |window_size|
      terms << word[...window_size]
    end
  end
  terms
end

Since we changed the way we look at the smallest element of a document, we also need to change the way we defined relevance and importance methods.

def importance(term, documents)
  number_of_documents = documents.count
  number_of_documents_containing_term = documents.count { |document| n_grams(document).include?(term) }
  Math.log((number_of_documents + 1) / (number_of_documents_containing_term + 1).to_f)
end

def relevance(query, document, documents)
  number_of_terms = n_grams(document).count
  query_terms = n_grams(query)
  query_terms
    .map { |term| n_grams(document).count(term) * importance(term, documents) }
    .sum / number_of_terms.to_f
end

Not much has changed. Instead of using words, we're using terms/n-grams.

One last thing is to remove punctuation from the documents and the query. We can do this by using a regular expression. Luckily, Ruby has a very short way of doing this with a regex.

def clean(document)
  document.gsub(/[[:punct:]]/, " ")
end

Full Engine

Let's put the pieces together and build a full search engine.

The API could look like this:

search_engine = SearchEngine.new
search_engine.add_document("first_document", "Peter,\n\nI'm going to need those TPS reports on my desk first thing tomorrow! And clean up your desk!\n\nLumbergh")
search_engine.add_document("second_document", "Everyone,\n\nM-m-m-m-my red stapler has gone missing. H-h-has a-an-anyone seen it?\n\nMilton")
search_engine.add_document("third_document", "Peter,\n\nYeah, I'm going to need you to come in on Saturday. Don't forget those reports.\n\nLumbergh")

results = search_engine.search("tps repor")
puts results
<<-OUTPUT
[
  { :name => "first_document", :relevance => SCORE_1, :content => "Peter,\n\nI'm going to need those TPS reports on my desk first thing tomorrow! And clean up your desk!\n\nLumbergh" },
  { :name => "third_document",  :relevance => SCORE_2, :content => "Peter,\n\nYeah, I'm going to need you to come in on Saturday. Don't forget those reports.\n\nLumbergh" }
]
OUTPUT

where SCORE_1 should be higher than SCORE_2 and the documents should be sorted by relevance.

Here is the full implementation:

class SearchEngine
  def initialize
    @documents = []
  end

  def add_document(name, document)
    @documents << { name: name, content: clean(document) }
  end

  def search(query)
    document_contents = @documents.map { |document| document[:content] }
    @documents
      .map { |document| { name: document[:name], relevance: relevance(query, document[:content], document_contents), content: document[:content] } }
      .sort_by { |document| -document[:relevance] }
  end

  private

  def clean(document)
    document.gsub(/[[:punct:]]/, " ").downcase
  end

  def n_grams(document, min_n: 2, max_n: 5)
    words = document.split
    terms = []
    words.each do |word|
      # the word can be smaller than the max window size like the word 'and' so we take the minimum.
      max_window_size = [max_n, word.length].min
      (min_n..max_window_size).each do |window_size|
        terms << word[...window_size]
      end
    end
    terms
  end

  def importance(term, documents)
    number_of_documents = documents.count
    # `count` method can take a block and count the number of times the block returns true.
    number_of_documents_containing_term = documents.count { |document| n_grams(document).include?(term) }
    Math.log((number_of_documents + 1) / (number_of_documents_containing_term + 1).to_f)
  end

  def relevance(query, document, documents)
    # Instead of just using `.split` we generate the n-grams and work on that.
    number_of_terms = n_grams(document).count
    query_terms = n_grams(query)
    query_terms
      .map { |term| n_grams(document).count(term) * importance(term, documents) }
      .sum / number_of_terms.to_f
  end
end

Performance

How performant is this? The answer is not very. First of all, we're using a dynamically typed language like Ruby. Since there is a lot of processing of data, a systems programming language like C, Rust, or Zig will be an excellent choice. Another reason is that we process the documents for every different query. This may not be true in some cases, but most of the time, the documents we're searching in will largely stay the same or change much less frequently than the queries. What we can do is pre-process the documents and store the n-grams and the importance of each term. This way, we can just use the stored data and calculate the relevance of the query. This will make the search engine much faster.

Ok, how are we going to store this pre-processed data? The trick is to look at the relevance method.
number_of_terms = n_grams(document).count:
We need a mapping between documents and their number of terms. We can have a documents collection and store the number of terms for each document. This document could look like this:

{
  "_id": "first_document",
  "content": "Peter,\n\nI'm going to need those TPS reports on my desk first thing tomorrow! And clean up your desk!\n\nLumbergh",
  "number_of_terms": 20
}

In the web, _id would be the URL of the document, but here we're using a simple string. The database can index based on the _id field, so we can quickly access the document.

query_terms = n_grams(query):
We can't do much about this because the query is completely dynamic.

n_grams(document).count(term):
We need a mapping between terms and appearances. Since a term can appear in more than one document, we need to have another mapping between document names and the number of appearances of the term. This structure could look like this:

{
  "_id": "tes",
  "appearances": {
    "first_document": 2,
    "second_document": 0,
    "third_document": 1
  }
}

Here I'm using the term's name as the _id because it's unique.

importance(term, documents):
We can just add a another field to the above structure:

{
  "name": "tes",
  "appearances": {
    "first_document": 2,
    "second_document": 0,
    "third_document": 1
  },
+ "importance": 0.5
}

By the way, this is called an inverted index. You can read more about it on Wikipedia.

Let's put these into code. I'm going to use MongoDB because it's really easy to convert from these JSONy structures to MongoDB documents.

def initialize(url)
  @client = Mongo::Client.new(url)
end

initialize method is going to take a URL to connect to the MongoDB server.

def search(query)
  document_contents = @client[:documents].find.map { |document| document[:content] }
  @client[:documents]
    .find
    .map { |document| { name: document[:_id], relevance: relevance(query, document), content: document[:content] } }
    .sort_by { |document| -document[:relevance] }
    .reject { |document| document[:relevance] == 0 }
end

search is almost the same. We get the documents from database instead of an instance variable.

def add_document(name, document)
  document = clean(document)
  terms = n_grams(document)
  number_of_terms = terms.count
  @client[:documents].insert_one({ _id: name, content: document, number_of_terms: number_of_terms })
  terms.each do |term|
    @client[:terms].update_one(
      { _id: term },
      # Increment the count of this document by one.
      { "$inc": { "appearances.#{name}": 1 } },
      upsert: true,
    )
  end
end

Here after we save the document, for each term we increment the count of the document by one or set it to one if it doesn't exist.

def importance(term)
  appearances = @client[:terms].find(_id: term).first["appearances"]
  number_of_documents = @client[:documents].count
  number_of_documents_containing_term = appearances.count
  Math.log((number_of_documents + 1) / (number_of_documents_containing_term + 1).to_f)
end

Not much to say here. We don't have to search through the entire documents to find how many documents contain the term. We can just look at the appearances field's length.

def relevance(query, document)
  number_of_terms = @client[:documents].find(_id: document[:_id]).first["number_of_terms"]
  query_terms = n_grams(query)
  query_terms.map { |term| term_relevance(term, document[:_id]) }.sum / number_of_terms.to_f
end

def term_relevance(term, document_id)
  appearances = @client[:terms].find(_id: term).first["appearances"]
  number_of_terms = @client[:documents].find(_id: document_id).first["number_of_terms"]
  if appearances.nil? || appearances[document_id].nil?
    return 0
  end
  importance(term) * appearances[document_id]
end

relevance don't have to take the documents as an argument now; it can just look at the database. I refactored the block that calculates the relevance of a term into a separate method called term_relevance for readability. If the term doesn't appear in the document, we return 0; otherwise, we calculate the relevance as before by multiplying the importance by the number of appearances.

The full class looks like this:

require "mongo"

class SearchEngine
  def initialize(url)
    @client = Mongo::Client.new(url)
  end

  def add_document(name, document)
    document = clean(document)
    terms = n_grams(document)
    number_of_terms = terms.count
    @client[:documents].insert_one({ _id: name, content: document, number_of_terms: number_of_terms })
    terms.each do |term|
      @client[:terms].update_one(
        { _id: term },
        # Increment the count of this document by one.
        { "$inc": { "appearances.#{name}": 1 } },
        upsert: true,
      )
    end
  end

  def search(query)
    document_contents = @client[:documents].find.map { |document| document[:content] }
    @client[:documents]
      .find
      .map { |document| { name: document[:_id], relevance: relevance(query, document), content: document[:content] } }
      .sort_by { |document| -document[:relevance] }
      .reject { |document| document[:relevance] == 0 }
  end

  private

  def clean(document)
    document.gsub(/[[:punct:]]/, " ").downcase
  end

  def n_grams(document, min_n: 2, max_n: 5)
    words = document.split
    terms = []
    words.each do |word|
      # the word can be smaller than the max window size like the word 'and' so we take the minimum.
      max_window_size = [max_n, word.length].min
      (min_n..max_window_size).each do |window_size|
        terms << word[...window_size]
      end
    end
    terms
  end

  def importance(term)
    appearances = @client[:terms].find(_id: term).first["appearances"]
    number_of_documents = @client[:documents].count
    number_of_documents_containing_term = appearances.count
    Math.log((number_of_documents + 1) / (number_of_documents_containing_term + 1).to_f)
  end

  def relevance(query, document)
    number_of_terms = @client[:documents].find(_id: document[:_id]).first["number_of_terms"]
    query_terms = n_grams(query)
    query_terms.map { |term| term_relevance(term, document[:_id]) }.sum / number_of_terms.to_f
  end

  def term_relevance(term, document_id)
    appearances = @client[:terms].find(_id: term).first["appearances"]
    number_of_terms = @client[:documents].find(_id: document_id).first["number_of_terms"]
    if appearances.nil? || appearances[document_id].nil?
      return 0
    end
    importance(term) * appearances[document_id]
  end
end

Conclusion

If you want to go deeper into the rabbit-hole of search engines, you should look at BM25, PageRank, Word2Vec. Maybe a next step would be using AI models but I'm not sure if this improves the search experience. For last few years current search engines gets shittier everyday. Maybe it's not such a good idea.
Anyways I hope you enjoyed this article. If you have any suggestions, please let me know. I'm still new to documenting my thought process so any feedback is appreciated. Thanks for reading!

Inspiration

Building A Python-Based Search Engine. An excellent conference talk by Daniel Lindsley on building a search engine in Python. I'm heavily inspired by this talk. You can take a look at his source code here.
Search Engine in Rust by Tsoding.