Rank documents by word-count similarity

A simple baseline for search: represent texts by their word counts and rank documents by cosine similarity to the query.

What to build

A program that ranks documents against a query by the cosine similarity of their word-count vectors.

Requirements

  • Each text is a vector of word counts; compare the query with each document by cosine similarity (0 if they share no words).
  • Print the k best as D: S, D the document number from 1 and S to 3 decimal places, highest first; equal scores by document number.

Input

Line 1: n. Then n documents, one per line. Then the query, then k.

Output

k lines.

Constraints

1 ≤ k ≤ n ≤ 1000; texts are lower-case words.

Example

Input:

3
the cat sat
the dog barked
a cat and a dog
cat dog
2

Output:

3: 0.535
1: 0.408

Why it works

Counting words turns texts into vectors, and cosine similarity rewards shared words while ignoring how long each text is.

Examples

Example 1 · Input
3
the cat sat
the dog barked
a cat and a dog
cat dog
2
Expected output
3: 0.535
1: 0.408
Example 2 · Input
2
x
y
y
2
Expected output
2: 1.000
1: 0.000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Turn each text into a dictionary of word counts.

Hint 2

Cosine similarity: the sum over shared words of count × count, divided by the two vectors' lengths.

Hint 3

Sort by score from highest to lowest, then by document number.

Solution

Show one correct solution (try it yourself first)
import math

n = int(input())
docs = [input().split() for _ in range(n)]
query = input().split()
k = int(input())


def counts(words):
    c = {}
    for w in words:
        c[w] = c.get(w, 0) + 1
    return c


def cosine(a, b):
    dot = sum(a[w] * b.get(w, 0) for w in a)
    return dot / (math.sqrt(sum(v * v for v in a.values())) * math.sqrt(sum(v * v for v in b.values())))


q = counts(query)
scores = sorted(((-cosine(q, counts(d)), i + 1) for i, d in enumerate(docs)))
for s, i in scores[:k]:
    print(f"{i}: {-s:.3f}")

Lesson: Semantic search →