Rank a retrieval baseline

Learn it

Words to know

retrieval

Finding the few documents, out of many, that can help answer a question.

baseline

The simplest working version, measured first, so that every later change can be compared with it.

lexical search

Search that matches the words themselves, not their meaning. It finds car only where the text says car.

embedding

A vector that a trained model produces for a piece of text. Texts with similar meaning get vectors that point in similar directions.

How it works

1. Turn a text into a set of words: make it lowercase, and take every run of the letters a to z as one word. A set holds each word once.
2. A document's score is how many of the query's words are in the document's set.
3. Drop documents with a score of 0.
4. Sort the rest from the highest score to the lowest. Documents with the same score keep the order they came in. Return the ids of the first k.

Worked example

Input
query = "vector search"
documents = [{ id: "a", text: "Search systems" }, { id: "b", text: "Vector search" }, { id: "c", text: "Cooking" }]
k = 2

Output
["b", "a"]

The query's words are vector and search. Sorted by score, b comes before a, and c is left out.

Why it matters

This is the search step of a document assistant. The first portfolio project starts from this ranking, measures it, and only then tries embeddings against the same questions.

Your turn

Rank documents by how many distinct words of the query they contain, and return the ids of the best k.

query

the question, as a string; it may be empty. A word is a run of the letters a to z, compared in lowercase

documents

a list of documents, each with a unique id and a text, both strings

k

the most ids to return; 0 or more

Returns

Up to k document ids, best score first. Equal scores keep the documents' original order. Documents that share no word with the query are left out.

Input
query = "vector search"
documents = [{ id: "a", text: "Search systems" }, { id: "b", text: "Vector search" }, { id: "c", text: "Cooking" }]
k = 2

Output
["b", "a"]

Input
query = "AI ai!"
documents = [{ id: "x", text: "ai ai" }, { id: "y", text: "AI" }]
k = 2

Output
["x", "y"]

Input
query = ""
documents = [{ id: "a", text: "hello" }]
k = 3

Output
[]

The checks also try

• k is 0
• only the best one
• repeated words in the query and in a document
• punctuation after a word
• a query word inside longer words
• punctuation at the end of both texts
• a capital letter in the query
• an apostrophe inside a word
• a digit attached to a word
• a long document with more shared words

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Where to start

   Write one small helper that turns a text into a set of lowercase words. You need it for the query and for every document.

2. Hint 2: The key step

   A document's score is the number of query words found in that document's set. Keep each score together with the document's id.

3. Hint 3: The outline

   Write a helper that lowercases a text and puts every run of the letters a to z in a set. For each document, count the query's words that are in the document's set; if the count is above 0, keep its id and score. Sort by score, highest first, keeping the order of equal scores. Return the first k ids.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Step by step

1. A text as a set of lowercase words. Lowercasing makes AI and ai the same word. A set holds each word once, so a word repeated ten times still counts once.
2. Score: how many query words the document contains. Looking a word up in a set is one fast check, and it matches whole words only: art is not found in start.
3. Keep only documents that share at least one word. A score of 0 means nothing connects the document to the question, so returning it would only add noise.
4. Highest score first; equal scores keep their order. A fixed rule for ties makes the output the same on every run, which you need when you compare two versions of a search.
5. The ids of the first k. Cutting after the sort, not before, makes sure the k that remain are the best ones.

The same numbered steps are the comments in the solution.

function solve(query, documents, k) {
  // 1. A text as a set of lowercase words
  const words = (text) =>
    new Set(text.toLowerCase().match(/[a-z]+/g) ?? []);
  const wanted = words(query);
  const scored = [];
  for (const doc of documents) {
    // 2. Score: how many query words the document contains
    const found = words(doc.text);
    let score = 0;
    for (const word of wanted) {
      if (found.has(word)) score++;
    }
    // 3. Keep only documents that share at least one word
    if (score > 0) scored.push({ id: doc.id, score });
  }
  // 4. Highest score first; equal scores keep their order
  scored.sort((first, second) => second.score - first.score);
  // 5. The ids of the first k
  return scored.slice(0, k).map((entry) => entry.id);
}

import re


def solve(query, documents, k):
    # 1. A text as a set of lowercase words
    def words(text):
        return set(re.findall(r"[a-z]+", text.lower()))

    wanted = words(query)
    scored = []
    for doc in documents:
        # 2. Score: how many query words the document contains
        found = words(doc["text"])
        score = 0
        for word in wanted:
            if word in found:
                score += 1
        # 3. Keep only documents that share at least one word
        if score > 0:
            scored.append((doc["id"], score))
    # 4. Highest score first; equal scores keep their order
    scored.sort(key=lambda entry: -entry[1])
    # 5. The ids of the first k
    return [doc_id for doc_id, score in scored[:k]]

Watch out

• Count each word once. If repeats count, a document that says go go go beats a better match only by repeating itself.
• Match whole words. Checking whether the text contains the letters art also finds start and cart.
• Sort first, then cut to k. Cutting first keeps whichever documents came first, not the best ones.
• In JavaScript: In JavaScript list.sort() with no function compares items as text, so 10 comes before 9. Always pass the comparison when you sort by a number.
• In Python: In Python, sorting whole pairs such as (score, id) breaks ties by the id. Sort by the score alone, with key=, so equal scores keep their original order.

Check yourself