Source: diff/lib/Lcs.js

  1. import {DiffConfig} from '../../config/DiffConfig.js';
  3. /**
  4.  * Compute the length of the longest common subsequence (LCS) between two
  5.  * sequences. A simple dynamic programming approach is employed, which yields
  6.  * O(n*m) time complexity and O(n*m) space complexity.
  7.  * @param {Array<any>} seqA The first sequence.
  8.  * @param {Array<any>} seqB The second sequence.
  9.  * @param {Function} compare The comparator function used to identify equal
  10.  *     elements between the sequences. Defaults to the built-in strict equality
  11.  *     operator ("===").
  12.  * @return {Number} The length of the LCS.
  13.  */
  14. export function getLcsLength(seqA, seqB, compare = (a, b) => a === b) {
  15.   // Initial 2D array of size (m + 1) * (n + 1)
  16.   const dp = new Array(seqA.length + 1);
  17.   for (let i = 0; i < seqA.length + 1; i++) {
  18.     dp[i] = new Array(seqB.length + 1);
  19.   }
  21.   // The LCS of any sequence with a sequence of length zero
  22.   // also has length zero
  23.   for (let i = 0; i <= seqA.length; i++) {
  24.     dp[i][0] = 0;
  25.   }
  26.   for (let i = 0; i <= seqB.length; i++) {
  27.     dp[0][i] = 0;
  28.   }
  30.   // We expect most inputs to yield a short LCS, so a bottom-up approach is
  31.   // preferred.
  32.   for (let i = 1; i <= seqA.length; i++) {
  33.     for (let j = 1; j <= seqB.length; j++) {
  34.       if (compare(seqA[i - 1], seqB[j - 1])) {
  35.         dp[i][j] = dp[i - 1][j - 1] + 1;
  36.       } else if (dp[i - 1][j] > dp[i][j - 1]) {
  37.         dp[i][j] = dp[i - 1][j];
  38.       } else {
  39.         dp[i][j] = dp[i][j - 1];
  40.       }
  41.     }
  42.   }
  44.   return dp[seqA.length][seqB.length];
  45. }
  47. // Initial 2D array of size (r + 1) * (r + 1)
  48. const dp = new Array(DiffConfig.COMPARATOR.PATH_COMPARE_RANGE + 1);
  49. for (let i = 0; i < dp.length; i++) {
  50.   dp[i] = new Array(dp.length);
  51. }
  53. /**
  54.  * Faster LCS computation for sequences of maximum length r (path compare
  55.  * range) due to matrix reuse.
  56.  * @param {Array<Number>} seqA The first sequence.
  57.  * @param {Array<Number>} seqB The second sequence.
  58.  * @return {Number} The length of the LCS.
  59.  */
  60. export function getLcsLengthFast(seqA, seqB) {
  61.   // The LCS of any sequence with a sequence of length zero
  62.   // also has length zero
  63.   for (let i = 0; i <= seqA.length; i++) {
  64.     dp[i][0] = 0;
  65.   }
  66.   for (let i = 0; i <= seqB.length; i++) {
  67.     dp[0][i] = 0;
  68.   }
  70.   // We expect most inputs to yield a short LCS, so a bottom-up approach is
  71.   // preferred.
  72.   for (let i = 1; i <= seqA.length; i++) {
  73.     for (let j = 1; j <= seqB.length; j++) {
  74.       if (seqA[i - 1] === seqB[j - 1]) {
  75.         dp[i][j] = dp[i - 1][j - 1] + 1;
  76.       } else if (dp[i - 1][j] > dp[i][j - 1]) {
  77.         dp[i][j] = dp[i - 1][j];
  78.       } else {
  79.         dp[i][j] = dp[i][j - 1];
  80.       }
  81.     }
  82.   }
  84.   return dp[seqA.length][seqB.length];
  85. }