Find the words an embedding considers most alike.
What to build
A program that lists the most similar words to each query word.
Requirements
- Compare a query with every other word by cosine similarity. Rank from most to least similar; equal similarities (to four decimal places) are ordered alphabetically.
- Print
QUERY: W1 (S1), W2 (S2), …with similarities to four decimal places.
Input
Line 1: n and d. Then n lines: a word and d numbers. Then q and q lines WORD k.
Output
q lines.
Constraints
n ≤ 500; d ≤ 50; k < n.
Example
Input:
4 2
cat 1 0
dog 1 1
car 0 1
sea -1 0
2
cat 2
dog 2
Output:
cat: dog (0.7071), car (0.0000)
dog: car (0.7071), cat (0.7071)
Why it works
Words used in similar ways get vectors pointing in similar directions, so ranking by cosine similarity finds related words.
Examples
Example 1 · Input
4 2 cat 1 0 dog 1 1 car 0 1 sea -1 0 2 cat 2 dog 2
Expected output
cat: dog (0.7071), car (0.0000) dog: car (0.7071), cat (0.7071)
Example 2 · Input
3 3 x 1 0 0 y 0 1 0 z 1 1 0 1 z 2
Expected output
z: x (0.7071), y (0.7071)
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Compute the cosine similarity between the query's vector and every other word's vector.
Hint 2
Sort by similarity from high to low, breaking ties alphabetically, and keep the first k.
Solution
Show one correct solution (try it yourself first)
import math
n, d = map(int, input().split())
vectors = {}
for _ in range(n):
word, *values = input().split()
vectors[word] = list(map(float, values))
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)))
for _ in range(int(input())):
word, k = input().split()
scores = [(round(cosine(vectors[word], v), 4) + 0.0, w) for w, v in vectors.items() if w != word]
scores.sort(key=lambda item: (-item[0], item[1]))
print(f"{word}: " + ", ".join(f"{w} ({s:.4f})" for s, w in scores[: int(k)]))