3

2〜5個の「ファイル」（実際には2〜5セットのデータベース行ですが、同様の概念）を比較する関数を作成する必要がありますが、その方法がわかりません。結果の差分は、2〜5個のファイルを並べて表示する必要があります。出力には、追加、削除、変更、および変更されていない行と、各ファイルの列が表示されます。

複雑さを低く抑えるために、行をトラバースするにはどのアルゴリズムを使用する必要がありますか？ファイルあたりの行数は10,000未満です。合計データサイズはメガバイトの範囲であるため、おそらく外部マージは必要ありません。もちろん、シンプルで読みやすいコードもいいでしょうが、必須ではありません。

編集：ファイルは未知のソースから派生している可能性があり、他の1〜4個のファイルと比較できる「オリジナル」はありません。すべてのファイルは、何らかの方法で他のファイルと比較する必要があります。

編集2：私、またはむしろ私の同僚は、出力順序が無関係であるため、コンテンツがソートされる可能性があることに気づきました。このソリューションは、アプリケーションのこの部分に追加のドメイン知識を使用することを意味しますが、diffの複雑さはO（N）であり、コードはそれほど複雑ではありません。この解決策は単純であり、バウンティを閉じるときにこの編集に対する回答は無視します。しかし、私は将来の参考のために私自身の質問に答えます。

4

3 に答える 3

2

n個のファイルすべて（例では2 <= n <= 5）を他のファイルと比較する必要がある場合、比較する組み合わせの数はC（n、2）であり、次のように定義されます。 （たとえば、Pythonの場合）次のようになります。

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

したがって、 n = 2、3、4、5の場合、それぞれ1、3、6、または10のペアワイズ比較が行われます。

その場合、時間計算量は、使用することを選択したペアワイズ差分アルゴリズムの複雑さのC（n、2）倍になります。これは、マイヤーズのアルゴリズムの場合、予想されるO（ND）になります。ここで、Nは比較する2つのシーケンスAとBの長さ、およびDはAとBの最小編集スクリプトのサイズです。

このコードが必要な環境についてはわかりませんが、例として、Pythonのdifflibを使用して、テキスト行だけでなく、あらゆる種類のシーケンス間の違いを見つけることができるので、役立つ場合があります。ドキュメントには、使用するアルゴリズムが正確に記載difflibされていませんが、時間計算量についての説明から、マイヤーズに似ていると思います。

于 2013-01-15T04:17:36.623 に答える
1

擬似コード（編集2用）：

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-15T15:00:43.183 に答える
0

2つのファイルの場合は、標準のdiffアルゴリズムで解決できます。上の3つのファイルから、「多数決」アルゴリズムを使用できます。

レコードの半分以上が同じである場合：3つのうち2つ、4つのうち3つ、5つのうち3つは、他のレコードが変更されたと見なすための参照です。

また、これは、変更の数が比較的少ない場合、アルゴリズムの大幅な高速化を意味します。

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-10T09:11:50.320 に答える