Moyen rapide de trouver des lignes dans un fichier qui ne sont pas dans un autre?

J’ai deux gros fichiers (jeux de noms de fichiers). Environ 30.000 lignes dans chaque fichier. J’essaie de trouver un moyen rapide de trouver des lignes dans fichier1 qui ne sont pas présentes dans fichier2.

Par exemple, s’il s’agit de fichier1:

line1 line2 line3 

Et ceci est fichier2:

 line1 line4 line5 

Ensuite, mon résultat / sortie doit être:

 line2 line3 

Cela marche:

grep -v -f file2 file1

Mais c’est très, très lent lorsqu’il est utilisé sur mes gros fichiers.

Je pense qu’il y a un bon moyen de faire ceci en utilisant diff (), mais la sortie devrait être juste les lignes, rien d’autre, et je n’arrive pas à trouver un commutateur pour cela.

Quelqu’un peut-il m’aider à trouver un moyen rapide de le faire, en utilisant des binarys Linux bash et basiques?

EDIT: Pour suivre ma propre question, c’est la meilleure façon que j’ai trouvée jusqu’ici en utilisant diff ():

 diff file2 file1 | grep '^>' | sed 's/^>\ //' 

Il doit certainement exister un meilleur moyen?

Vous pouvez y parvenir en contrôlant le formatage des anciennes lignes / nouvelles / inchangées dans la sortie GNU diff :

 diff --new-line-format="" --unchanged-line-format="" file1 file2 

Les fichiers d’entrée doivent être sortingés pour que cela fonctionne. Avec bash (et zsh ), vous pouvez sortinger sur place avec la substitution de processus < ( ) :

 diff --new-line-format="" --unchanged-line-format="" < (sort file1) <(sort file2) 

Dans les lignes nouvelles et inchangées ci-dessus sont supprimés, donc seulement modifié (c.-à-lignes supprimées dans votre cas) sont sorties. Vous pouvez également utiliser quelques options diff que d'autres solutions n'offrent pas, telles que -i pour ignorer la casse ou diverses options d' -E ( -E , -b , -v etc.) pour une correspondance moins ssortingcte.


Explication

Les options --new-line-format , --old-line-format et --unchanged-line-format vous permettent de contrôler la façon dont diff diffère les différences, comme pour les printf format printf . Ces options formatent respectivement les nouvelles lignes (ajoutées), anciennes (supprimées) et inchangées . Si on en met un à vide "" empêche la sortie de ce type de ligne.

Si vous connaissez le format diff unifié , vous pouvez le recréer en partie avec:

 diff --old-line-format="-%L" --unchanged-line-format=" %L" \ --new-line-format="+%L" file1 file2 

Le spécificateur %L est la ligne en question, et nous préfixons chacun avec "+" "-" ou "", comme diff -u (notez qu’il ne produit que des différences, il lui manque les lignes --- +++ et @@ en haut de chaque changement groupé). Vous pouvez également l'utiliser pour faire d'autres choses utiles comme numéroter chaque ligne avec %dn .


La méthode diff (avec d'autres suggestions de comm et de join ) ne produit que la sortie attendue avec une entrée sortingée , bien que vous puissiez utiliser < (sort ...) pour sortinger en place. Voici un simple script awk (nawk) (inspiré des scripts liés à la réponse de Konsolebox) qui accepte les fichiers d'entrée ordonnés arbitrairement et affiche les lignes manquantes dans l'ordre dans lequel elles apparaissent dans fichier1.

 # output lines in file1 that are not in file2 BEGIN { FS="" } # preserve whitespace (NR==FNR) { ll1[FNR]=$0; nl1=FNR; } # file1, index by lineno (NR!=FNR) { ss2[$0]++; } # file2, index by ssortingng END { for (ll=1; ll< =nl1; ll++) if (!(ll1[ll] in ss2)) print ll1[ll] } 

Cela stocke l'intégralité du contenu de file1 ligne par ligne dans un tableau indexé de numéro de ligne ll1[] , et l'intégralité du contenu de file2 ligne par ligne dans un tableau associatif indexé au contenu de ligne ss2[] . Une fois les deux fichiers lus, effectuez une itération sur ll1 et utilisez l'opérateur in pour déterminer si la ligne dans file1 est présente dans file2. (Cela aura une sortie différente de la méthode diff s'il y a des doublons.)

Si les fichiers sont suffisamment volumineux et que leur stockage entraîne un problème de mémoire, vous pouvez échanger le processeur contre de la mémoire en ne stockant que le fichier 1 et en supprimant les correspondances au fur et à mesure de la lecture du fichier.

 BEGIN { FS="" } (NR==FNR) { # file1, index by lineno and ssortingng ll1[FNR]=$0; ss1[$0]=FNR; nl1=FNR; } (NR!=FNR) { # file2 if ($0 in ss1) { delete ll1[ss1[$0]]; delete ss1[$0]; } } END { for (ll=1; ll< =nl1; ll++) if (ll in ll1) print ll1[ll] } 

Ce qui précède stocke l'intégralité du contenu de fichier1 dans deux tableaux, l'un indexé par le numéro de ligne ll1[] , l'autre par le contenu de ligne ss1[] . Ensuite, à la lecture de fichier2, chaque ligne correspondante est supprimée de ll1[] et de ss1[] . A la fin, les lignes restantes du fichier 1 sont sorties, préservant l'ordre d'origine.

Dans ce cas, avec le problème comme indiqué, vous pouvez également diviser et conquérir en utilisant la split GNU (le filtrage est une extension GNU), répéter les exécutions avec des morceaux de fichier1 et lire complètement le fichier2 à chaque fois:

 split -l 20000 --filter='gawk -f linesnotin.awk - file2' < file1 

Notez l'utilisation et l'emplacement de - signifiant stdin sur la ligne de commande gawk . Ceci est fourni par split from fichier1 en blocs de 20000 lignes par invocation.

Pour les utilisateurs sur des systèmes non GNU, il existe certainement un paquetage GNU coreutils que vous pouvez obtenir, y compris sur OSX dans les outils Apple Xcode , qui fournit GNU diff , awk , mais uniquement une split POSIX / BSD plutôt qu'une version GNU.

La commande comm (abréviation de “common”) peut être utile comm - compare two sorted files line by line

 #find lines only in file1 comm -23 file1 file2 #find lines only in file2 comm -13 file1 file2 #find lines common to both files comm -12 file1 file2 

Le fichier man est en fait assez lisible pour cela.

Comme suggéré par konsolebox, les affiches grep solution

 grep -v -f file2 file1 

fonctionne vraiment bien (rapide) si vous ajoutez simplement l’option -F , pour traiter les patterns comme des chaînes fixes au lieu d’expressions régulières. Je l’ai vérifié sur une paire de ~ 1000 listes de fichiers que je devais comparer. Avec -F il a fallu 0,031 s (réel), alors que sans lui, il a fallu 2,278 s (réel) pour redirect la sortie de grep vers wc -l .

Ces tests comprenaient également le commutateur -x , qui fait partie intégrante de la solution afin de garantir une précision totale dans les cas où file2 contient des lignes qui correspondent à une partie, mais pas à toutes, d’une ou plusieurs lignes de file1.

Ainsi, une solution qui ne nécessite pas le sorting des entrées, est rapide, flexible (sensibilité à la casse, etc.) et fonctionne également (je pense) sur n’importe quel système POSIX:

 grep -F -x -v -f file2 file1 

Quelle est la vitesse de sorting et de diff?

 sort file1 -u > file1.sorted sort file2 -u > file2.sorted diff file1.sorted file2.sorted 
 $ join -v 1 -t '' file1 file2 line2 line3 

Le -t s’assure qu’il compare la ligne entière, si vous aviez un espace dans certaines lignes.

L’utilisation de fgrep ou l’ajout de l’option -F à grep pourrait aider. Mais pour des calculs plus rapides, vous pouvez utiliser Awk.

Vous pouvez essayer l’une de ces méthodes Awk:

http://www.linuxquestions.org/questions/programming-9/grep-for-huge-files-826030/#post4066219

Vous pouvez utiliser Python:

 python -c ' lines_to_remove = set() with open("file2", "r") as f: for line in f.readlines(): lines_to_remove.add(line.ssortingp()) with open("f1", "r") as f: for line in f.readlines(): if line.ssortingp() not in lines_to_remove: print(line.ssortingp()) ' 

La façon dont je le fais habituellement utilise l’ --suppress-common-lines , mais notez que cela ne fonctionne que si vous le faites au format côte à côte.

diff -y --suppress-common-lines file1.txt file2.txt

J’ai trouvé que pour moi, utiliser une instruction if et for loop normale fonctionnait parfaitement.

 for i in $(cat file2);do if [ $(grep -i $i file1) ];then echo "$i found" >>Matching_lines.txt;else echo "$i missing" >>missing_lines.txt ;fi;done