Build word vectors from the company words keep, the idea behind GloVe and word2vec.
What to build
A program that builds a co-occurrence matrix and compares words with cosine similarity.
Requirements
- Lowercase the sentences and split them on whitespace; the vocabulary is all their words, sorted. Windows never cross from one sentence to another.
- For every occurrence of a word, add 1 to its vector at the column of each word within w positions before or after it in the same sentence.
- Print
vocabulary: ..., thenword: c1 c2 ...for every vocabulary word in order. Then, for each query pair, printa b Cwith the cosine similarity of their vectors to three decimal places (0.000 if either vector is all zeros).
Input
Line 1: the window size w. Line 2: n. Then n sentences. Then q and q pairs of vocabulary words.
Output
The vocabulary line, one line per word, then q lines.
Constraints
w ≤ 5; at most 30 distinct words.
Example
Input:
1
3
i like tea
i like coffee
you drink tea
2
tea coffee
like drink
Output:
vocabulary: coffee drink i like tea you
coffee: 0 0 0 1 0 0
drink: 0 0 0 0 1 1
i: 0 0 0 2 0 0
like: 1 0 2 0 1 0
tea: 0 1 0 1 0 0
you: 0 1 0 0 0 0
tea coffee 0.707
like drink 0.289
Why it works
Words that appear in the same contexts collect counts in the same columns, so their rows point in similar directions even if the two words never appear together.
Examples
1 3 i like tea i like coffee you drink tea 2 tea coffee like drink
vocabulary: coffee drink i like tea you coffee: 0 0 0 1 0 0 drink: 0 0 0 0 1 1 i: 0 0 0 2 0 0 like: 1 0 2 0 1 0 tea: 0 1 0 1 0 0 you: 0 1 0 0 0 0 tea coffee 0.707 like drink 0.289
2 1 a b c 2 a c a b
vocabulary: a b c a: 0 1 1 b: 1 0 1 c: 1 1 0 a c 0.500 a b 0.500
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For the word at position i, its neighbours are positions max(0, i − w) to min(len − 1, i + w), except i itself.
Hint 2
Give each vocabulary word an index (`{t: i for i, t in enumerate(vocab)}`) so you can add 1 to the right column.
Solution
Show one correct solution (try it yourself first)
import math
w = int(input())
sentences = [input().lower().split() for _ in range(int(input()))]
vocab = sorted(set(t for s in sentences for t in s))
index = {t: i for i, t in enumerate(vocab)}
vec = {t: [0] * len(vocab) for t in vocab}
for s in sentences:
for i, t in enumerate(s):
for j in range(max(0, i - w), min(len(s), i + w + 1)):
if j != i:
vec[t][index[s[j]]] += 1
print("vocabulary:", " ".join(vocab))
for t in vocab:
print(f"{t}: {' '.join(map(str, vec[t]))}")
for _ in range(int(input())):
a, b = input().split()
u, v = vec[a], vec[b]
dot = sum(x * y for x, y in zip(u, v))
norm = math.sqrt(sum(x * x for x in u)) * math.sqrt(sum(y * y for y in v))
print(f"{a} {b} {dot / norm:.3f}" if norm else f"{a} {b} 0.000")