* Finds the differences between two sequences of chunk lengths or sizes. * Uses a longest common subsequence algorithm to identify matching elements * and extract the differences between the sequences. * * @param first The first sequence of chunk values * @param second The second sequence of chunk values * @return A vector of differences, where each difference is a pair of * subsequ
| 418 | * subsequences (one from each input) that differ |
| 419 | */ |
| 420 | std::vector<ChunkDiff> FindDifferences(const ChunkList& first, const ChunkList& second) { |
| 421 | // Compute the longest common subsequence using dynamic programming |
| 422 | size_t n = first.size(), m = second.size(); |
| 423 | std::vector<std::vector<size_t>> dp(n + 1, std::vector<size_t>(m + 1, 0)); |
| 424 | |
| 425 | // Fill the dynamic programming table |
| 426 | for (size_t i = 0; i < n; i++) { |
| 427 | for (size_t j = 0; j < m; j++) { |
| 428 | if (first[i] == second[j]) { |
| 429 | // If current elements match, extend the LCS |
| 430 | dp[i + 1][j + 1] = dp[i][j] + 1; |
| 431 | } else { |
| 432 | // If current elements don't match, take the best option |
| 433 | dp[i + 1][j + 1] = std::max(dp[i + 1][j], dp[i][j + 1]); |
| 434 | } |
| 435 | } |
| 436 | } |
| 437 | |
| 438 | // Backtrack through the dynamic programming table to reconstruct the common |
| 439 | // parts and their positions in the original sequences |
| 440 | std::vector<std::pair<size_t, size_t>> common; |
| 441 | for (size_t i = n, j = m; i > 0 && j > 0;) { |
| 442 | if (first[i - 1] == second[j - 1]) { |
| 443 | // Found a common element, add to common list |
| 444 | common.emplace_back(i - 1, j - 1); |
| 445 | i--, j--; |
| 446 | } else if (dp[i - 1][j] >= dp[i][j - 1]) { |
| 447 | // Move in the direction of the larger LCS value |
| 448 | i--; |
| 449 | } else { |
| 450 | j--; |
| 451 | } |
| 452 | } |
| 453 | // Reverse to get indices in ascending order |
| 454 | std::reverse(common.begin(), common.end()); |
| 455 | |
| 456 | // Build the differences by finding sequences between common elements |
| 457 | std::vector<ChunkDiff> result; |
| 458 | size_t last_i = 0, last_j = 0; |
| 459 | for (auto& c : common) { |
| 460 | auto ci = c.first; |
| 461 | auto cj = c.second; |
| 462 | // If there's a gap between the last common element and this one, |
| 463 | // record the difference |
| 464 | if (ci > last_i || cj > last_j) { |
| 465 | result.push_back({{first.begin() + last_i, first.begin() + ci}, |
| 466 | {second.begin() + last_j, second.begin() + cj}}); |
| 467 | } |
| 468 | // Move past this common element |
| 469 | last_i = ci + 1; |
| 470 | last_j = cj + 1; |
| 471 | } |
| 472 | |
| 473 | // Handle any remaining elements after the last common element |
| 474 | if (last_i < n || last_j < m) { |
| 475 | result.push_back( |
| 476 | {{first.begin() + last_i, first.end()}, {second.begin() + last_j, second.end()}}); |
| 477 | } |