An upperbound for the length of an LCS.
| 247 | |
| 248 | // An upperbound for the length of an LCS. |
| 249 | static unsigned lcs_upperbound(const TokenBag &t1, const TokenBag &t2) |
| 250 | { |
| 251 | unsigned share_1 = 0; // card. of intersection considering multiplicity |
| 252 | |
| 253 | // Lock-step traversal of the 2 vectors: |
| 254 | auto it1 = t1.cbegin(); |
| 255 | auto it2 = t2.cbegin(); |
| 256 | auto t1_cend = t1.cend(); |
| 257 | auto t2_cend = t2.cend(); |
| 258 | |
| 259 | while (it1 != t1_cend && it2 != t2_cend) { |
| 260 | if (it1->first < it2->first) |
| 261 | ++it1; |
| 262 | else |
| 263 | if (it1->first > it2->first) |
| 264 | ++it2; |
| 265 | else { // intersection |
| 266 | share_1 += it1->second < it2->second ? it1->second : it2->second; |
| 267 | ++it1; ++it2; |
| 268 | } |
| 269 | } |
| 270 | return share_1; |
| 271 | } |
| 272 | |
| 273 | /* Compute cosine similarity of 2 multisets. |
| 274 | */ |