Como encontrar linhas duplicadas em muitos arquivos grandes?

9

Eu tenho ~ 30k arquivos. Cada arquivo contém ~ 100k linhas. Uma linha não contém espaços. As linhas em um arquivo individual são classificadas e duplicadas gratuitamente.

Meu objetivo: quero encontrar todas as linhas duplicadas em dois ou mais arquivos e também os nomes dos arquivos que continham entradas duplicadas.

Uma solução simples seria esta:

cat *.words | sort | uniq -c | grep -v -F '1 '

E então eu corria:

grep 'duplicated entry' *.words

Você vê uma maneira mais eficiente?

Lars Schneider
fonte

Respostas:

13

Como todos os arquivos de entrada já foram classificados, podemos ignorar a etapa de classificação real e apenas usá sort -m- los para mesclar os arquivos.

Em alguns sistemas Unix (que eu saiba apenas Linux), pode ser o suficiente para fazer

sort -m *.words | uniq -d >dupes.txt

para obter as linhas duplicadas gravadas no arquivo dupes.txt.

Para descobrir de quais arquivos essas linhas vieram, você pode fazer

grep -Fx -f dupes.txt *.words

Isso instruirá grepa tratar as linhas em dupes.txt( -f dupes.txt) como padrões de string fixos ( -F). greptambém exigirá que toda a linha corresponda perfeitamente do início ao fim ( -x). Irá imprimir o nome do arquivo e a linha do terminal.

Unices não Linux (ou ainda mais arquivos)

Em alguns sistemas Unix, os nomes de arquivos 30000 serão expandidos para uma cadeia longa demais para passar para um único utilitário (o significado sort -m *.wordsfalhará com o Argument list too longque ocorre no meu sistema OpenBSD). Até o Linux reclamará se o número de arquivos for muito maior.

Encontrando os idiotas

Isso significa que, no caso geral (isso também funcionará com muito mais que apenas 30000 arquivos), é necessário "dividir" a classificação:

rm -f tmpfile
find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

Como alternativa, criando tmpfilesem xargs:

rm -f tmpfile
find . -type f -name '*.words' -exec sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh {} +

Isso encontrará todos os arquivos no diretório atual (ou abaixo) cujos nomes correspondem *.words. Para um pedaço desses nomes de tamanho apropriado por vez, cujo tamanho é determinado por xargs/ find, ele os mescla no tmpfilearquivo classificado . Se tmpfilejá existir (para todos, exceto o primeiro bloco), esse arquivo também será mesclado com os outros arquivos no bloco atual. Dependendo do tamanho dos seus nomes de arquivos e do tamanho máximo permitido de uma linha de comando, isso pode exigir mais ou muito mais do que 10 execuções individuais do script interno ( find/ xargsfará isso automaticamente).

O shscript "interno" ,

if [ -f tmpfile ]; then
    sort -o tmpfile -m tmpfile "$@"
else
    sort -o tmpfile -m "$@"
fi

usa sort -o tmpfilepara enviar para tmpfile(isso não substituirá, tmpfilemesmo que também seja uma entrada para sort) e -mpara fazer a mesclagem. Nos dois ramos, "$@"será expandido para uma lista de nomes de arquivos citados individualmente, passados ​​para o script de findou xargs.

Em seguida, basta executar uniq -dem tmpfileobter toda a linha que são duplicados:

uniq -d tmpfile >dupes.txt

Se você gosta do princípio "SECO" ("Não se repita"), pode escrever o script interno como

if [ -f tmpfile ]; then
    t=tmpfile
else
    t=/dev/null
fi

sort -o tmpfile -m "$t" "$@"

ou

t=tmpfile
[ ! -f "$t" ] && t=/dev/null
sort -o tmpfile -m "$t" "$@"

De onde eles vieram?

Pelas mesmas razões acima, não podemos usar grep -Fx -f dupes.txt *.wordspara descobrir de onde vieram essas duplicações; portanto, usamos findnovamente:

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt {} +

Como não há processamento "complicado" a ser feito, podemos chamar grepdiretamente de -exec. A -execopção usa um comando utilitário e coloca os nomes encontrados {}. Com +no final, findcolocará tantos argumentos no lugar {}quanto o shell atual suporta em cada chamada do utilitário.

Para ser totalmente correto, pode-se querer usar

find . -type f -name '*.words' \
    -exec grep -H -Fx -f dupes.txt {} +

ou

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt /dev/null {} +

para garantir que os nomes de arquivos sempre sejam incluídos na saída de grep.

A primeira variação usa grep -Hpara sempre gerar nomes de arquivos correspondentes. A última variação usa o fato de grepincluir o nome do arquivo correspondente se mais de um arquivo for fornecido na linha de comando.

Isso é importante, já que o último pedaço de nome de arquivo enviado para grepde, findna verdade, pode conter apenas um único nome de arquivo, caso em grepque não o mencionaria em seus resultados.


Material bônus:

Dissecando o comando find+ xargs+ sh:

find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

find . -type f -name '*.words'simplesmente gerará uma lista de nomes de caminho a partir do diretório atual (ou abaixo), onde cada nome de caminho é o de um arquivo comum ( -type f) e possui um componente de nome de arquivo no final correspondente *.words. Se apenas o diretório atual precisar ser pesquisado, é possível adicionar -maxdepth 1após o ., antes -type f.

-print0garantirá que todos os nomes de caminho encontrados sejam gerados com um caractere \0( nul) como delimitador. Este é um caractere que não é válido em um caminho Unix e nos permite processar nomes de caminho, mesmo que contenham caracteres de nova linha (ou outras coisas estranhas).

findcanaliza sua saída para xargs.

xargs -0lerá a \0lista de nomes de caminho -delimited e executará o utilitário especificado repetidamente com partes deles, garantindo que o utilitário seja executado com argumentos suficientes para não fazer com que o shell se queixe de uma lista de argumentos muito longa, até que não haja mais entrada de find.

O utilitário invocado por xargsé shcom um script fornecido na linha de comando como uma string usando seu -csinalizador.

Ao invocar sh -c '...some script...'com os argumentos a seguir, os argumentos estarão disponíveis para o script $@, exceto pelo primeiro argumento , que será colocado $0(este é o "nome do comando" no qual você poderá localizar, por exemplo, topse for rápido o suficiente). É por isso que inserimos a string shcomo o primeiro argumento após o final do script real. A string shé um argumento fictício e pode ser qualquer palavra (algumas parecem preferir _ou sh-find).

Kusalananda
fonte
No final do seu primeiro bloco de shell script, para que serve fi' sh?
dan
@danielAzuelos fiÉ o fim da ifdeclaração no shshell script "interno" . As 'extremidades desse script de shell (o script inteiro é uma string entre aspas). O shserá passado para o script interno em $0(não parte de $@, que conterá os nomes dos arquivos). Nesse caso, essa shsequência pode realmente ser qualquer palavra. Se for deixado de fora shno final, o primeiro nome do arquivo será passado $0e não fará parte do processamento que o script de shell interno está executando.
Kusalananda
8

As linhas em um arquivo individual são classificadas e duplicadas gratuitamente.

O que significa que você provavelmente encontrará algum uso para sort -m:

 -m, --merge
        merge already sorted files; do not sort

A outra alternativa óbvia para fazer isso seria uma simples awkcoleta das linhas em uma matriz e contá-las. Mas, como comentou @ dave_thompson_085 , esses 3.000 milhões de linhas (ou quaisquer outras únicas) provavelmente levariam uma quantidade considerável de memória para armazenar, de modo que pode não funcionar muito bem.

ilkkachu
fonte
3

Com o awk, você pode obter todas as linhas repetidas em todos os arquivos em um único comando:

$ awk '_[$0]++' *.words

Mas ele repetirá as linhas se uma linha existir 3 ou mais vezes.
Existe uma solução para obter apenas a primeira duplicata:

$ awk '_[$0]++==1' *.words

Deve ser bem rápido (se houver poucas repetições), mas consumirá muita memória para manter todas as linhas na memória. Talvez, dependendo dos arquivos e das repetições reais, tente primeiro com 3 ou 4 arquivos.

$ awk '_[$0]++==1' [123]*.words

Caso contrário, você pode fazer:

$ sort -m *.words | uniq -d

O que imprimirá linhas repetidas uniq.

Isaac
fonte
2
+1 parasort -m * | uniq -d
Jeff Schaller
O awk pode evitar as repetições com, 'x[$0]++==1'mas realmente precisará de muita memória; se as linhas 3G tiverem valores 1G distintos e se o seu awk precisar digitar 50 bytes para uma entrada de hasharray mapeando uma string (presumivelmente curta) para o valor uninit, são 50 GB. Para entrada classificada, você pode fazer uniq -dmanualmente com, awk '$0==p&&n++==1;$0!=p{p=$0;n=1}'mas por que se preocupar?
Dave_thompson_085
@ dave_thompson_085 Obrigado pelo conceito de ==1, ótima idéia.
Isaac
Supondo que 30000 arquivos com 100000 linhas de 80 caracteres cada e sem duplicatas , será necessário awkarmazenar 2,4E11 bytes (223 GiB).
Kusalananda
sort -m *.words | uniq -dfunciona bem! Após o processo, corro greppara encontrar um arquivo que contenha uma entrada duplicada. Você vê uma maneira de imprimir pelo menos um nome de arquivo que contém uma entrada duplicada?
Lars Schneider
3

Solução otimizada sort+ uniq:

sort --parallel=30000 *.words | uniq -d
  • --parallel=N - altere o número de tipos executados simultaneamente para N
  • -d, --repeated - imprima apenas linhas duplicadas, uma para cada grupo
RomanPerekhrest
fonte