algorithm - diff は独自のゲームで打ち負かすことができますか?

Question

2 つのファイルを比較するために使用する適切なアルゴリズムを探しています。diffいくつかの制約が追加されたため、より良いことができると思います。

私が持っているのは、それぞれファイルのリストを含む 2 つのテキスト ファイルです。これらは、2 つの異なる時点で取得された、システム上のすべてのファイルのスナップショットです。2 つのスナップショット間で追加または削除されたファイルを特定したいと考えています。

これらのファイルを比較するために使用できますdiffが、次の理由により使用しません。

1. diffファイル内のどのチャンクが変更されたかを見つけて、変更をグループ化しようとします。変更された行のリストを探しているだけで、最長共通部分列などを見つけるよりもはるかに簡単な問題になるはずです。

2. 一般化された差分アルゴリズムは、実行時または空間でO(mn)です。時間でO(m+n) 、空間でO(1)のようなものを探しています。

問題の制約は次のとおりです。

1. ファイルのリストは、両方のファイルで同じ順序になっています。必ずしもアルファベット順ではありませんが、相対的な順序は同じです。

2. ほとんどの場合、リスト間に違いはありません。違いがある場合、通常、新規/削除されたファイルはほんの一握りです。

3. 「このディレクトリ全体が削除されました」や「100 ～ 200 行が新しい」など、結果をグループ化する必要はありません。異なる各行を個別にリストできます。

これは、並べ替えられた 2 つのリストがあり、2 つのリストの違いを見つけようとする問題と同じだと思います。問題は、リスト項目が必ずしもアルファベット順にソートされているとは限らないため、ある項目が別の項目より「大きい」かどうかわからないことです。両方のリストに存在するファイルが同じ順序になることがわかっているだけです。

参考までに、数年前にこの質問をAsk Metafilterに投稿しました。事前にいくつかの潜在的な回答に回答させてください.

回答:この問題はLongest Common Subsequenceと呼ばれます。

応答:単純なアルゴリズムはO(mn)時間/空間で実行され、より優れたアルゴリズムは複雑で「ヒューリスティック」であるため、最長の一般的なサブシーケンスを回避しようとしています。私の直感では、追加された制約により線形時間アルゴリズムが存在することがわかります。

答え:アルファベット順に並べ替えてから比較してください。

応答:それはO(m log m+n log n)になり、 O(m+n)よりも悪くなります。

Answer 1

1 つのファイルを読み取り、各ファイル名をHashSetのようなデータ構造に配置し、O(1)add およびO(1)contains 実装を使用します。

次に、秒ファイルを読み取り、各ファイル名を HashSet と照合します。

mファイル 1 に長さがあり、2 番目のファイルに長さがある場合の合計アルゴリズムnはO(m+n)、必要に応じて異なります。

注: このアルゴリズムは、データセットが高速で物理メモリに快適に収まることを前提としています。

データ セットが簡単にメモリに収まらない場合は、ディスク ページングを使用したB ツリーのバリエーションを使用してルックアップを実装できます。複雑なのは、O(mlog m)最初のセットアップとO(n log m)、他のファイルの比較です。

Answer 2

これは完全O(1)なメモリではなく、変更の数の順序でのメモリ要件ですが、O(m+n)ランタイムです。

これは基本的に、任意の行で以前のすべての行の違いを認識しているバッファリングされたストリーミング アルゴリズムです。

// Pseudo-code:
initialize HashMap<Line, SourceFile> changes = new empty HashMap
while (lines left in A and B) {
    read in lineA from file A
    read in lineB from file B

    if (lineA.equals(lineB)) continue

    if (changes.contains(lineA) && changes.get(lineA).SourceFile != A) {
         changes.remove(lineA)
    } else {
         changes.add(lineA, A)
    }

    if (changes.contains(lineB) && changes.get(lineB).SourceFile != B) {
         changes.remove(lineB)
    } else {
         changes.add(lineB, B)
    }
}

for each (line in longerFile) {
    if (changes.contains(line) && changes.get(line).SourceFile != longerFile) {
         changes.remove(line)
    } else {
         changes.add(line, longerFile)
    }
}

Lines in the HashMap from SourceFile == A have been removed
Lines in the HashMap from SourceFile == B have been added

これは、ファイルが同じ相対的な順序でリストされているという事実に大きく依存しています。そうしないと、メモリ要件が変更の数よりもはるかに大きくなります。ただし、その順序により、このアルゴリズムは 2 * numChanges より多くのメモリを使用するべきではありません。

Answer 3

実際には、ソート時間の対数係数の違いはおそらく重要sortではなく、数秒で数十万行をソートできます。したがって、実際にコードを記述する必要はありません。

sort filelist1 > filelist1.sorted
sort filelist2 > filelist2.sorted
comm -3 filelist1.sorted filelist2.sorted > changes

これが必ずしも最速の解決策であると主張しているわけではありません.Ben Sの受け入れられた答えは、少なくともNの値を超えると思います.しかし、それは間違いなく最も単純であり、任意の数のファイルにスケーリングします.は、Google のバックアップ オペレーションの担当者です)、持っているファイルの数に対して十分に高速です。

Answer 4

理論的な観点から、2 つの文字列間の編集距離を比較する (ここでは、「文字」がファイル名である面白い言語の文字列があるため) O(m+n) にすることはできません。しかし、ここでは単純化しています。

あなたの場合のアルゴリズムの実装（間違いを含むはずです）：

# i[0], i[1] are undoable iterables; at the end they both return Null

while (a = i[0].next()) && (b = i[1].next()) :    # read one item from each stream
    if a != b:                 # skip if they are identical
        c = [[a],[b]]          # otherwise, prepare two fast arrays to store difference
        for (w = 1; ; w = 1-w) # and read from one stream at a time
             nxi = Null        
             if (nx = i[1-w].next()) in c[w]:  # if we read a new character that matches
                  nxi = c[w].index(nx)          
             if nx is Null: nxi = -1           # or if we read end of stream
             if nxi is not Null:               # then output that we found some diff
                 for cc in c[1-w]: yield cc              # the ones stored 
                 for cc in c[w][0:nxi-1]: yield cc       # and the ones stored before nx
                 for cc in c[w][nxi+1:]: i[w].undo(cc)   # about the remainder - put it back
                 break                         # and return back to normal cycle
 # one of them finished
 if a: yield a
 if b: yield b
 for ci in i: 
     while (cc = ci.next()): yield cc

私が高速配列と呼んでいるデータ構造があります。それらはおそらくHashSetモノですが、順序を覚えているものです。それらの加算とルックアップは である必要がありますO(log N)が、メモリ使用量はO(N).

O(m+n)これは、違いを見つける以外にメモリやサイクルを使用しません。すべての「差分ブロック」 (M 個の連続する項目を削除し、N 個の項目を追加することとして説明できる操作) ごとに、O(M+N)メモリと命令が必要です。ブロックが完了した後にメモリが解放されるため、実際に小さな変更しかない場合、これは大したことではありません。もちろん、最悪の場合のパフォーマンスはジェネリック メソッドと同じくらい悪くなります。O(MN) O(Mlog N+Nlog M)

Answer 5

辞書 (ハッシュ マップ) が O(n) 空間であり、O(1) 挿入/ルックアップであることを受け入れる場合、このソリューションは時間と空間の両方で O(m+n) になるはずです。

from collections import defaultdict
def diff(left, right):
    left_map, right_map = defaultdict(list), defaultdict(list)
    for index, object in enumerate(left): left_map[object] += [index]
    for index, object in enumerate(right): right_map[object] += [index]
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left_map[right[j]]:
            i2 = left_map[right[j]].pop(0)
            if i2 < i: continue
            del right_map[right[j]][0]
            for i in range(i, i2): print '<', left[i]
            print '=', left[i2], right[j]
            i, j = i2 + 1, j + 1
        elif right_map[left[i]]:
            j2 = right_map[left[i]].pop(0)
            if j2 < j: continue
            del left_map[left[i]][0]
            for j in range(j, j2): print '>', right[j]
            print '=', left[i], right[j2]
            i, j = i + 1, j2 + 1
        else:
            print '<', left[i]
            i = i + 1
    for j in range(j, len(right)): print '>', right[j]

>>> diff([1, 2, 1, 1, 3, 5, 2, 9],
... [ 2, 1, 3, 6, 5, 2, 8, 9])
< 1
= 2 2
= 1 1
< 1
= 3 3
> 6
= 5 5
= 2 2
> 8
= 9 9

わかりました、list.appendとlist.__delitem__がリンクされたリストの場合は O(1) だけです。

Answer 6

メモリを使い果たすことなく大きなファイルを比較するプログラムを探していましたが、目的に合ったものは何も見つかりませんでした。差分をパッチ適用に使用することに興味はありませんが (その後、おそらくrdifflibrdiff から使用します)、差分を視覚的に検査するために、dwdiff --diff-input(統一された差分形式を読み取る) を使用して単語差分に変換し、おそらく単語を収集します。 - どういうわけか違います。

(私の典型的な使用例: 大きなテキスト コーパスを処理するために使用する NLP ツールがあります。一度実行すると、122760246 行の長さのファイルが取得されます。ツールに変更を加え、再度実行すると、次のファイルが取得されます。 100 万行ごとに異なります。おそらく 2 つの挿入と削除、または 1 行だけの違いなどです。)

何も見つからなかったので、小さなスクリプトhttps://github.com/unhammer/diff-large-filesを作成しました。動作します (dwdiff は入力として受け入れます)。十分に高速です (xz プロセスよりも高速です)。多くの場合、パイプラインでその後に実行されます)、そして最も重要なのは、メモリ不足にならないことです。

Answer 7

ファイルのリストを 2 つのセットに読み取り、どちらのリストにも固有のファイル名を見つけます。

Python では、次のようになります。

files1 = set(line.strip() for line in open('list1.txt'))
files2 = set(line.strip() for line in open('list2.txt'))
print('\n'.join(files1.symmetric_difference(files2)))