Check pairs of samples for similarity. All n(n-1)/2 pairs are considered in principle. Avoid a quadratic number of tests by flagging samples that are found similar. */
| 375 | that are found similar. |
| 376 | */ |
| 377 | static void check_samples() |
| 378 | { |
| 379 | unsigned num_clusters = 0; |
| 380 | unsigned max_cluster_size = 0; |
| 381 | unsigned total_cluster_size = 0; |
| 382 | unsigned singletons = 0; |
| 383 | unsigned num_samples = samples.size(); |
| 384 | |
| 385 | if (!num_samples) |
| 386 | return; |
| 387 | |
| 388 | // Output only non-singleton clusters separated by a blank line. |
| 389 | |
| 390 | // Tried using a std::queue for inner loop but does not seem to affect |
| 391 | // performance much. Probably because of underlying deque. |
| 392 | // Even simple queue using fixed size array does no improve things. |
| 393 | |
| 394 | for (auto it1 = samples.begin(), end = samples.end(); it1 != end; ++it1) { |
| 395 | //fprintf(stderr, "id: %s\n", it1->id.c_str()); |
| 396 | if (it1->flag) continue; |
| 397 | const unsigned s1 = it1->size(); |
| 398 | // FIXME: Put all samples similar to this one in a cluster. |
| 399 | unsigned cluster_size = 1; |
| 400 | for (auto it2 = next(it1), end = samples.end(); it2 != end; ++it2) { |
| 401 | if (it2->flag) continue; |
| 402 | const unsigned s2 = it2->size(); |
| 403 | |
| 404 | // Allow s2 to deviate up to +- 5% from s1: |
| 405 | if (::abs(s1 - s2) * 100.0 / s1 > 5.0) continue; |
| 406 | |
| 407 | switch (mode) { |
| 408 | case LCS: { |
| 409 | // Cheap upperbound calculation: |
| 410 | unsigned up = lcs_upperbound(it1->token_bag, it2->token_bag); |
| 411 | if (up < s1 * threshold_0) |
| 412 | continue; |
| 413 | |
| 414 | unsigned lcs_len = lcs(it1->token_seq, it2->token_seq, s1, s2); |
| 415 | if (lcs_len >= s1 * threshold_0) { |
| 416 | // Flag it2 (always beyond it1) as dealt with: |
| 417 | it2->flag = true; |
| 418 | if (cluster_size == 1) |
| 419 | fprintf(stdout, "%s: (%3u)\n", it1->id.c_str(), s1); |
| 420 | fprintf(stdout, "%s: %3u (%3u)\n", it2->id.c_str(), lcs_len, s2); |
| 421 | cluster_size++; |
| 422 | } |
| 423 | break; |
| 424 | } |
| 425 | |
| 426 | case JACCARD: { |
| 427 | Double2 similarity = jaccard(it1->token_bag, it2->token_bag); |
| 428 | if (similarity.first >= threshold_0 && |
| 429 | similarity.second >= threshold_1) { |
| 430 | |
| 431 | // Flag it2 (always beyond it1) as dealt with: |
| 432 | it2->flag = true; |
| 433 | if (cluster_size == 1) |
| 434 | fprintf(stdout, "%s:\n", it1->id.c_str()); |