NLP: Rank documents by TF-IDF cosine

Rank documents for a query the way a classic search engine does.

What to build

A program that ranks documents by the cosine similarity of their TF-IDF vectors to each query.

Requirements

  • Lowercase and split documents and queries on whitespace. For any text, a word's weight is (number of times it occurs in the text) × idf, with idf = ln(N ÷ df) over the documents. Query words that occur in no document are ignored.
  • Score each document by the cosine similarity of its weights and the query's weights (0 if either has length 0).
  • For each query, print the at most k documents with a score above 0 as D:S (document number from 1, score with four decimal places), separated by spaces, highest score first and equal scores in document order; print no results if there are none.

Input

Line 1: N and k. Then N documents. Then q and q queries.

Output

q lines.

Constraints

N ≤ 200; q ≤ 50.

Example

Input:

4 2
cheap flights paris
paris hotels cheap
python books
python guide
2
cheap paris hotels
python

Output:

2:1.0000 1:0.3333
3:0.4472 4:0.4472

Why it works

Cosine ignores document length, and IDF gives words found in every document a weight of 0 and rare words large weights, so documents that share the query's informative words rise to the top.

Examples

Example 1 · Input
4 2
cheap flights paris
paris hotels cheap
python books
python guide
2
cheap paris hotels
python
Expected output
2:1.0000 1:0.3333
3:0.4472 4:0.4472
Example 2 · Input
2 3
the cat
the dog
2
the
cat dog
Expected output
no results
1:0.7071 2:0.7071

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

Hints

Hint 1

A text's weights are a dictionary `{word: count × idf}` over its words that occur in the collection; idf = `math.log(N / df)`.

Hint 2

Cosine = dot ÷ (length × length); if either length is 0, the similarity is 0. Sort by `(-round(score, 9), number)`.

Solution

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

n, k = map(int, input().split())
docs = [input().lower().split() for _ in range(n)]
df = {}
for doc in docs:
    for w in set(doc):
        df[w] = df.get(w, 0) + 1
idf = {w: math.log(n / c) for w, c in df.items()}


def weights(words):
    return {w: words.count(w) * idf[w] for w in words if w in idf}


def cosine(a, b):
    dot = sum(a[w] * b[w] for w in a if w in b)
    na = math.sqrt(sum(v * v for v in a.values()))
    nb = math.sqrt(sum(v * v for v in b.values()))
    return dot / (na * nb) if na and nb else 0.0


vectors = [weights(doc) for doc in docs]
for _ in range(int(input())):
    q = weights(input().lower().split())
    scores = [(cosine(q, v), i + 1) for i, v in enumerate(vectors)]
    ranked = sorted([s for s in scores if s[0] > 0], key=lambda s: (-round(s[0], 9), s[1]))[:k]
    print(" ".join(f"{i}:{s:.4f}" for s, i in ranked) if ranked else "no results")

Lesson: Text similarity and search →