Building a Search Engine

simple-search-engine.md

Simple Search Engine

You provide:

• Data (data) as an array of items (item)
• Key generator function (keygen): A pure function that, given an item from data, returns a deterministic key as a string.
• Tokenizer (tokenizer): A pure function that, given an item from data, returns a list of tokens (strings) describing that item.

What the search engine does when created:

• For each item, invokes keygen and tokenizer to build a forward index
• Performs an iterative key-value swap transformation to create an inverted index

How it's used:

Given a query (like the string you'd enter into google), the keys of the inverted index can be scanned for possible matches. The values of any matching keys are then cross-referenced via the forward index to get the matching items, which are your search results.

Types:

type Keygen<T> = (item: T) => string;

type Tokenizer<T> = (item: T) => string[];

type InvertedIndex = { 
  [key: string]: string[];
};

type ForwardIndex = { 
  [token: string]: string[]; 
};