How can I efficiently locate identical sequences of cells in two or more arrays?

Question

How can I efficiently locate identical sequences of cells in two or more arrays?

Unique Example 1

We can explore an interesting scenario by considering two arrays:

('m','o','o','n','s','t','a','r','d')
('s','t','a','r','d')

Let's search for matching sequences between the two arrays that are not part of longer matches. Here is what we found:

('s','t','a','r','d') = position 5 in array 1 and position 0 in array 2

Array 1: ('m','o','o','n','s','t','a','r','d')

Array 2: ('s','t','a','r','d')

Unique Example 2

('m','o','o','n','s','t','a','r','d')
('s','t','a','r','d')

In this case, we have shorter matching sequences:

('s','t','a','r','d') = position 5 in array 1 and position 0 in array 2

Array 1: ('m','o','o','n','s','t','a','r','d')

Array 2: ('s','t','a','r','d')

Overall Overview

Both examples showcase multiple matches, all contained within larger matches in at least one of the arrays.

If you're seeking efficient code (a balance of low memory consumption and high speed suitable for mobile devices), JavaScript implementations would be very beneficial!

javascript arrays algorithm pattern-matching

Answer 1

Answer №1

My attempt at implementing a general LCS algorithm in JavaScript, with a time and space complexity of O(mn). By iterating row by row, we are able to optimize space usage by reusing only two rows and copying the second row to the first once it's processed.

var example1 = [['n','v','a','n','i','n','n','v','a','n'],
               ['a','n','n','n','v','a','n','v','n']],

    example2 = [['n','v','a','n','i','n','n','v','i','n'],
               ['a','n','i','n','v','i','n','v','n']];

function findLCS(arr){
  var M = new Array(arr[0].length),
      result = [];

  for (var i=0; i<arr[0].length; i++){
    M[i] = new Array(arr[1].length).fill(0);

    for (var j=0; j<arr[1].length; j++){
      if (arr[0][i] == arr[1][j]){
        M[i][j] = M[i-1] && M[j-1] ? 1 + M[i-1][j-1] : 1;
      }
      if ((i == arr[0].length - 1 || j == arr[1].length - 1) && M[i][j] > 2){
        result.push([i - M[i][j] + 1,j - M[i][j] + 1,M[i][j]]);
      } else if (i > 1 && j > 1 && M[i][j] < M[i-1][j-1] && M[i-1][j-1] > 2){
        result.push([i - M[i-1][j-1],j - M[i-1][j-1],M[i-1][j-1]]);
      }
    }
  }

  return result;
}

console.log(JSON.stringify(findLCS(example2))); // [[2,0,4],[6,3,4]]

Answer 2

My attempt at implementing a general LCS algorithm in JavaScript, with a time and space complexity of O(mn). By iterating row by row, we are able to optimize space usage by reusing only two rows and copying the second row to the first once it's processed.

var example1 = [['n','v','a','n','i','n','n','v','a','n'],
               ['a','n','n','n','v','a','n','v','n']],

    example2 = [['n','v','a','n','i','n','n','v','i','n'],
               ['a','n','i','n','v','i','n','v','n']];

function findLCS(arr){
  var M = new Array(arr[0].length),
      result = [];

  for (var i=0; i<arr[0].length; i++){
    M[i] = new Array(arr[1].length).fill(0);

    for (var j=0; j<arr[1].length; j++){
      if (arr[0][i] == arr[1][j]){
        M[i][j] = M[i-1] && M[j-1] ? 1 + M[i-1][j-1] : 1;
      }
      if ((i == arr[0].length - 1 || j == arr[1].length - 1) && M[i][j] > 2){
        result.push([i - M[i][j] + 1,j - M[i][j] + 1,M[i][j]]);
      } else if (i > 1 && j > 1 && M[i][j] < M[i-1][j-1] && M[i-1][j-1] > 2){
        result.push([i - M[i-1][j-1],j - M[i-1][j-1],M[i-1][j-1]]);
      }
    }
  }

  return result;
}

console.log(JSON.stringify(findLCS(example2))); // [[2,0,4],[6,3,4]]

Answer 3

Answer №2

If you have two arrays of lengths m and n, it seems that achieving better performance than O(mn) in general is highly unlikely. Consider arrays with alternating as but otherwise unique characters, such as:

[a, b, a, c, a, d, a, e, a, f, a, g]
[a, h, a, i, a, j, a, k, a, l, a, m]

The number of matches between these arrays is (m/2)*(n/2). To find all matches, the algorithm's complexity will likely be at least O(mn).

To achieve O(mn) time complexity, you can perform the following steps. Imagine sliding one array against the other like this:

[a, b, c, d, e]
            [f, g, h, i, j]

   [a, b, c, d, e]
            [f, g, h, i, j]

      [a, b, c, d, e]
            [f, g, h, i, j]

                  ...
                        [a, b, c, d, e]
            [f, g, h, i, j]

There are m + n - 1 possible positions. At each position, you must iterate over pairs of aligned characters (usually no more than min(m, n)) to find the longest chains of matching characters. This results in a time complexity of

O((m + n) * min(m, n)) = O(mn)

This solution's drawback is that its time complexity depends mainly on the length of the arrays rather than their actual content. For instance, even if the arrays are identical, it still requires O(nm) time, although determining equality would only take O(n). As noted in another response, there exist smarter solutions that are significantly faster when dealing with fewer matching sequences.

Answer 4

If you have two arrays of lengths m and n, it seems that achieving better performance than O(mn) in general is highly unlikely. Consider arrays with alternating as but otherwise unique characters, such as:

[a, b, a, c, a, d, a, e, a, f, a, g]
[a, h, a, i, a, j, a, k, a, l, a, m]

The number of matches between these arrays is (m/2)*(n/2). To find all matches, the algorithm's complexity will likely be at least O(mn).

To achieve O(mn) time complexity, you can perform the following steps. Imagine sliding one array against the other like this:

[a, b, c, d, e]
            [f, g, h, i, j]

   [a, b, c, d, e]
            [f, g, h, i, j]

      [a, b, c, d, e]
            [f, g, h, i, j]

                  ...
                        [a, b, c, d, e]
            [f, g, h, i, j]

There are m + n - 1 possible positions. At each position, you must iterate over pairs of aligned characters (usually no more than min(m, n)) to find the longest chains of matching characters. This results in a time complexity of

O((m + n) * min(m, n)) = O(mn)

This solution's drawback is that its time complexity depends mainly on the length of the arrays rather than their actual content. For instance, even if the arrays are identical, it still requires O(nm) time, although determining equality would only take O(n). As noted in another response, there exist smarter solutions that are significantly faster when dealing with fewer matching sequences.

Answer 5

Answer №3

Provided here is an optimal O(n+k) solution for comparing two strings A and B, with total length n and k maximal matching substrings:

To begin, construct a generalised suffix tree using the strings A and B. This involves creating a standard suffix tree on the concatenated single string A$B#, where $ and # are unique characters absent from both A and B. Building this tree can be achieved in O(n) time employing algorithms like Ukkonen's.
Subsequently, engage in a bottom-up depth-first search through the constructed tree while executing two tasks at each node:
- Determine and record whether there are any leaf nodes corresponding to suffixes of A or B under the current node. (Try to figure out how to address this question specifically for a leaf node.)
- If leaf nodes exist for both kinds of strings, and this condition does not hold true for any child nodes, identify and report the substring denoted by the current node as a potential match. If the same situation occurs for a child node as well, the substring represented by the parent node will be a subset of the child node's substring—emphasizing the need for maximum substrings only.

This method also extends smoothly to deal with scenarios involving multiple input strings greater than or equal to three: maintain and assess the set of input strings connected to leaves below the present node, triggering appropriate actions when this set reaches full capacity.

Answer 6

Provided here is an optimal O(n+k) solution for comparing two strings A and B, with total length n and k maximal matching substrings:

To begin, construct a generalised suffix tree using the strings A and B. This involves creating a standard suffix tree on the concatenated single string A$B#, where $ and # are unique characters absent from both A and B. Building this tree can be achieved in O(n) time employing algorithms like Ukkonen's.
Subsequently, engage in a bottom-up depth-first search through the constructed tree while executing two tasks at each node:
- Determine and record whether there are any leaf nodes corresponding to suffixes of A or B under the current node. (Try to figure out how to address this question specifically for a leaf node.)
- If leaf nodes exist for both kinds of strings, and this condition does not hold true for any child nodes, identify and report the substring denoted by the current node as a potential match. If the same situation occurs for a child node as well, the substring represented by the parent node will be a subset of the child node's substring—emphasizing the need for maximum substrings only.

This method also extends smoothly to deal with scenarios involving multiple input strings greater than or equal to three: maintain and assess the set of input strings connected to leaves below the present node, triggering appropriate actions when this set reaches full capacity.

How can I efficiently locate identical sequences of cells in two or more arrays?

Answer №1

Answer №2

Answer №3

Similar questions

Help needed with using Regex to restrict the number of alphabetical characters allowed

Leverage Jquery within the div element to manipulate the data retrieved from a post ajax request

How can I retrieve a file from the www-directory using PhoneGap?

Is it possible to execute "green arrow" unit tests directly with Mocha in IntelliJ IDEA, even when Karma and Mocha are both installed?

Inverting array - excluding the initial digit

Create a layout with two rows of two buttons in HTML aligned to the right side while maintaining the left side's

Update google maps markers and infoBubbles dynamically with ajax

Challenges with implementing speech recognition within a React component's state

Uniform Image Sizes in Bootstrap Carousel (With One Exception)

Collaborative JavaScript repository within the Websphere Liberty platform

`Node.js encountering issues with undefined JSON Array values`

encountered net::ERR_EMPTY_RESPONSE while attempting to locate a CSS file within an AngularJS directive

Flask is failing to display AJAX data

Enhancing Efficiency and Optimization with jQuery

Determine if the input text field contains any text and store it in a variable using jQuery

Custom positioning of Mui Snackbar in V5

Utilizing jQuery grep() to sort through a JSON array

Populate a select list in real time with dynamically generated options

What's the best way to manage endless routing options in express.js?

Tips for effectively exchanging information among angular services