什么's是在两个(或多个）阵列中找到匹配的细胞序列的最有效方法

What's the most efficient way to find matching sequences of cells in two (or more) arrays?

本文关键字：方法 有效 细胞 什么 两个 阵列      更新时间：2024-06-12

示例1

假设我有两个阵列：

('n','v','a','n','i','n','n','v','a','n')
('a','n','n','n','v','a','n','v','n')

我想找到这两者之间的所有匹配序列（可能在两个单元格以上），它们不是其他较长匹配的子匹配。以下是我所看到的匹配：

('n','n','v','a','n')=阵列1中的位置5和阵列2中的位置3

数组1：（'n'，'v'，'a'，'n'、'i'、'n'和'n'）

数组2：（'a'，'n'，'n'、'n'和'v'，'a'，'n’，'v'和'n'）

示例2

('n','v','a','n','i','n','n','v','i','n')
('a','n','i','n','p','v','i','n','v','n')

这里，我们有不止一个序列，但它们更短，如下所示：

('a','n','i','n')=阵列1中的位置2和阵列2 中的位置0

('v','i','n')=阵列1中的位置7和阵列2中的位置5

数组1：（'n'，'v'，‘a'，'n'、'i'、'n'、'a'、'v'、'i’、'n'）

数组2：（‘a'，‘n'，‘n’，‘p’，'v'，‘i’，‘n‘、'v'、‘n’）

摘要

两个示例中都有多个匹配，但它们都存在于至少一个数组中较大的匹配中。

那么，能实现这一目标的最有效的（比如移动设备，低内存和高速的平衡）代码是什么？JavaScript代码示例将非常棒！

以下是我对通用LCS O(mn)时间和空间版本的JavaScript尝试。由于我们一行接一行地进行，因此可以通过重用两行来减少空间，完成后将第二行复制到第一行。

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 f(as){
  var M = new Array(as[0].length),
      result = [];
  for (var i=0; i<as[0].length; i++){
    M[i] = new Array(as[1].length).fill(0);
    for (var j=0; j<as[1].length; j++){
      if (as[0][i] == as[1][j]){
        M[i][j] = M[i-1] && M[j-1] ? 1 + M[i-1][j-1] : 1;
      }
      if ((i == as[0].length - 1 || j == as[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(f(example2))); // [[2,0,4],[6,3,4]]

如果这两个数组的长度分别为m和n，我认为在一般情况下，您不可能比O(mn)做得更好。假设您的数组具有交替的a，但在其他方面具有不同的字符，如

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

匹配数为(m/2)*(n/2)。如果你想找到它们，你的算法最多可以是O(mn)。

您可以在O(mn)时间内执行以下操作。想象一下，像这样滑动一个阵列经过另一个阵列：

[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]

有m + n - 1可能的位置。对于每个位置，您必须迭代对齐的字符对（这些字符对中最坏的是min(m, n)），并找到匹配字符的最长链。这具有时间复杂性

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

这种解决方案的缺点是所花费的时间实际上只取决于数组的长度，而不是内容。例如，即使数组相等，它仍然需要O(nm)时间（显然只需要O(n)时间来检查并返回一个答案）。如另一个答案所示，如果匹配序列的数量较少，则有更聪明的解决方案将花费更少的时间。

这是两个字符串A和B的O（n）O（n+k）解，它们的长度和为n，并且有k个这样的最大匹配子字符串：

  1. 在两个字符串A和B上构建一个通用后缀树。（这只是单个字符串A$B#上的一个普通后缀树，其中$和#是在A或B中任何地方都不会出现的单个字符。）这可以使用例如Ukkonen算法在O（n）时间内完成
  2. 通过该树执行自下而上的DFS，在每个节点执行两件事：
    • 确定并记录此节点下是否有与后缀A相对应的任何叶，以及此节点下方是否有与前缀B相对应的任意叶。（练习：如何回答一片叶子的这个问题？）
    • 如果这两种类型的叶子都存在，和这对任何子节点都不成立，那么将与该节点对应的子字符串报告为解决方案。（如果条件也适用于某个子节点，则与该节点相对应的子字符串是与该子节点相对应子字符串的子字符串，并且您只需要最大子字符串。）

这也适用于数量>=3的小字符串：计算并存储当前节点下具有叶子的输入字符串的集，并在该集满时"激发"。

相关文章：