求全部對，在恰好一個位置上不同

我需要表示與下面的非規範操作一組序列（全部相同，已知，長度）的數據結構序列：求全部對，在恰好一個位置上不同

找到兩個恰好在一個索引處不同的序列。（或建立，沒有這樣的一對的存在。）

如果N是序列的數目，有一個明顯的O(N*M*M)算法對序列並M的長度。我想知道是否有更高效地解決這個問題的標準方法。如果需要，我願意應用預處理。

獎勵分數如果不是返回一對，算法會返回所有序列，這些序列在同一點上有所不同。

備選地，我也有興趣在一個解決方案，其中，我可以有效地檢查一個特定序列是否在一個索引的不同之從在所述組的任何序列。如果有幫助，我們可以假定在該集合中，沒有兩個序列具有該屬性。

編輯：你可以假設N是相當小的。通過這個，我的意思是改進如O(log(N)*M*M)對我的用例來說並不是很有用。

來源

2013-05-02 Philippe

我們可以假設序列包含整數嗎？ – IVlad 2013-05-02 20:23:15

@IVlad是的，如果有幫助。在我的情況下，我碰巧擁有一個完美的散列函數（對於元素，而不是序列）.. – Philippe 2013-05-02 22:31:42

對於每個序列和該序列中的每個位置i，計算沒有位置i的序列的散列並將其添加到散列表。如果表中已經有一個條目，那麼您已經找到了只在一個位置上有所不同的潛在對。從開始和結束使用rolling hashes並組合它們，您可以在恆定時間內計算每個哈希值。總運行時間預計爲O（N * M）。

來源

2013-05-03 12:02:17

這正是我即將提出的建議。您也可以散列整個序列。所以每個序列S（n）將有N個部分哈希hS（i）和一個完整哈希hS。然後輸入組合散列（（hS）|（hS（i））<< hashSize）的單個散列表。對於任何測試序列，計算N散列方式相同，並在同一個散列表中查看每個散列表。 – 2013-05-03 13:00:16

每個隨機選擇j組k指數（確保沒有一組重疊）。

對於每組XOR元素。

您現在每個文檔都有j個指紋。

比較基於這些指紋的序列。如果序列確實匹配，則j-1個指紋應該匹配。但相反可能不是真實的，你可能需要按位置檢查位置。

關於比較部分的更多說明：對所有文檔中的所有指紋進行排序（或使用散列表）。這樣你就不必比較每一對，但只有那些具有匹配指紋的對。

來源

2013-05-02 15:37:21 ElKamina

如果我的'j'集合都包含序列不同的索引，那麼這些指紋都不會匹配，看起來好像？ – Philippe 2013-05-02 15:47:41

@Philippe是的。我忘了補充說，這些設置應該是相互排斥的。 – ElKamina 2013-05-02 15:51:29

好的，那可以（在統計上）改善'O（N * M * M）中的'N' ......對於很長的序列，這絕對聽起來像是一個好方法。不過，我希望能改善二次因子。爲了清晰起見，將編輯 – Philippe 2013-05-02 16:05:55

一個簡單的遞歸方法：

查找，通過排序或哈希具有相同的前半序列的所有集。
對於這些組中的每一組，重複整個過程，現在只查看下半部分。
通過排序或哈希查找所有具有相同後半部分的序列集合。
對於這些組中的每一組，重複整個過程，現在只查看前半部分。
當您達到長度1時，所有不匹配的都是您要查找的內容。

僞代碼：

findPairs(1, N) 

findPairs(set, start, end) 
    mid = (start + end)/2 
    sort set according to start and mid indices 
    if end - start == 1 
    last = '' 
    for each seq: set 
     if last != '' and seq != last 
     DONE - PAIR FOUND 
     last = seq 
    else 
    newSet = {} 
    last = '' 
    for each seq: set 
     if newSet.length > 1 and seq and last don't match from start to mid indices 
     findPairs(newSet, mid, end) 
     newSet = {} 
     newSet += seq 
     last = seq

它應該很容易修改代碼，以便能夠找到所有對。

複雜性？我可能是錯的，但是：

最大深度爲log M。（我相信）最糟糕的情況是，如果所有的序列都是相同的。在這種情況下，完成的工作將是O(N*M*log M*log M)，這比O(N*M*M)好。

來源

2013-05-02 20:24:37 Dukeling

求全部對，在恰好一個位置上不同

回答

相關問題