¿Forma rápida de encontrar líneas en un archivo que no están en otro?

Tengo dos archivos grandes (conjuntos de nombres de archivos). Aproximadamente 30,000 líneas en cada archivo. Estoy tratando de encontrar una forma rápida de encontrar líneas en el archivo1 que no están presentes en el archivo2.

Por ejemplo, si esto es archivo1:

line1 line2 line3 

Y este es el archivo2:

 line1 line4 line5 

Entonces mi resultado / salida debería ser:

 line2 line3 

Esto funciona:

grep -v -f file2 file1

Pero es muy, muy lento cuando se usa en mis archivos grandes.

Sospecho que hay una buena manera de hacer esto usando diff (), pero la salida debería ser solo las líneas, nada más, y parece que no puedo encontrar un interruptor para eso.

¿Alguien puede ayudarme a encontrar una manera rápida de hacer esto, usando bash y binarios básicos de Linux?

EDITAR: para dar seguimiento a mi propia pregunta, esta es la mejor manera que he encontrado hasta ahora usando diff ():

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

Sin duda, debe haber una mejor manera?

Puede lograr esto controlando el formato de las líneas antiguas / nuevas / sin cambios en la salida de diff GNU:

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

Los archivos de entrada se deben ordenar para que esto funcione. Con bash (y zsh ) puede ordenar in situ con la sustitución de proceso <( ) :

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

En las líneas nuevas y sin cambios se suprimen, por lo que solo se modifican (es decir, se eliminan las líneas en su caso). También puede usar algunas opciones de diff que otras soluciones no ofrecen, como -i para ignorar mayúsculas y minúsculas o varias opciones de espacios en blanco ( -E , -b , -v , etc.) para una coincidencia menos estricta.


Explicación

Las opciones --new-line-format , --old-line-format y --unchanged-line-format permiten controlar la manera en que diff formatea las diferencias, de forma similar a los especificadores de formato printf . Estas opciones formatean líneas nuevas (agregadas), antiguas (eliminadas) y sin cambios , respectivamente. Configurar uno para vaciar "" evita la salida de ese tipo de línea.

Si está familiarizado con el formato de diff unificado , puede recrearlo en parte con:

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

El especificador %L es la línea en cuestión, y prefijamos cada uno con "+" "-" o "", como diff -u (tenga en cuenta que solo genera diferencias, carece de las líneas --- +++ y @@ en la parte superior de cada cambio agrupado). También puede usar esto para hacer otras cosas útiles como numerar cada línea con %dn .


El método diff (junto con otras sugerencias comm y join ) solo produce el resultado esperado con la entrada ordenada , aunque puede usar <(sort ...) para clasificar en su lugar. Aquí hay un script simple awk (nawk) (inspirado en los scripts vinculados en la respuesta de Konsolebox) que acepta archivos de entrada ordenados arbitrariamente, y genera las líneas que faltan en el orden en que ocurren en file1.

 # 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 string END { for (ll=1; ll<=nl1; ll++) if (!(ll1[ll] in ss2)) print ll1[ll] } 

Esto almacena todo el contenido del archivo1 línea por línea en una matriz indexada de número de línea ll1[] , y todo el contenido de file2 línea por línea en una matriz asociativa indexada de contenido de línea ss2[] . Después de que se leen ambos archivos, itere sobre ll1 y use el operador in para determinar si la línea en el archivo 1 está presente en el archivo2. (Esto tendrá un resultado diferente al método diff si hay duplicados).

En el caso de que los archivos sean lo suficientemente grandes como para almacenarlos genere un problema de memoria, puede cambiar la CPU por memoria almacenando solo el archivo 1 y eliminando las coincidencias a medida que se lee el archivo2.

 BEGIN { FS="" } (NR==FNR) { # file1, index by lineno and string 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] } 

Lo anterior almacena todo el contenido del archivo1 en dos matrices, una indexada por el número de línea ll1[] , una indexada por el contenido de línea ss1[] . Luego, cuando se lee el ll1[] , cada línea coincidente se elimina de ll1[] y ss1[] . Al final, las líneas restantes del archivo 1 se imprimen, preservando el orden original.

En este caso, con el problema tal como se establece, también puede dividir y conquistar usando la split GNU (el filtrado es una extensión de GNU), las ejecuciones repetidas con los fragmentos del archivo1 y la lectura del archivo2 por completo cada vez:

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

Tenga en cuenta el uso y la colocación de - significado stdin en la línea de comandos de gawk . Esto se proporciona mediante la split del archivo 1 en fragmentos de 20000 líneas por invocación.

Para los usuarios de sistemas que no son de GNU, es casi seguro que pueda obtener un paquete GNU coreutils, incluido OSX como parte de las herramientas de Apple Xcode que proporciona GNU diff , awk , aunque solo una split POSIX / BSD en lugar de una versión de GNU.

El comando comm (abreviatura de “common”) puede ser útil 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 

El archivo man es realmente bastante legible para esto.

Al igual que konsolebox sugirió, la solución grep de carteles

 grep -v -f file2 file1 

en realidad funciona muy bien (rápido) si simplemente agrega la opción -F , para tratar los patrones como cadenas fijas en lugar de expresiones regulares. Verifiqué esto en un par de ~ 1000 listas de archivos de línea que tuve que comparar. Con -F tomó 0.031 s (real), mientras que sin eso tomó 2.278 s (real), al redirigir la salida grep a wc -l .

Estas pruebas también incluyeron el -x , que son parte necesaria de la solución con el fin de garantizar una precisión total en los casos en que el archivo2 contiene líneas que coinciden con una parte, pero no todas, de una o más líneas en el archivo1.

Entonces una solución que no requiere que las entradas sean ordenadas, es rápida, flexible (sensibilidad de mayúsculas y minúsculas, etc.) y también (creo) funciona en cualquier sistema POSIX es:

 grep -F -x -v -f file2 file1 

¿Cuál es la velocidad de como sort y diff?

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

El -t asegura que compara toda la línea, si tiene espacio en algunas de las líneas.

El uso de fgrep o la adición de la opción -F a grep podría ayudar. Pero para cálculos más rápidos podrías usar Awk.

Podrías probar uno de estos métodos Awk:

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

Puedes usar Python:

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

La forma en que usualmente hago esto es usando el --suppress-common-lines , aunque tenga en cuenta que esto solo funciona si lo hace en formato lado a lado.

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

Descubrí que para mí usar un enunciado de bucle if y for funcionaba perfectamente.

 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