| 21 | // --------------------------------------------------------------------------- |
| 22 | |
| 23 | double L1Scoring::score(const BowVector& v1, const BowVector& v2) const { |
| 24 | BowVector::const_iterator v1_it, v2_it; |
| 25 | const BowVector::const_iterator v1_end = v1.end(); |
| 26 | const BowVector::const_iterator v2_end = v2.end(); |
| 27 | |
| 28 | v1_it = v1.begin(); |
| 29 | v2_it = v2.begin(); |
| 30 | |
| 31 | double score = 0; |
| 32 | |
| 33 | while (v1_it != v1_end && v2_it != v2_end) { |
| 34 | const WordValue& vi = v1_it->second; |
| 35 | const WordValue& wi = v2_it->second; |
| 36 | |
| 37 | if (v1_it->first == v2_it->first) { |
| 38 | score += fabs(vi - wi) - fabs(vi) - fabs(wi); |
| 39 | |
| 40 | // move v1 and v2 forward |
| 41 | ++v1_it; |
| 42 | ++v2_it; |
| 43 | } else if (v1_it->first < v2_it->first) { |
| 44 | // move v1 forward |
| 45 | v1_it = v1.lower_bound(v2_it->first); |
| 46 | // v1_it = (first element >= v2_it.id) |
| 47 | } else { |
| 48 | // move v2 forward |
| 49 | v2_it = v2.lower_bound(v1_it->first); |
| 50 | // v2_it = (first element >= v1_it.id) |
| 51 | } |
| 52 | } |
| 53 | |
| 54 | // ||v - w||_{L1} = 2 + Sum(|v_i - w_i| - |v_i| - |w_i|) |
| 55 | // for all i | v_i != 0 and w_i != 0 |
| 56 | // (Nister, 2006) |
| 57 | // scaled_||v - w||_{L1} = 1 - 0.5 * ||v - w||_{L1} |
| 58 | score = -score / 2.0; |
| 59 | |
| 60 | return score; // [0..1] |
| 61 | } |
| 62 | |
| 63 | // --------------------------------------------------------------------------- |
| 64 | // --------------------------------------------------------------------------- |