# How can I compute a similarity score between two documents with the provided algorithm?

I am implementing an algorithm to determine a similarity score between two text documents, Document A and Document B, and I need some help with the math for computing similarity scores.

Method 1:

1. For each document
2. Break the document into sentences
3. Record the hash value for each sentence into a Set

Now there is a Set of hashes for Doc. A, and a Set of Hashes for Doc. B. Take the intersection of the two Sets, and:

Similarity = # hashes in intersection
__________________________
max(total # of hashes in Doc. A, total # of hashes in Doc. B


In essence, if Doc. A has 120 sentences, Doc. B has 15o sentences, and they share 75 of the same exact sentences, then the similarity score is 75/max(120,250) = 75/150 = 0.5.

Question 1: Is that a legitimate calculation for similarity? I'm especially concerned about taking the max() in the denominator.

Method 2:

1. For each document
2. Break the document into sentences (and record the hash value for each sentence)
3. For each sentence, slide through the sentence with a basic sliding window algorithm
4. Record the hash value for each window into a Set

Here is a quick example of a basic sliding window:

"Jack and Jill ran up the hill because Jill wanted
to fetch a pail of water. Unfortunately, Jack fell
down and broke his crown. Even worse, Jill came tumbling after."

window 1 = Jack and Jill ran up
window 2 = and Jill ran up the
window 3 = Jill ran up the hill
window 4 = ...


Method 2 should be more accurate in that it will pick up on potential changes within the sentences. At this point, I can compute the similarity in the same way that I did in Method 1 - the Sets will just be larger. But instead, I think it would be more accurate/more optimal to:

1. Take the intersection between the sets of hashed sentences, and compute the score as described in Method 1.
2. For any elements NOT in the intersection, compare the hashed windows of each sentence, rather than the hashed sentences. Compute similarity as before, with (intersection of windows / max(windows of Doc. A, windows Doc. B))

Question 2: Now that I have two partial scores, how can I combine them into one (accurate) similarity score?

• Where is the set theory part? – Asaf Karagila Sep 12 '13 at 20:33

Question 1: Yes, it is legitimate, why not? Alternatively, you might use the arithmetic or geometric mean.

Question 2: You can do a lot of things, e.g. compute a convex combination. of the partial scores. Be careful: With identical documents, your sliding window score might end up as $\frac 00$. Also, it might happen that changing a word might slicghtly decrease the sentence score and greatyly increas the window score! To avoid that, why not use the sliding window score alone or combine the sentence hases with the window hashes? A long sentence will creat many window matches, but should that really be avoided?

I'll disagree with Hagen: I don't think the $\max$ in the denominator is a legitimate way to compute similarity. If document 1 is one sentence long and document 2 is $x$ sentences long, then adding a sentence to document 2 shouldn't usually be expected to increase the collision rate between the documents. If both documents are $x$ sentences long, then adding a sentence to document 2 should usually be expected to increase the collision rate between the documents. Yet taking a $\max$ in the denominator means that the "cost" in similarity value of adding a sentence to document 2 is the same in either case.

Here's another way of making a hash-based model that seems more informed to me. Suppose your hash algorithm is throwing input into one of $b$ different bins, and we'll assume it's a perfect hash algorithm (the probability of a random sentence being placed in any given bin is the same). Suppose document $1$ is $x$ sentences long, and document $2$ is $y$ sentences long. If $x$ and $y$ are independently generated, then we would expect to see $\frac{xy}{b}$ collisions (do you see why that's true?). More generally, if the probability of one $x$ sentence colliding with one $y$ sentence is $p$ (instead of $\frac{1}{b}$), then we would expect to see $pxy$ collisions.

In some sense, the "similarity score" is the parameter $p$. We can get a good estimate of it by writing $pxy \approx c$, so $p \approx \frac{c}{xy}$. This will give you $p$-values between $0$ and $1$, which you can then map onto any interval you like in any manner you like (with the knowledge that your map should place the value $p = \frac{1}{b}$ as the "average" similarity score).

I don't like the idea of using a hash. What I would do is to construct a similarity measure between each pair of sentences as some combination of the distance between the sentences $D(S_1, S_2)$ (i.e., the number of changes needed to transform one sentence into the other) and how far apart the sentences are in the documents ($|Loc(S_1)-Loc(S_2)|$).

If you want the distance between the sentences to be symmetric, you could average their distances $(\dfrac{D(S_1, S_2)+D(S_2, S_1)}{2}$).