用于匹配整数数组（指纹）的算法

参考：

00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

候选人：

FF FF FF 01 02 03 FF AA 09 0A 0B 0C 0D 0E FF

所需的输出：

01 02 03 09 0A 0B 0C 0D 0E

//澄清我感兴趣的是找到连续两场比赛。在现实世界的例子中，将会出现很多奇异匹配（噪声），可能还有1到3个更大的群集。

引用和候选是文本的近似值（指纹）（如书）。小范围的比赛毫无意义。指纹内的值是K-Grams的散列值，因此值不是唯一的。

来源

2014-10-16 Lukasz Kujawa

都是总是排序顺序或增加/减少顺序？ – luisluix 2014-10-16 22:46:39

哦，对不起，这个例子可能会让人困惑。序列从不排序。 – 2014-10-16 22:52:41

这实际上是差异所做的（只需用您的8位令牌替换行）http://en.wikipedia.org/wiki/Diff_utility有很多启发式方法来处理*性能良好的*案例。 – wildplasser 2014-10-16 23:03:32

看起来像你需要的是两个列表中的Longest Common Subsequence。

来源

2014-10-16 22:41:57 MAK

只需从其中一个开始即可。弹出一个值，将它与其他数组值逐个比较，直到它结束。并弹出另一个值来检查，等等......！

来源

2014-10-16 22:43:20 Angel

因为两个序列都没有排序，所以你必须单独检查每个值。这将java代码给你所需的输出：

for(int i=0;i<array2.length();i++) 
{ 
    for(int j=0;j<array1.length();j++) 
    { 
     if(array1[j].equals(array2[i]) 
     { 
      System.out.println(array2[i]+" "); 
     } 
    } 
}

来源

2014-10-16 23:00:23 luisluix

注意：如果您的评论说，阵列从未排序。我将这意味着你不是在寻找最长的公共子序列，而只是想确定候选数组中的哪些元素也出现在参考数组中，而不管其顺序如何（即一组交集）（）。如果这是不正确的，请澄清这个问题！

您可以在O（n + m）时间内完成此操作，其中n和m是列表的长度。这比通过第一个列表并检查每个元素是否包含在第二个列表中的幼稚方法要快得多。

我假设，从你的例子，你的参考数组不包含重复。如果它有处理这个问题的方法，但是它并不完全清楚你想要输出结果的样子。

建立一个位字段，这是一个数据结构，告诉你是否存在任何给定的元素，并且它用一个位表示每个可能的元素。因此，您可以使用一个int来表示32个不同的输入/输出值。有一个Apache Commons实现可用，您可以直接使用。

解决问题的方法是通过参考数组，将它的每个元素放入位域。完成此操作后，您实际上有一个Set，您可以通过查看是否在位域中设置其位，来测试任何给定值是否位于参考数组中。所以现在你通过你的候选数组，并且为每个元素测试它在位域中的存在。

即使可能值的范围很大，您仍然可以这样做。即使所有可能的int值都是允许的，您仍然可以在1GB内存中表示所有这些值。

从您的示例看起来好像可能值的数量很小，在这种情况下，您可以更简单地执行此操作，并且还可以处理重复项，只需使用int[]数组，每个可能的值为一个。因此，如果值的范围是0到999，那么你声明

int[] present = new int[1000];

，然后你通过你的参考阵列：

for (int ref: refArray) 
    present[ref]++;

现在你有每个值的出现次数的计数在你的present阵列中。你通过你的候选阵列，并期待，为每一个，有多少次是在present数组中：

for (int cand: candidateArray) 
    if (present[cand]>0) 
     System.out.println(cand+" occurred "+present[cand]+" times in the ref array");

如果你不引用数组中得到重复，你可以只使用一个boolean[]，当然。

这是很多快于其他建议的方式，它是O（n * m）。

来源

2014-10-16 23:08:58

感谢您的回复。你分享了一些有用的想法，但是我担心我的问题仍然令人困惑。我为此道歉。值不是唯一的。我对连续比赛的最大范围感兴趣。 – 2014-10-17 09:08:08

用于匹配整数数组（指纹）的算法

回答

相关问题