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

241

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

Por exemplo, se esse for o arquivo1:

line1
line2
line3

E este é o arquivo2:

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 existe 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 binários básicos e básicos do linux?

Edição: Para acompanhar a minha própria pergunta, esta é a melhor maneira que eu encontrei até agora usando diff ():

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

Certamente deve haver uma maneira melhor?

Niels2000
fonte
1
você poderia tentar isso, se é mais rápido:awk 'NR==FNR{a[$0];next}!($0 in a)' file2 file1 > out.txt
Kent
sem requisito rápido: stackoverflow.com/questions/4366533/…
Ciro Santilli escreveu:
4
Obrigado por informar sobre grep -v -f arquivo2 arquivo1
Rahul Prasad
Maneira simples com conjunto de ferramentas reduzido:, cat file1 file2 file2 | sort | uniq --uniqueveja minha resposta abaixo.
Onda Žižka

Respostas:

233

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

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

Os arquivos de entrada devem ser classificados para que isso funcione. 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 novas e inalteradas acima , são suprimidas, portanto, apenas as alterações (ou seja, linhas removidas no seu caso) são exibidas. Você também pode usar algumas diffopções que outras soluções não oferecem, tais como -ipara ignorar caso, ou várias opções em branco ( -E, -b, -vetc.) para correspondência menos rigoroso.


Explicação

As opções --new-line-format, --old-line-formate --unchanged-line-formatpermitem controlar a forma como diffformata as diferenças, semelhantes aos printfespecificadores de formato. Essas opções formatam as linhas nova (adicionada), antiga (removida) e inalterada , respectivamente. Definir um como vazio "" impede a saída desse tipo de linha.

Se você estiver familiarizado com o formato diff unificado , é possível recriá-lo parcialmente com:

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

O %Lespecificador é a linha em questão, e prefixamos cada um com "+" "-" ou "", como diff -u (observe que ele apenas gera diferenças, não possui as linhas --- +++e @@na parte superior de cada alteração agrupada). Você também pode usar isso para fazer outras coisas úteis como número cada linha com %dn.


O diffmétodo (junto com outras sugestões comme join) produz apenas a saída esperada com entrada classificada , embora você possa usar <(sort ...)para classificar no local. Aqui está um awkscript simples (nawk) (inspirado nos scripts vinculados à resposta do Konsolebox) que aceita arquivos de entrada ordenados arbitrariamente e gera 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 uma matriz indexada por número de linha ll1[]e todo o conteúdo do arquivo2 linha por linha em uma matriz associativa indexada por conteúdo de linha ss2[]. Após a leitura dos dois arquivos, repita ll1e use o inoperador para determinar se a linha no arquivo1 está presente no arquivo2. (Isso terá uma saída diferente para o diffmétodo se houver duplicatas.)

No caso de os arquivos serem suficientemente grandes, o armazenamento dos dois causa um problema de memória, você pode trocar a CPU por memória armazenando apenas o arquivo1 e excluindo correspondências ao longo do caminho à medida que o arquivo2 é 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 exemplo acima armazena todo o conteúdo do arquivo1 em duas matrizes, uma indexada pelo número da linha ll1[], uma indexada pelo conteúdo da linha ss1[]. Então, como o arquivo2 é lido, cada linha correspondente é excluída de ll1[]e ss1[]. No final, as linhas restantes do arquivo1 são exibidas, preservando a ordem original.

Nesse caso, com o problema conforme indicado, você também pode dividir e conquistar usando o GNU split(a filtragem é uma extensão do GNU), execuções repetidas com partes do arquivo1 e lendo o arquivo2 toda vez:

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

Observe o uso e o posicionamento do -significado stdinna gawklinha de comando. Isso é fornecido pelo splitarquivo1 em pedaços de 20000 linhas por chamada.

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

mr.spuratic
fonte
1
Isso faz exatamente o que eu preciso, em uma pequena fração do tempo gasto pelo enorme grep. Obrigado!
Niels2000
1
Encontrei esta página de manual do gnu
Juto 13/08
alguns de nós não estão em gnu [OS X BSD aqui ...] :)
rogerdpack
1
Suponho que você queira dizer diff: em geral, os arquivos de entrada serão diferentes, 1 é retornado diffnesse caso. Considere isso um bônus ;-) Se você estiver testando em um shell script 0 e 1 são códigos de saída esperados, 2 indica um problema.
precisa saber é o seguinte
1
Ah, sim, agora eu acho isso no man diff. Obrigado!
Archeosudoerus 2/11
242

O comando comm (abreviação de "common") pode ser útilcomm - 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 manarquivo é realmente bastante legível para isso.

JnBrymn
fonte
6
Funciona perfeitamente no OSX.
pisaruk
40
Talvez o requisito para entrada classificada deva ser destacado.
Tripleee
20
commtambém tem uma opção para verificar se a entrada está classificada --check-order(o que parece acontecer de qualquer maneira, mas essa opção causará erros ao invés de continuar). Mas para classificar os arquivos, basta fazer: com -23 <(sort file1) <(sort file2)e assim por diante
michael
Eu estava comparando um arquivo que foi gerado no Windows com um arquivo que foi gerado no Linux e parecia que commnão estava funcionando. Demorei um pouco para descobrir que se trata das terminações de linha: mesmo as linhas que parecem idênticas são consideradas diferentes se tiverem terminações de linha diferentes. O comando dos2unixpode ser usado para converter as terminações da linha CRLF apenas em LF.
ZeroOne 27/03
23

Como o konsolebox sugeriu, a solução grep para pôsteres

grep -v -f file2 file1

realmente funciona muito bem (rápido) se você simplesmente adicionar a -Fopção, para tratar os padrões como cadeias de caracteres fixas em vez de expressões regulares. Eu verifiquei isso em um par de ~ 1000 listas de arquivos de linha que tive que comparar. Com -Fisso, levou 0,031 s (real), enquanto sem levou com 2.278 s (real), ao redirecionar a saída grep para wc -l.

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

Portanto, uma solução que não exige que as entradas sejam classificadas é rápida e flexível (diferenciação de maiúsculas e minúsculas, etc.) é:

grep -F -x -v -f file2 file1

Isso não funciona com todas as versões do grep, por exemplo, falha no macOS, onde uma linha no arquivo 1 será mostrada como não presente no arquivo 2, mesmo que seja, se corresponder a outra linha que é uma substring dele . Como alternativa, você pode instalar o GNU grep no macOS para usar esta solução.

pbz
fonte
Sim, funciona, mas mesmo com -Fisso não escala bem.
Molomby 28/09
isso não é tão rápido, eu esperei 5 minutos para 2 arquivos de ~ 500k linhas antes de desistir
Cahen
na verdade, desta forma ainda mais lenta é a forma de comunicação, porque este pode manipular arquivos não ordenados, portanto, arrastado por unsorting, comm leva a vantagem de triagem
workplaylifecycle
@workplaylifecycle Você precisa adicionar o tempo para a classificação, que pode ser o gargalo para pessoas extremamente grandes file2.
rwst
No entanto, o grep com a -xopção aparentemente usa mais memória. Com file2180 milhões de palavras contendo 6 a 10 bytes, meu processo chegou Killeda uma máquina com 32 GB de RAM ...
rwst
11

qual é a velocidade de como classificar e diff?

sort file1 -u > file1.sorted
sort file2 -u > file2.sorted
diff file1.sorted file2.sorted
Puggan Se
fonte
1
Obrigado por me lembrar sobre a necessidade de classificar os arquivos antes de fazer o diff. sort + diff é MUITO mais rápido.
Niels2000
4
um forro ;-) diff <(sort file1 u) <(sort arq2 -u)
steveinatorx
11

Se você está com falta de "ferramentas sofisticadas", por exemplo, em alguma distribuição mínima do Linux, há uma solução com just cat, sorte uniq:

cat includes.txt excludes.txt excludes.txt | sort | uniq --unique

Teste:

seq 1 1 7 | sort --random-sort > includes.txt
seq 3 1 9 | sort --random-sort > excludes.txt
cat includes.txt excludes.txt excludes.txt | sort | uniq --unique

# Output:
1
2    

Isso também é relativamente rápido, comparado a grep.

Ondra Žižka
fonte
1
Nota - algumas implementações não reconhecerão a --uniqueopção. Você deve ser capaz de usar a opção POSIX padronizado para isso:| uniq -u
AndrewF
1
No exemplo, de onde veio o "2"?
perfil completo de Niels2000
1
@ Niels2000, seq 1 1 7cria números de 1, com incremento 1, até 7, ou seja, 1 2 3 4 5 6 7. E aí está o seu 2!
Eirik Lygre
5
$ join -v 1 -t '' file1 file2
line2
line3

O -tgarante que ele compara a linha inteira, se você tiver um espaço em algumas das linhas.

Steven Penny
fonte
Como comm, joinexige que as duas linhas de entrada sejam classificadas no campo em que você está executando a operação de junção.
Tripleee
4

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())
'
Olá adeus
fonte
4

Use combinede moreutilspacote, um utilitário conjuntos que suporta not, and, or, xoroperações

combine file1 not file2

ou seja, me dê linhas que estão no arquivo1, mas não no arquivo2

OU me dê linhas no arquivo1 menos linhas no arquivo2

Nota: combine classifica e localiza linhas exclusivas nos dois arquivos antes de executar qualquer operação, mas diffnão o faz. Então você pode encontrar diferenças entre a saída de diffe combine.

Então, com efeito, você está dizendo

Encontre linhas distintas em arquivo1 e arquivo2 e, em seguida, me dê linhas em arquivo1 menos linhas em arquivo2

Na minha experiência, é muito mais rápido que outras opções

CiganoCosmonauta
fonte
2

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

Você pode tentar um destes métodos do Awk:

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

konsolebox
fonte
2
+1 Esta é a única resposta que não requer que as entradas sejam classificadas. Embora aparentemente o OP estivesse satisfeito com esse requisito, é uma restrição inaceitável em muitos cenários do mundo real.
Tripleee
1

A maneira como costumo fazer isso é usar a --suppress-common-linesbandeira, embora observe que isso só funciona se você fizer isso no formato lado a lado.

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

BAustin
fonte
0

Eu descobri que, para mim, usar uma instrução if e for normal 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
Tman
fonte
2
Consulte DontReadLinesWithFor . Além disso, esse código se comportará muito mal se algum dos seus grepresultados se expandir para várias palavras ou se alguma das suas file2entradas puder ser tratada pelo shell como um globo.
Charles Duffy