Compute Jaccard similarity of 2 multisets, both with ignoring an element's multiplicity and with considering it. The first case of course equals to assuming an overall multiplicity of 1. Returns a pair of numbers. */
| 315 | Returns a pair of numbers. |
| 316 | */ |
| 317 | static Double2 jaccard(const TokenBag &t1, const TokenBag &t2) |
| 318 | { |
| 319 | unsigned share_0 = 0; // card. of intersection ignoring multiplicity |
| 320 | unsigned total_0 = 0; // card. of union ignoring multiplicity |
| 321 | unsigned share_1 = 0; // card. of intersection considering multiplicity |
| 322 | unsigned total_1 = 0; // card. of union considering multiplicity |
| 323 | |
| 324 | /* Example: |
| 325 | A = 1 1 2 3 3 3 4 4 5 | 1 2 3 4 5 | 9 | 5 |
| 326 | B = 2 2 3 3 3 4 6 | 2 3 4 6 | 7 | 4 |
| 327 | --------------------------------------------------- |
| 328 | A*B = 2 3 3 3 4 | 2 3 4 | 5 | 3 |
| 329 | A+B= 1 1 2 2 3 3 3 4 4 5 6 | 1 2 3 4 5 6 | 11 | 6 |
| 330 | |
| 331 | share_0 = 3, total_0 = 6, share_0/total_0 = 0.5 |
| 332 | share_1 = 5, total_1 = 11, share_1/total_1 = 0.45 |
| 333 | (of course _0 and _1 the same when multiplicity is 1 overall) |
| 334 | |
| 335 | Note: result numbers are independent, can have |
| 336 | share_0/total_0 (<, ==, >) share_1/total_1 |
| 337 | */ |
| 338 | |
| 339 | // Lock-step traversal of the 2 vectors: |
| 340 | auto it1 = t1.cbegin(); |
| 341 | auto it2 = t2.cbegin(); |
| 342 | auto t1_cend = t1.cend(); |
| 343 | auto t2_cend = t2.cend(); |
| 344 | |
| 345 | while (it1 != t1_cend && it2 != t2_cend) { |
| 346 | total_0++; |
| 347 | if (it1->first < it2->first) // difference |
| 348 | total_1 += (it1++)->second; |
| 349 | else |
| 350 | if (it1->first > it2->first) // difference |
| 351 | total_1 += (it2++)->second; |
| 352 | else { // intersection |
| 353 | share_0++; |
| 354 | // just as fast as single if |
| 355 | total_1 += max(it1->second, it2->second); |
| 356 | share_1 += min(it1->second, it2->second); |
| 357 | ++it1; ++it2; |
| 358 | } |
| 359 | } |
| 360 | // Handle leftover tails: |
| 361 | while (it1 != t1_cend) { |
| 362 | total_0++; |
| 363 | total_1 += (it1++)->second; |
| 364 | } |
| 365 | while (it2 != t2_cend) { |
| 366 | total_0++; |
| 367 | total_1 += (it2++)->second; |
| 368 | } |
| 369 | return { double(share_0)/total_0, double(share_1)/total_1 }; |
| 370 | } |
| 371 | |
| 372 | /* Check pairs of samples for similarity. |
| 373 | All n(n-1)/2 pairs are considered in principle. |