Compute cosine similarity of 2 multisets. */
| 273 | /* Compute cosine similarity of 2 multisets. |
| 274 | */ |
| 275 | static double cosine(const TokenBag &t1, const TokenBag &t2) |
| 276 | { |
| 277 | double dot = 0.0; |
| 278 | double norm1 = 0.0; |
| 279 | double norm2 = 0.0; |
| 280 | |
| 281 | // Lock-step traversal of the 2 vectors: |
| 282 | auto it1 = t1.cbegin(); |
| 283 | auto it2 = t2.cbegin(); |
| 284 | auto t1_cend = t1.cend(); |
| 285 | auto t2_cend = t2.cend(); |
| 286 | |
| 287 | // Feature value is the frequency. |
| 288 | while (it1 != t1_cend && it2 != t2_cend) { |
| 289 | // For normalization: |
| 290 | norm1 += it1->second * it1->second; |
| 291 | norm2 += it2->second * it2->second; |
| 292 | |
| 293 | if (it1->first < it2->first) |
| 294 | ++it1; |
| 295 | else |
| 296 | if (it1->first > it2->first) |
| 297 | ++it2; |
| 298 | else { // intersection of features |
| 299 | dot += it1->second * it2->second; |
| 300 | ++it1; ++it2; |
| 301 | } |
| 302 | } |
| 303 | // Handle leftover tails: |
| 304 | for (; it1 != t1_cend; ++it1) |
| 305 | norm1 += it1->second * it1->second; |
| 306 | for (; it2 != t2_cend; ++it2) |
| 307 | norm2 += it2->second * it2->second; |
| 308 | |
| 309 | return dot / sqrt(norm1 * norm2); |
| 310 | } |
| 311 | |
| 312 | /* Compute Jaccard similarity of 2 multisets, both with ignoring an |
| 313 | element's multiplicity and with considering it. The first case of |