A small search engine with spelling correction
The problem
Build a search engine over a collection of short documents that corrects misspelled queries, ranks the results and shows the passage that matched.
Requirements
- Index at least 30 short documents, such as help pages or recipes, with an inverted index
- Rank documents for a query by TF-IDF cosine similarity
- Correct unknown query words with edit distance and word frequencies from the collection
- Show the top three results with a snippet in which the query words are marked
- Measure the ranking on at least 10 test queries with known relevant documents
Technologies
- Python
- Regular expressions
- Inverted index
- TF-IDF
- Edit distance
Step by step
- Write or collect the documents and a list of test queries with the documents they should find.
- Build the tokenizer, the inverted index and the TF-IDF vectors.
- Implement ranking and check it on the test queries.
- Add spelling correction for query words that are not in the vocabulary.
- Add snippets: find the sentence with the most query words and mark them.
- Measure how often the right document is in the top three, before and after spelling correction.
Expected result
A command-line search tool that forgives typos and explains its results, with a measured hit rate.
How it is evaluated
- Queries with typos still find the right documents
- Rankings are reproducible because ties are broken in a fixed way
- The hit rate on the test queries is reported
- Indexing, ranking, correction and display are separate functions
Ways to improve it
- Rank with BM25 and compare it with TF-IDF
- Add co-occurrence or pretrained embeddings to match synonyms
- Pass the top passages to a language model to answer questions (retrieval-augmented generation)