Trouver rapidement les différences entre les deux grands fichiers texte

J'ai deux 3GB de texte des fichiers, chaque fichier a environ 80 millions de lignes. Et ils part de 99,9% des lignes identiques (fichier Un a unique de 60 000 lignes, fichier B a unique de 80 000 lignes).

Comment puis-je trouver rapidement des lignes de deux fichiers? Est-il prêt-à-utiliser les outils de ligne de commande pour cela? Je suis à l'aide de Python, mais je suppose que c'est de moins en moins possible d'en trouver un efficace Pythonic méthode pour charger les fichiers et de les comparer.

Toutes les suggestions sont les bienvenues.

Voulez-vous dire que 99,9% de la fichiers sont identiques, ou que 99,9% de la lignes sont identiques (c'est à dire la même ligne est répétée)?
Avez-vous attention à l'ordre des lignes? Le B disposent de toutes les lignes d'Une même commande? Peut-il y avoir de réorganisation, les suppressions de lignes? Existe-il répété lignes dont le comte A a n fois, les B a n-b fois-> la différence est b* * * * ligne)
Si vous demandez à propos de "prêt-à-utiliser les outils de ligne de commande", vous pouvez spécifier un OS. Sur la plupart, "diff" est natif ou porté. Encore, je ne peux pas être sûr de ce que vous voulez à partir de votre question: peut-être sur Linux: tri-unique < fichier1 > uniq1; tri-unique < fichier2 > uniq1; diff uniq[12].
Combien d'octets par ligne en moyenne?
exactement, 99.9% des lignes dans les deux fichiers sont identiques, mais l'unique lignes sont aléatoirement réparties dans deux fichiers.

OriginalL'auteur jack | 2010-08-23

  1. 7

    Si l'ordre des questions, essayez de le comm utilitaire. Si l'ordre n'a pas d'importance, sort file1 file2 | uniq -u.

    Comment le tri de deux 3G fichiers sera plus rapide que diff?
    un diff mise en œuvre est généralement quadratique, alors que le tri est généralement n log n dans la moyenne des cas (quicksort).

    OriginalL'auteur

  2. 3

    Je pense que c'est la méthode la plus rapide (si c'est en Python ou un autre langage ne devrait pas trop OMI).

    Notes:

    1.Je ne stocker chaque ligne de hachage pour économiser de l'espace (et le temps si la pagination peut se produire)

    2.En raison de ce qui précède, je ne l'imprimer des numéros de ligne; si vous avez besoin de réelles lignes, vous auriez juste besoin de lire les fichiers dans le nouveau

    3.Je suppose que la fonction de hachage résultats dans aucun conflit. C'est presque, mais pas tout à fait, certains.

    4.- Je importer hashlib parce que le haut-hash() la fonction est trop court pour éviter les conflits.

    import sys
import hashlib

file = []
lines = []
for i in range(2):
    # open the files named in the command line
    file.append(open(sys.argv[1+i], 'r'))
    # stores the hash value and the line number for each line in file i
    lines.append({})
    # assuming you like counting lines starting with 1
    counter = 1
    while 1:
        # assuming default encoding is sufficient to handle the input file
        line = file[i].readline().encode()
        if not line: break
        hashcode = hashlib.sha512(line).hexdigest()
        lines[i][hashcode] = sys.argv[1+i]+': '+str(counter)
        counter += 1
unique0 = lines[0].keys() - lines[1].keys()
unique1 = lines[1].keys() - lines[0].keys()
result = [lines[0][x] for x in unique0] + [lines[1][x] for x in unique1]
    Regarde de la bonne réponse pour moi, je voudrais seulement suggérer pour enregistrer la position de recherche de chaque ligne lors de la lecture de les récupérer pour le résultat rapidement.
    Oui, très bon point.

    OriginalL'auteur

  3. 2

    Avec 60 000 ou 80 000 lignes uniques, vous pouvez simplement créer un dictionnaire pour chaque ligne unique, de la cartographie en nombre. mydict["hello world"] => 1, etc. Si votre moyenne est d'environ 40 à 80 caractères, ce sera dans le quartier de 10 MO de mémoire.

    Puis lire chaque fichier, de le convertir à un tableau de nombres par le dictionnaire. Ceux-ci vont s'insérer facilement dans la mémoire (2 fichiers de 8 octets * 3GB /60k lignes est de moins de 1 MO de mémoire). Alors diff les listes. Vous pourriez inverser le dictionnaire et de l'utiliser pour imprimer le texte des lignes qui diffèrent.

    EDIT:

    En réponse à votre commentaire, voici un exemple de script qui attribue un numéro unique des lignes qu'il lit à partir d'un fichier.

    #!/usr/bin/python

class Reader:

    def __init__(self, file):
        self.count = 0
        self.dict = {}
        self.file = file

    def readline(self):
        line = self.file.readline()
        if not line:
            return None
        if self.dict.has_key(line):
            return self.dict[line]
        else:
            self.count = self.count + 1
            self.dict[line] = self.count
            return self.count

if __name__ == '__main__':
    print "Type Ctrl-D to quit."
    import sys
    r = Reader(sys.stdin)
    result = 'ignore'
    while result:
        result = r.readline()
        print result
    L, je suis confus. Comment puis-je carte de 60 000 ou 80 000 lignes uniques pour un dictionnaire avant de savoir ce que les lignes sont contenues dans les deux fichiers.
    Vous pouvez simplement construire le dictionnaire comme vous de lire les fichiers. Je vais ajouter du code pour une fonction d'aide ci-dessus.
    dict.les touches() avec 3 GO? Je ne crois pas que vous pouvez économiser de hachage seulement avec seff.dict[en ligne], mais il économise de l'ensemble de la ligne dans les touches + les tables de hachage.
    Veijalainen, Oui, le dict permettra d'économiser de l'ensemble des lignes, mais seulement à enregistrer chaque ligne une fois. Donc, cette technique fonctionne bien ici seulement parce que Jack a beaucoup de doublons de lignes: 3 GO pourrait être de 100 millions de lignes de texte, mais seulement de 80 000 lignes uniques seront stockées dans le dictionnaire de la touche set.
    "Il n'y a pas répété les lignes dans les deux fichiers". Voir le poster de commentaire à son poste en réponse à moi. Peut-être que je ne comprends pas son anglais correctement.

    OriginalL'auteur

  4. 1

    Si je comprends bien, vous voulez que les lignes de ces fichiers sans les doublons. De ce fait le travail:

    uniqA = set(open('fileA', 'r'))

    OriginalL'auteur

  5. 0

    http://www.emeditor.com/ peut gérer de gros fichiers et permet également de les comparer.

    OriginalL'auteur

  6. 0

    Python a difflib qui prétend être tout à fait compétitif avec d'autres diff utilities voir:
    http://docs.python.org/library/difflib.html

    Cette lib poignée 3 go de fichiers texte?! Même de bonnes bases de données ont du mal avec ce genre de tâche... Ils ont besoin d'indexation et d'autres d'optimisation pour obtenir le résultat dans un délai raisonnable.
    Comme les lignes sont dans un ordre aléatoire et il n'y a pas besoin de trouver les changements de lignes, probablement pas la meilleure approche. Serait le cas si deux fichiers sont des versions d'un même fichier (a possibilité en raison de la grande similitude dans les lignes qui les séparent).

    OriginalL'auteur