Nearest words by cosine similarity

Find the words whose embeddings are most similar to a given word.

What to build

A program that lists the k nearest neighbours of a word in an embedding table.

Requirements

  • Compare the query word with every other word by cosine similarity.
  • Print the k most similar as WORD S, with S to 3 decimal places, highest first; equal similarities in alphabetical order.

Input

Line 1: n. Then n lines word x1 x2 .... Then a line query k.

Output

k lines.

Constraints

2 ≤ n ≤ 1000; 1 ≤ k < n; no vector is all zeros.

Example

Input:

5
king 5 1 0
queen 5 4 0
man 1 0 0
woman 1 3 0
apple 0 1 5
king 3

Output:

man 0.981
queen 0.888
woman 0.496

Why it works

Cosine similarity ranks the other words by how closely their embeddings point in the query word's direction, which is how semantic neighbours are found.

Examples

Example 1 · Input
5
king 5 1 0
queen 5 4 0
man 1 0 0
woman 1 3 0
apple 0 1 5
king 3
Expected output
man 0.981
queen 0.888
woman 0.496
Example 2 · Input
3
a 1 0
b 0 1
c 1 1
a 1
Expected output
c 0.707

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

Hints

Hint 1

Compute the cosine similarity between the query word's vector and every other word's vector.

Hint 2

Sort by similarity from highest to lowest, then alphabetically, and keep k.

Solution

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

n = int(input())
vectors = {}
for _ in range(n):
    word, *nums = input().split()
    vectors[word] = list(map(float, nums))
query, k = input().split()


def cosine(a, b):
    dot = sum(x * y for x, y in zip(a, b))
    return dot / (math.sqrt(sum(x * x for x in a)) * math.sqrt(sum(y * y for y in b)))


scores = [(word, cosine(vectors[query], v)) for word, v in vectors.items() if word != query]
scores.sort(key=lambda ws: (-ws[1], ws[0]))
for word, s in scores[: int(k)]:
    print(word, f"{s:.3f}")

Lesson: Embeddings and similarity →