比較五個不同的來源

我需要編寫一個函數來比較2-5個「文件」（實際上2-5組數據庫行，但類似的概念），我不知道如何去做。由此產生的差異應該呈現2-5個文件並排。輸出應顯示添加，刪除，更改和未更改的行，每個文件都有一列。比較五個不同的來源

我應該使用什麼算法遍歷行，從而保持低複雜度？每個文件的行數少於10,000。由於總數據大小在兆字節範圍內，因此我可能不需要External Merge。簡單易讀的代碼當然也很好，但這不是必須的。

編輯：這些文件可能來源於某些未知來源，沒有其他1-4文件可以與之比較的「原始」所有文件都必須以某種方式與其他人進行比較。

編輯2：我或者更確切地說是我的同事意識到可以對內容進行排序，因爲輸出順序是不相關的。這個解決方案意味着在這部分應用程序中使用額外的領域知識，但是差異複雜度是O（N）和較不復雜的代碼。這個解決方案很簡單，當我關閉賞金時，我會忽略這個編輯的任何答案。不過，我會回答我自己的問題以供將來參考。

來源

2013-01-11 Jonas Byström

您是否對線路比較或字符級比較感興趣？也就是說，如果在一組中一行是'a，b，c'，另一組是'a，b，d'，你是否還想讓這兩行被認爲'除了c/d'一樣？或者他們是不同的記錄，因爲他們有不同的數據？ – Kaganar

@Kaganar：他們不同，但並不重要。我確定了單獨比較器中行的正交性。 –

因此，真正看到的是添加，刪除和未更改的行。（沒有'改變'的行，那麼因爲他們會被視爲添加。）另外，給定「編輯2」你想要的是一種模糊。通過大多數定義，一組數據庫行是無序的，解決您的問題的方法是重新排序和比較。另一種方法是使用散列進行比較，然後在集合中顯示相似的行。但是，這聽起來不像是你的原始問題的核心 - 你是否真的想要以行間依賴的方式比較行的行數？ – Kaganar

如果所有的Ñ文件（其中2 < = n < = 5爲例）必須與其他人進行比較，那麼在我看來，比較組合的數量將是C（n,2），由在Python中，例如）：

def C(n,k): 
    return math.factorial(n)/(math.factorial(k)*math.factorial(n-k))

因此，你將有1，3,6或10的成對比較，用於分別Ñ = 2，3，4，5。

的時間複雜度將被C（Ñ，2）成對DIFF算法選擇使用，這將是一個預期O（ND）的次數的複雜性，在Myers'算法的情況下，其中N是要比較的兩個序列長度的總和，A和B，D是A和B的最小編輯腳本的大小。

我不確定環境你需要這個代碼，但difflib在Python中，作爲一個例子，可以用來找到各種序列之間的差異 - 不只是文本行 - 所以它可能是對你有用。 difflib文檔沒有說明它使用什麼算法，但它對時間複雜度的討論使我認爲它與Myers相似。（編輯2）

來源

2013-01-15 04:17:36 Simon

我還發現[這個python]（https://github.com/paulgb/simplediff/blob/master/python/simplediff/__init__.py）的實現，我將試驗並嘗試擁抱你的建議理論。謝謝！ –

看看這篇文章。細節出比較2個數據源與所述陷阱

[http://www.codeproject.com/Articles/30102/Comparing-DataSets-using-LINQ][1]

來源

2013-01-14 15:52:01 user1974729

我需要比較兩個以上的數據源。 –

僞代碼：

10: stored cells = <empty list> 
for each column: 
    if cell < stored cells: 
    stored cells = cell 
    elif cell == lastCell: 
    stored cells += cell 

if stored cells == <empty>: 
    return result 
result += stored cells 
goto 10

來源

2013-01-15 15:00:43

的2個文件中的情況下，可以用標準的diff算法來解決。你從3個文件可以用「多數表決」的算法：

如果一半以上的記錄是相同的：2出3,3出4,3出5比這些都是需要考慮的參考其他記錄發生變化。

這也意味着如果改變的次數相對較少，算法會大大加快速度。

Pseudocode: 
    initialize as many line indexes as there are files 
    while there are still at least 3 indexes incrementable 
    if all indexed records are the same 
     increment all line indexes 
    else 
     if at least one is different - check majority vote 
     if there is a majority 
     mark minority changes, increment all line indexes 
     else 
     mark minority additions (maybe randomly deciding e.g. in a 2:2 vote) 
     check addition or removing and set line indexes accordingly 
     increment all indexes 
     endif 
    endif 
    endwhile

來源

2013-02-10 09:11:50

比較五個不同的來源

回答

相關問題