Est-ce que diff peut être battu à son propre jeu?

Question

Je cherche l'algorithme approprié à utiliser pour comparer deux fichiers. Je pense que je peux faire mieux que diff en raison de certaines contraintes supplémentaires.

Ce que j’ai sont deux fichiers texte contenant chacun une liste de fichiers. Ce sont des instantanés de tous les fichiers d’un système pris à deux moments différents. Je veux savoir quels fichiers ont été ajoutés ou supprimés entre les deux instantanés.

Je pourrais utiliser diff pour comparer ces fichiers, mais je ne le souhaite pas car:

1. diff tente de regrouper les modifications, en recherchant les morceaux qui ont été modifiés dans un fichier. Je cherche seulement une liste de lignes qui ont changé, et ce devrait être un problème beaucoup plus simple que de trouver la sous-séquence la plus longue commune ou une chose du genre.

2. Les algorithmes de diff généralisés sont O (mn) en mode d'exécution ou dans l'espace. Je recherche quelque chose qui ressemble davantage à O (m + n) dans le temps et à O (1) dans l'espace.

Voici les contraintes sur le problème:

1. Les listes de fichiers sont dans le même ordre dans les deux fichiers. Ils ne sont pas nécessairement dans l'ordre alphabétique, mais ils sont dans le même ordre relatif .

2. La plupart du temps, il n'y aura pas de différences entre les listes. S'il y a des différences, il n'y aura généralement qu'une poignée de fichiers nouveaux / supprimés.

3. Je n'ai pas besoin de regrouper les résultats, c'est comme dire que "tout ce répertoire a été supprimé". ou "les lignes 100 à 200 sont nouvelles". Je peux lister individuellement chaque ligne différente.

Je pense que cela équivaut au problème de disposer de deux listes triées et d'essayer de comprendre les différences entre les deux listes. Le hic est que les éléments de la liste ne sont pas nécessairement triés par ordre alphabétique, de sorte que vous ne savez pas si un élément est "supérieur". qu'un autre. Vous savez simplement que les fichiers présents dans les deux listes seront dans le même ordre.

Pour ce que cela vaut, j'ai posté précédemment cette question sur < a href = "http://ask.metafilter.com/" rel = "noreferrer"> Demandez à Metafilter il y a plusieurs années. Permettez-moi de répondre à plusieurs réponses potentielles dès le départ.

Réponse: Ce problème est appelé la plus longue sous-séquence commune . .

Réponse: j'essaie d'éviter la sous-séquence la plus longue commune, car de simples algorithmes s'exécutent dans le temps / l'espace O (mn) , et les meilleurs sont compliqués et plus complexes. " heuristique " ;. Mon intuition me dit qu’il existe un algorithme linéaire en raison des contraintes supplémentaires.

Réponse: triez-les par ordre alphabétique, puis comparez-les.

Réponse: Ce serait O (m log m + n log n) , ce qui est pire que O (m + n) .

Answer 1

Ce n'est pas tout à fait la O (1) mémoire, la mémoire requise dans l'ordre du nombre de modifications, mais son exécution est O (m + n) .

Il s’agit essentiellement d’un algorithme de diffusion en continu avec tampon qui, à une ligne donnée, connaît la différence entre toutes les lignes précédentes.

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

Cela dépend beaucoup du fait que les fichiers sont listés dans le même ordre relatif. Sinon, les besoins en mémoire seraient beaucoup plus importants que le nombre de modifications. Cependant, en raison de cet ordre, cet algorithme ne devrait pas utiliser beaucoup plus de mémoire que 2 * numChanges.

Answer 2

Lisez un fichier en plaçant chaque nom de fichier dans un Structure de données semblable à HashSet avec O (1) add et O (1) contient des implémentations.

Lisez ensuite le fichier de secondes en comparant chaque nom de fichier avec le HashSet.

Algorithme total si le fichier un a la longueur m et que le second fichier a la longueur n est O (m + n) selon les besoins.

Remarque: Cet algorithme suppose que l'ensemble de données s'adapte facilement à la mémoire physique pour être rapide.

Si le jeu de données ne parvient pas à tenir facilement dans la mémoire, la recherche pourrait être implémentée en utilisant une variante du B-Tree avec pagination de disque. La complexité serait alors O (mlog m) à configurer initialement et O (n journal m) pour chaque comparaison de fichier.

Answer 3

D'un point de vue théorique, comparer la distance d'édition entre deux chaînes (car ici, vous avez des chaînes dans une langue amusante dans laquelle un "caractère" est un nom de fichier) ne peut pas être défini sur O (m + n). Mais ici nous avons des simplifications.

Une implémentation d'un algorithme dans votre cas (doit contenir des erreurs):

# 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

Il existe des structures de données que j'appelle des tableaux rapides. Ce sont probablement des éléments HashSet , mais celles qui se souviennent de l'ordre. L’ajout et la recherche dans ces éléments doivent être O (journal N) , mais la mémoire utilise O (N) .

Ceci n'utilise pas de mémoire ni de cycles au-delà de O (m + n) en dehors de la recherche de différences. Pour chaque "bloc de différences" - l'opération qui peut être décrite comme enlever de M éléments consécutifs et en ajouter N -, cela prend O (M + N) en mémoire et O (MN) O (instructions Mlog N + Nlog M) . La mémoire est libérée après la fin d'un blocage, ce n'est donc pas un problème si vous n'avez que de petits changements. Bien entendu, les performances dans le pire des cas sont aussi mauvaises qu'avec la méthode générique.

Answer 4

En pratique, une différence de facteur de journalisation dans les délais de tri est probablement insignifiante - sort peut trier des centaines de milliers de lignes en quelques secondes. Vous n'avez donc pas besoin d'écrire de code:

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

Je ne prétends pas qu'il s'agit nécessairement de la solution la plus rapide. Je pense La réponse acceptée de Ben S sera au moins supérieure à la valeur de N. Mais c'est certainement la plus simple, elle s'adapte à un nombre quelconque de fichiers et (à moins que vous ne soyez le responsable l’opération de sauvegarde de Google), il sera suffisamment rapide pour le nombre de fichiers que vous avez.

Answer 5

Si vous acceptez que les dictionnaires (cartes de hachage) soient O (n) espace et O (1) insertion / recherche, cette solution doit être O (m + n) à la fois dans le temps et dans l'espace.

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

D'accord, une légère triche en tant que list.append et liste .__ delitem __ ne sont que O (1) si ce sont des listes chaînées, ce qui n'est pas vraiment vrai. mais c’est l’idée, de toute façon.

Answer 6

Raffinement de la réponse de l'éphémient, elle utilise uniquement de la mémoire supplémentaire en cas de modification.

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

Commentaires? Des améliorations?

Answer 7

Je cherchais un programme permettant de convertir des fichiers volumineux sans manquer de mémoire, mais rien ne correspondait à mes besoins. Je ne suis pas intéressé à utiliser les diffs pour patcher (alors j'utiliserais probablement rdiff de librdiff), mais pour inspecter visuellement les diffs, peut-être les transformer en mots-diffs avec dwdiff - -diff-input (qui lit le format des différences unifiées) et peut-être en collectant les différences de mots en quelque sorte.

(Mon cas d’utilisation typique: j’utilise un outil de PNL pour traiter un corpus de texte volumineux. Je le lance une fois, j’obtiens un fichier de 122760246 lignes, je modifie mon outil, je le lance à nouveau, je récupère un fichier qui diffère comme chaque million de lignes, peut-être deux insertions et une suppression, ou juste une ligne diffère, ce genre de chose.)

N'ayant rien trouvé, je viens de créer un petit script https: // github. com / unhammer / diff-large-files & # 8211; cela fonctionne (dwdiff l'accepte comme entrée), il est assez rapide (plus rapide que le processus xz qui l'exécute souvent dans le pipeline) et, plus important encore, il ne manque pas de mémoire.

Answer 8

Je voudrais lire les listes de fichiers en deux ensembles et trouver les noms de fichiers propres à l'une ou l'autre liste.

En Python, quelque chose comme:

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