Il diff può essere battuto nel suo stesso gioco?

Question

Sto cercando l'algoritmo appropriato da utilizzare per confrontare due file. Penso di poter fare meglio di diff a causa di alcuni vincoli aggiunti.

Quello che ho sono due file di testo contenenti ciascuno un elenco di file. Sono istantanee di tutti i file su un sistema prese in due momenti diversi. Voglio capire quali file sono stati aggiunti o eliminati tra le due istantanee.

Potrei usare diff per confrontare questi file, ma non voglio perché:

1. diff tenta di raggruppare le modifiche, scoprendo quali blocchi in un file sono cambiati. Sto solo cercando un elenco di righe che sono cambiate e che dovrebbe essere un problema molto più semplice rispetto a trovare la sottosequenza comune più lunga o qualcosa del genere.

2. Gli algoritmi diff generalizzati sono O (mn) in runtime o spazio. Sto cercando qualcosa di più simile a O (m + n) nel tempo e O (1) nello spazio.

Ecco i vincoli al problema:

1. Gli elenchi dei file sono nello stesso ordine in entrambi i file. Sono non necessariamente in ordine alfabetico, ma sono nello stesso ordine relativo

2. Il più delle volte non ci saranno differenze tra gli elenchi. Se ci sono differenze, di solito ci sarà solo una manciata di file nuovi / eliminati.

3. Non ho bisogno di raggruppare i risultati insieme, come dire " l'intera directory è stata cancellata " o "le righe 100-200 sono nuove". Posso elencare individualmente ogni riga diversa.

Sto pensando che questo equivale al problema di avere due elenchi ordinati e provare a capire le differenze tra i due elenchi. Il problema è che gli elementi dell'elenco non sono necessariamente ordinati alfabeticamente, quindi non sai se un elemento è "più grande" di un altro. Sai solo che i file presenti in entrambi gli elenchi saranno nello stesso ordine.

Per quello che vale, precedentemente pubblicato questa domanda su < a href = "http://ask.metafilter.com/" rel = "noreferrer"> Chiedi a Metafilter diversi anni fa. Consentimi di rispondere in anticipo a diverse potenziali risposte.

Risposta: questo problema si chiama Seguito comune più lungo .

Risposta: Sto cercando di evitare la sottosequenza comune più lunga perché algoritmi semplici vengono eseguiti in O (mn) tempo / spazio e quelli migliori sono complicati e altro " heuristical " ;. La mia intuizione mi dice che esiste un algoritmo a tempo lineare a causa dei vincoli aggiunti.

Risposta: ordinali in ordine alfabetico e poi confronta.

Risposta: sarebbe O (m log m + n log n) , che è peggio di O (m + n) .

Answer 1

Questa non è abbastanza memoria O (1) , il requisito di memoria nell'ordine del numero di modifiche, ma è il tempo di esecuzione O (m + n) .

È essenzialmente un algoritmo di streaming bufferizzato che in una determinata riga conosce la differenza di tutte le righe precedenti.

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

Questo dipende fortemente dal fatto che i file sono elencati nello stesso ordine relativo. Altrimenti, il requisito di memoria sarebbe molto più grande del numero di modifiche. Tuttavia, a causa di questo ordinamento questo algoritmo non dovrebbe usare molta più memoria di 2 * numChanges.

Answer 2

Leggi un file, posizionando ciascun nome file in un Struttura dei dati simile a HashSet con O (1) add e O (1) contiene implementazioni.

Quindi leggi il file dei secondi, controllando ogni nome di file con l'HashSet.

Algoritmo totale se il file uno ha lunghezza m e il secondo file ha lunghezza n è O (m + n) come richiesto.

Nota: questo algoritmo presuppone che il set di dati si adatti comodamente alla memoria fisica per essere veloce.

Se il set di dati non si adatta facilmente alla memoria, la ricerca potrebbe essere implementata utilizzando una variante di B-Tree con paging del disco. La complessità sarebbe quindi O (mlog m) da configurare inizialmente e O (n log m) per ogni altro confronto di file.

Answer 3

Da un punto di vista teorico, non è possibile creare O (m + n) confrontando la distanza di modifica tra due stringhe (perché qui si hanno stringhe in un linguaggio divertente in cui un 'carattere' è un nome di file). Ma qui abbiamo semplificazioni.

Un'implementazione di un algoritmo nel tuo caso (dovrebbe contenere errori):

# 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

Ci sono strutture di dati che chiamo array veloci - probabilmente sono cose HashSet , ma quelle che ricordano l'ordinamento. L'aggiunta e la ricerca in essi dovrebbero essere O (log N) , ma la memoria usa O (N) .

Non utilizza memoria o cicli oltre O (m + n) al di fuori della ricerca di differenze. Per ogni 'blocco differenza' - l'operazione che può essere descritta come rimozione di M elementi consequtivi e aggiunta di N elementi - questo richiede O (M + N) memoria e O (MN) O (Mlog N + Nlog M) . La memoria viene rilasciata al termine di un blocco, quindi non è una gran cosa se si hanno solo piccole modifiche. Naturalmente, le prestazioni nel caso peggiore sono peggiori come con il metodo generico.

Answer 4

In pratica, una differenza del fattore di registro nei tempi di ordinamento è probabilmente insignificante - sort può ordinare centinaia di migliaia di righe in pochi secondi. Quindi in realtà non è necessario scrivere alcun codice:

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

Non sto affermando che questa sia necessariamente la soluzione più veloce - penso La risposta accettata da Ben S sarà, almeno al di sopra del valore di N. Ma è sicuramente la più semplice, si ridimensionerà su qualsiasi numero di file e (a meno che tu non sia il responsabile dell'operazione di backup di Google) sarà più che abbastanza veloce per il numero di file che hai.

Answer 5

Se accetti che i dizionari (mappe hash) siano O (n) spazio e O (1) inserisci / cerca, questa soluzione dovrebbe essere O (m + n) sia nel tempo che nello spazio.

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

Ok, un leggero imbroglio come list.append e list .__ delitem__ sono solo O (1) se sono elenchi collegati, il che non è proprio vero .. ma questa è l'idea, comunque.

Answer 6

Un perfezionamento della risposta effimera, questa utilizza memoria aggiuntiva solo quando ci sono cambiamenti.

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

Commenti? Miglioramenti?

Answer 7

Ho cercato un programma per diffondere file di grandi dimensioni senza esaurire la memoria, ma non ho trovato nulla adatto ai miei scopi. Non mi interessa usare i diff per il patching (quindi probabilmente userei rdiff da librdiff), ma per ispezionare visivamente i diff, magari trasformandoli in word diff con dwdiff - -diff-input (che legge il formato diff unificato) e forse raccoglie in qualche modo le diff-word.

(Il mio caso d'uso tipico: ho alcuni strumenti NLP che utilizzo per elaborare un corpus di testo di grandi dimensioni. Lo eseguo una volta, ottengo un file lungo 122760246 righe, apporto una modifica al mio strumento, lo eseguo di nuovo, ottengo un file che differisce come ogni milione di righe, forse due inserzioni e una cancellazione, o solo una riga differisce, quel tipo di cose.)

Dato che non sono riuscito a trovare nulla, ho appena realizzato un piccolo script https: // github. com / unhammer / diff-large-files - funziona (dwdiff lo accetta come input), è abbastanza veloce (più veloce del processo xz che spesso viene eseguito nella pipeline) e, cosa più importante, non funziona esaurire la memoria.

Answer 8

Leggerei gli elenchi di file in due set e troverei quei nomi di file che sono unici per entrambi gli elenchi.

In Python, qualcosa del tipo:

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