Maneira rápida de encontrar linhas em um arquivo que não estão em outro?

Eu tenho dois arquivos grandes (conjuntos de nomes de arquivos). Aproximadamente 30.000 linhas em cada arquivo. Eu estou tentando encontrar uma maneira rápida de encontrar linhas no arquivo1 que não estão presentes no arquivo2.

Por exemplo, se este for o arquivo1:

line1 line2 line3 

E isso é file2:

 line1 line4 line5 

Então meu resultado / saída deve ser:

 line2 line3 

Isso funciona:

grep -v -f file2 file1

Mas é muito, muito lento quando usado em meus arquivos grandes.

Eu suspeito que há uma boa maneira de fazer isso usando diff (), mas a saída deve ser apenas as linhas, nada mais, e não consigo encontrar uma opção para isso.

Alguém pode me ajudar a encontrar uma maneira rápida de fazer isso, usando bash e binários básicos do Linux?

EDIT: Para acompanhar a minha própria pergunta, esta é a melhor maneira que encontrei até agora usando diff ():

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

Certamente deve haver uma maneira melhor?

Você pode conseguir isso controlando a formatação das linhas antigas / novas / inalteradas na saída do diff GNU:

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

Os arquivos de input devem ser classificados para isso funcionar. Com bash (e zsh ), você pode classificar no local com a substituição do processo < ( ) :

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

Nas linhas acima novas e inalteradas são suprimidas, portanto, apenas alteradas (isto é, linhas removidas no seu caso) são produzidas. Você também pode usar algumas opções de diff que outras soluções não oferecem, como -i para ignorar maiúsculas e minúsculas, ou várias opções de espaços em branco ( -E , -b , -v , etc.) para uma correspondência menos estrita.


Explicação

As opções - --new-line-format , --old-line-format e - --unchanged-line-format permitem controlar a forma como o diff formata as diferenças, semelhante aos especificadores de formato printf . Essas opções formatam novas linhas (adicionadas), antigas (removidas) e inalteradas , respectivamente. Definir um para esvaziar "" impede a saída desse tipo de linha.

Se você estiver familiarizado com o formato diff unificado , poderá recriá-lo parcialmente com:

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

O %L especificador é a linha em questão, e prefixamos cada um com "+" "-" ou "", como diff -u (note que ele só gera diferenças, ele não possui as linhas --- +++ e @@ no topo de cada alteração agrupada). Você também pode usar isso para fazer outras coisas úteis, como numerar cada linha com %dn .


O método diff (junto com outras sugestões comm e join ) apenas produz a saída esperada com a input classificada , embora você possa usar < (sort ...) para classificar no local. Aqui está um simples script awk (nawk) (inspirado pelos scripts vinculados na resposta do Konsolebox) que aceita arquivos de input ordenados arbitrariamente, e imprime as linhas ausentes na ordem em que ocorrem no arquivo1.

 # 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] } 

Isso armazena todo o conteúdo do arquivo1 linha por linha em um array indexado por números de linha ll1[] , e todo o conteúdo do arquivo2 linha por linha em uma matriz associativa indexada por conteúdo de linha ss2[] . Depois que os dois arquivos forem lidos, faça uma iteração sobre ll1 e use o operador in para determinar se a linha no arquivo1 está presente no arquivo2. (Isso terá saídas diferentes para o método diff se houver duplicatas.)

No caso de os arquivos serem suficientemente grandes para armazená-los, ambos causarão um problema de memory, você poderá trocar a CPU por memory, armazenando apenas o arquivo1 e excluindo as correspondências ao longo do caminho, conforme o arquivo2 for lido.

 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] } 

O acima armazena todo o conteúdo do arquivo1 em duas matrizes, uma indexada pelo número de linha ll1[] , uma indexada pelo conteúdo da linha ss1[] . Então, como file2 é lido, cada linha correspondente é excluída de ll1[] e ss1[] . No final, as linhas restantes do arquivo 1 são produzidas, preservando a ordem original.

Neste caso, com o problema declarado, você também pode dividir e conquistar usando a split GNU (a filtragem é uma extensão GNU), executa repetidas com partes do arquivo1 e lê o arquivo2 completamente a cada vez:

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

Observe o uso e posicionamento de - significando stdin na linha de comando do gawk . Isso é fornecido pela split do arquivo1 em blocos de 20000 linhas por invocação.

Para usuários em sistemas não-GNU, há quase certamente um pacote GNU coreutils que você pode obter, incluindo o OSX como parte das ferramentas Apple Xcode que fornecem GNU diff , awk , embora apenas uma split POSIX / BSD em vez de uma versão GNU.

O comando comm (abreviação de “common”) pode ser útil para 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 

O arquivo man é realmente muito legível para isso.

Como konsolebox sugerido, a solução grep posters

 grep -v -f file2 file1 

realmente funciona muito bem (rápido) se você simplesmente adicionar a opção -F , para tratar os padrões como strings fixas ao invés de expressões regulares. Eu verifiquei isso em um par de listas de arquivos de ~ 1000 linhas que eu tive que comparar. Com -F demorou 0.031 s (real), enquanto sem levou 2.278 s (real), ao redirect a saída do grep para wc -l .

Esses testes também incluíram a opção -x , que é parte necessária da solução para garantir total precisão nos casos em que file2 contém linhas que correspondem a parte, mas não a todas, de uma ou mais linhas no arquivo1.

Então uma solução que não requer que as inputs sejam ordenadas, seja rápida, flexível (case sensitive, etc) e também (eu acho) funciona em qualquer sistema POSIX é:

 grep -F -x -v -f file2 file1 

Qual é a velocidade de classificar e diferenciar?

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

O -t garante que compara toda a linha, se você tivesse um espaço em algumas das linhas.

Usar o fgrep ou adicionar a opção -F ao grep poderia ajudar. Mas, para cálculos mais rápidos, você poderia usar o Awk.

Você poderia tentar um desses methods Awk:

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

Você pode usar o 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()) ' 

A maneira que eu costumo fazer isso é usando o --suppress-common-lines , mas note que isso só funciona se você fizer isso no formato side-by-side.

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

Descobri que, para mim, usar uma instrução normal if e for loop funcionou perfeitamente.

 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