用於匹配整數數組（指紋）的算法

參考：

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

用於匹配整數數組（指紋）的算法

回答

相關問題