Kann diff an seinem eigenen Spiel geschlagen werden?

Question

Ich suche nach dem entsprechenden Algorithmus vergleichen zwei Dateien zu verwenden. Ich glaube, ich kann wegen einiger zusätzlichen Einschränkungen als diff besser.

Was ich habe, sind zwei Textdateien, die jeweils eine Liste von Dateien enthält. Sie sind Schnappschüsse aller Dateien auf einem System zu zwei verschiedenen Zeiten genommen. Ich möchte herausfinden, welche Dateien wurden zwischen den beiden Snapshots hinzugefügt oder gelöscht werden.

Ich kann diff verwenden, um diese Dateien zu vergleichen, aber ich will nicht, weil:

1. diff versucht, Gruppe ändert sich zusammen, Feststellung, die in einer Datei Brocken haben sich geändert. Ich suche nur für eine Liste von Linien, die sich geändert haben, und das sollte ein viel einfacheres Problem als die längste-Common-Subsequenz oder eine solche Sache zu finden.

2. Generalized diff Algorithmen sind O (mn) in Laufzeit oder Raum. Ich suche nach etwas mehr wie O (m + n) in der Zeit und O (1) im Raum.

Hier sind die Einschränkungen für das Problem:

1. Die Dateilisten in derselben Reihenfolge in beiden Dateien sind. Sie sind nicht unbedingt in alphabetischer Reihenfolge, aber sie sind in der gleichen relativ um.

2. Die meiste Zeit gibt es keine Unterschiede zwischen den Listen sein. Wenn es Unterschiede gibt, wird es in der Regel nur eine Handvoll neuer / gelöschte Dateien sein.

3. Ich brauche nicht zu einer Gruppe zusammen die Ergebnisse, wie wenn man sagt „das gesamte Verzeichnis wurde gelöscht“ oder „Linien 100-200 neu sind“. Ich kann individuell jede Zeile auflisten, die anders ist.

Ich denke, dies zu dem Problem, zwei sortierten Listen gleichwertig ist und versucht, die Unterschiede zwischen den beiden Listen, um herauszufinden. Der Haken ist die Listenelemente sind nicht unbedingt alphabetisch sortiert, so dass Sie nicht wissen, ob ein Element „größer“ als der andere ist. Sie müssen nur wissen, dass die Dateien, die in beiden Listen vorhanden sind, in der gleichen Reihenfolge sein werden.

Für das, was es wert ist, ich vorher diese Frage gepostet auf < a href = "http://ask.metafilter.com/" rel = "noreferrer"> vor einigen Jahren Metafilter Frage. Erlauben Sie mir, mehrere mögliche Antworten zu reagieren Voraus.

Antwort: Dieses Problem genannt wird, Längste gemeinsame Subsequence .

Antwort: Ich versuche, die längste gemeinsame Teilfolge, weil einfache Algorithmen laufen in O (mn) Zeit / Raum und besseren ist kompliziert und mehr „heuristisch zu vermeiden “. Meine Intuition sagt mir, dass es eine lineare Zeit Algorithmus aufgrund der zusätzlichen Einschränkungen.

Antwort:. sortieren sie alphabetisch und dann vergleichen

Antwort: Das wäre O (m log m + n log n) , das ist schlimmer als O (m + n) .

Answer 1

Das ist nicht ganz O(1) Speicher, der Speicherbedarf in der Reihenfolge der Anzahl der Änderungen, aber es ist O(m+n) Laufzeit.

Es ist im Wesentlichen ein gepufferte Streaming-Algorithmus, den die Differenz aller bisherigen Linien zu einem bestimmten Zeile kennt.

// 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

Diese stützt sich stark auf der Tatsache, die die Dateien in der gleichen relativen Reihenfolge aufgeführt sind. Andernfalls wäre der Speicherbedarf viel größer als die Anzahl der Änderungen. Doch aufgrund dieser Anordnung soll dieser Algorithmus nicht viel mehr Speicherplatz als 2 * numChanges.

Answer 2

Lesen einer Datei, indem jede Datei-Namen in eine HashSet -ähnlichen Datenstruktur mit O(1) add und O(1) enthält Implementierungen.

Dann die Sekunden Datei lesen, jede Datei-Namen gegen die HashSet überprüfen.

Insgesamt Algorithmus, wenn die Datei eine Länge m hat und die zweite Dateilänge n hat, wird O(m+n) nach Bedarf.

Hinweis: Dieser Algorithmus nimmt das Daten-Set bequem im physischen Speicher paßt, schnell sein

.

Wenn der Datensatz nicht so leicht in dem Speicher passen kann, könnte die Suche mit einiger Variation eines B-Baum mit Festplatte auslagert. Die Komplexität würde dann vergleichen für jede andere Datei zunächst Setup und O(mlog m) O(n log m) werden.

Answer 3

Aus theoretischer Sicht Vergleichen die Bearbeitung Abstand zwischen zwei Strings (weil hier Sie Strings in einer lustigen Sprache, wo ein ‚Charakter‘ ist ein Dateiname) kann nicht O (m + n) hergestellt werden. Aber hier haben wir Vereinfachungen.

Eine Implementierung eines Algorithmus in Ihrem Fall (sollte Fehler enthalten):

# 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

Es gibt Datenstrukturen, die ich schnell Arrays nennen - sie sind wahrscheinlich HashSet Dinge, aber diejenigen, die Bestellung zu erinnern. Die Zugabe und das Nachschlagen in ihnen sollen O(log N) werden, aber die Speichernutzung O(N).

Diese verwenden keine Speicher oder Zyklen über O(m+n) außerhalb Unterschiede zu finden. Für jeden ‚Differenzblock‘ - der Vorgang, wie Wegnehmen M consequtive Artikel und das Hinzufügen von N diejenigen beschrieben werden kann - dies dauert O(M+N) Speicher und O(MN) O(Mlog N+Nlog M) Anweisungen. Der Speicher freigegeben wird, nachdem ein Block durchgeführt wird, so ist dies nicht viel von einer Sache, wenn Sie in die Tat nur kleine Änderungen haben. Natürlich ist die Worst-Case-Leistung so schlecht, wie mit generischer Methode.

Answer 4

In der Praxis ist ein Log-Faktor Unterschied in Sortier mal wahrscheinlich unbedeutend - sort Hunderttausende von Linien in wenigen Sekunden sortieren. So brauchen Sie nicht eigentlich keinen Code schreiben:

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

Ich behaupte nicht, dass dies unbedingt die schnellste Lösung - ich glaube, Ben S die akzeptierte Antwort wird über einem bestimmten Wert von N sein, zumindest aber es ist definitiv die einfachste, wird es auf eine beliebige Anzahl von Dateien skalieren, und (es sei denn, Sie sind der Mann verantwortlich die Sicherungsoperation Google) wird es als schnell genug, um mehr sein für die Anzahl der Dateien, die Sie haben.

Answer 5

Wenn Sie akzeptieren, dass Wörterbücher (Hash-Karten) ist O (n) Raum und O (1) einfügen / Lookup, diese Lösung sollte O (m + n) in Zeit und Raum sein.

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

Okay, leichte Betrug als list.append und list.__delitem__ ist nur O (1), wenn sie verkettete Listen sind, die nicht wirklich wahr ist ... aber das ist die Idee, irgendwie.

Answer 6

Eine Verfeinerung ephemient Antwort, diese verwendet nur zusätzliche Speicher, wenn es Änderungen.

def diff(left, right):
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if left[i] == right[j]:
            print '=', left[i], right[j]
            i, j = i+1, j+1
            continue

        old_i, old_j = i, j
        left_set, right_set = set(), set()

        while i < len(left) or j < len(right):
            if i < len(left) and left[i] in right_set:
                for i2 in range(old_i, i): print '<', left[i2]
                j = old_j
                break

            elif j < len(right) and right[j] in left_set:
                for j2 in range(old_j, j): print '>', right[j2]
                i = old_i
                break

            else:
                left_set .add(left [i])
                right_set.add(right[j])
                i, j = i+1, j+1

    while i < len(left):
        print '<', left[i]
        i = i+1

    while j < len(right):
        print '>', right[j]
        j = j+1

Kommentare? Verbesserungen?

Answer 7

Ich habe nach einem Programm gewesen, große Dateien diff ohne aus dem Speicher ausgeführt wird, aber nichts gefunden meine Zwecke zu passen. Ich bin die Diffs in Verwendung für das Patchen nicht interessiert (dann würde ich wahrscheinlich rdiff von librdiff verwenden), sondern auch für visuell die diffs Inspektion, vielleicht sie in Wort-diffs mit dwdiff --diff-input drehen (was das Standard-Diff Format liest) und vielleicht das Sammeln das Wort diffs irgendwie.

(Mein typischer Anwendungsfall:. Ich einige NLP-Tool, das ich verwende einen großen Textkorpus zu verarbeiten Ich betreibe es einmal, eine Datei, die 122.760.246 Zeilen lang ist, mache ich eine Änderung an mein Werkzeug, führen Sie es wieder, erhalten eine Datei, die wie alle Millionen Zeilen, vielleicht zwei Einfügungen und eine Deletion, oder nur eine Zeile, so etwas unterscheidet unterscheidet.)

Da ich nichts finden konnte, habe ich nur ein kleines Skript https: // GitHub. com / unhammer / diff-large-Dateien - es funktioniert (dwdiff es als Eingabe akzeptiert), es ist schnell genug (schneller als der xZ-Prozess, der in der Pipeline, nachdem es läuft oft), und vor allem macht es nicht läuft aus dem Speicher.

Answer 8

Ich würde die Liste der Dateien in zwei Sätze lesen und diese Dateinamen, die auf beiden Listen eindeutig sind.

In Python, so etwas wie:

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)))