Como remover linhas duplicadas dentro de um arquivo de texto?

126

Um enorme arquivo de texto (com até 2 GiB) contém cerca de 100 duplicatas exatas de cada linha (inútil no meu caso, pois o arquivo é uma tabela de dados semelhante a CSV).

O que eu preciso é remover todas as repetições enquanto (de preferência, mas isso pode ser sacrificado por um aumento significativo no desempenho), mantendo a ordem da sequência original. No resultado, cada linha deve ser única. Se houvesse 100 linhas iguais (geralmente as duplicatas estão espalhadas pelo arquivo e não serão vizinhas), resta apenas uma do tipo.

Eu escrevi um programa no Scala (considere Java se você não conhece o Scala) para implementar isso. Mas talvez haja ferramentas nativas escritas em C mais rápidas, capazes de fazer isso mais rapidamente?

ATUALIZAÇÃO: a awk '!seen[$0]++' filenamesolução parecia estar funcionando bem para mim, desde que os arquivos estivessem perto de 2 GiB ou menores, mas agora como eu estou limpando um arquivo de 8 GiB, ele não funciona mais. Parece levar o infinito em um Mac com 4 GiB de RAM e um PC Windows 7 de 64 bits com 4 GiB de RAM e 6 GiB de swap fica sem memória. E não me sinto entusiasmado em experimentá-lo no Linux com 4 GiB de RAM, dada essa experiência.

Ivan
fonte
isso destruirá sua ordem, mas, você já tentou classificar -u, não tenho idéia de como ou se ele pode ser executado em um arquivo tão grande
0x7c0
5
O C geralmente não é significativamente mais rápido que o Java, e se você o estiver executando (em ordem) agora, há uma boa chance de que ele termine antes de obter uma resposta aqui, implementá-lo e concluir a execução; fora de ordem, sort -uprovavelmente será mais rápido.
Kevin Kevin

Respostas:

215

Uma awksolução vista em #bash (Freenode):

awk '!seen[$0]++' filename
enzotib
fonte
1
Apenas tentei isso em um arquivo 2G e levou três minutos no meu notebook. Não é ruim. Eu também tentei o nome do arquivo uniq | awk '! viu [$ 0] ++', mas não foi mais rápido.
mgjk
Isso é surpreendentemente mais rápido do que uma awkversão mais detalhada, usando 2 pesquisas de matriz (mostradas como uma explicação expandida na resposta de Gilles): 0m36.132s vs 0m49.958s .. para 50 milhões de linhas .. pensei que o gargalo seria a E / S, mas a pesquisa de variedade extra é ... 1 milhão de elementos na matriz parece fazer um dente bastante significativo ...
Peter.O
Mas como isso se compara à classificação -u ....?
HashWizard 13/05
1
@HashWizard: este comando não classificar, mas elimina todas próxima ocorrência da mesma linha
enzotib
1
@MaxWilliams sim, funciona é que eles são distribuídos aleatoriamente.
setholopolus
47

Existe um método simples (o que não é óbvio) usando utilitários padrão que não exigem sortmuita memória, exceto para serem executados , que na maioria das implementações possui otimizações específicas para arquivos grandes (um bom algoritmo de classificação externa). Uma vantagem desse método é que ele apenas percorre todas as linhas dentro de utilitários para fins especiais, nunca dentro de linguagens interpretadas.

<input nl -b a -s : |           # number the lines
sort -t : -k 2 -u |             # sort and uniquify ignoring the line numbers
sort -t : -k 1n |               # sort according to the line numbers
cut -d : -f 2- >output          # remove the line numbers

Se todas as linhas começarem com um caractere que não seja um espaço em branco, você poderá dispensar algumas das opções:

<input nl | sort -k 2 -u | sort -k 1n | cut -f 2- >output

Para uma grande quantidade de duplicação, um método que requer apenas o armazenamento de uma única cópia de cada linha na memória terá um desempenho melhor. Com alguma sobrecarga de interpretação, há um script awk muito conciso para isso (já publicado pelo enzotib ):

<input awk '!seen[$0]++'

Menos concisamente:, !seen[$0] {print} {seen[$0] += 1}ou seja, imprima a linha atual, se ainda não foi vista, e aumente o seencontador dessa linha (variáveis ​​não inicializadas ou elementos de matriz têm o valor numérico 0).

Para linhas longas, você pode economizar memória mantendo apenas uma soma de verificação não falsificada (por exemplo, um resumo criptográfico) de cada linha. Por exemplo, usando SHA-1, você só precisa de 20 bytes mais uma sobrecarga constante por linha. Mas a computação digesta é bastante lenta; esse método só vencerá se você tiver uma CPU rápida (especialmente uma com um acelerador de hardware para calcular os resumos) e não houver muita memória em relação ao tamanho do arquivo e linhas suficientemente longas. Nenhum utilitário básico permite calcular uma soma de verificação para cada linha; você teria que suportar a sobrecarga de interpretação do Perl / Python / Ruby /… ou escrever um programa compilado dedicado.

<input perl -MDigest::MD5 -ne '$seen{Digest::MD5::md5($_)}++ or print' >output
Gilles
fonte
@Gilles Com base na sua explicação awk '!seen[$0]++', significa que se o awk vir duas linhas duplicadas, ele manterá a primeira sempre e ignorará todas as linhas subseqüentes? (Ou ele irá manter o último?)
user779159
1
@ user779159 Mantém a primeira: cada linha de entrada é impressa imediatamente (primeira ocorrência) ou não é impressa (ocorrência repetida).
Gilles
Mas como isso se compara à classificação -u ...?
HashWizard 13/05
@HashWizard Uma planície sort -umuda a ordem. Minha resposta mostra soluções que preservam a ordem (a ordem das primeiras ocorrências, para ser mais preciso).
Gilles
@ Gilles, você diria que é mais rápido que classificar -u para arquivos grandes (10G) com 50% de duplicatas?
HashWizard
25
sort -u big-csv-file.csv > duplicates-removed.csv

Observe que o arquivo de saída será classificado.

Vladislavs Dovgalecs
fonte
1
Não tão rápido quanto o awkcomando em outras respostas, mas conceitualmente simples!
Johann
@ Johann Eu estou fazendo isso com bastante frequência em arquivos com centenas de milhares (até milhões) de sequências terminadas de nova linha. Recebo os resultados rapidamente para as experiências que estou fazendo. Pode ser mais importante se usado em scripts executados repetidamente, a economia de tempo pode ser considerável.
Vladislavs Dovgalecs 31/03
1
Use sort -upara remover duplicatas durante a classificação, e não depois. (E economiza largura de banda de memória) canalizando-o para outro programa). Isso só é melhor que a awkversão se você deseja que sua saída seja classificada também. (O OP sobre esta questão quer a sua disposição original preservada , por isso esta é uma boa resposta para um caso de uso um pouco diferente.)
Peter Cordes
Levou cerca de um minuto, para mim, para um arquivo de linha de 5,5 milhões (1,8 GB no total). Brilhante.
Max Williams
18

Supondo que você possa manter tanto quanto o arquivo desduplicado na memória (se seus dados forem realmente duplicados por um fator de 100, ou seja, cerca de 20MiB +), você poderá fazer isso muito facilmente com o Perl.

$ perl -ne 'print unless $dup{$_}++;' input_file > output_file

Isso preserva a ordem também.

Você pode extrair o número de ocorrências de cada linha do %duphash, se desejar, como um bônus grátis adicional.

Se você preferir awk, também deve fazê-lo (mesma lógica da versão perl, mesma ordem, mesmos dados reunidos na dupvariável):

$ awk '{if (++dup[$0] == 1) print $0;}' input_file > output_file
Esteira
fonte
Isso é muito bom @ Mat, eu estava prestes a beber o arquivo, lol ;-).
Nikhil Mulley
Agora à espera de @ManAtWork por sua sed e awk weavery magia também :-)
Nikhil Mulley
incrível novamente para o :-) ponta awk
Nikhil Mulley
1
É possível alterar o script perl para remover apenas linhas adjacentes duplicadas?
dumbledad
2
@dumbledad: uniqfaz isso por si só
Mat
3

Como nenhuma outra resposta forneceu suporte no local, aqui está uma:

gawk -i inplace '!a[$0]++' file
Jan Chren - rindeal
fonte
Isso preserva a ordem? A propósito, isso não funcionou para mim. Minha versão é: #GNU Awk 4.0.2
Leonid
1
@ Leonid sim, faz. Imprime a primeira ocorrência de qualquer linha exclusiva. O apoio inplace foi introduzido pela primeira vez na versão 4.1, que foi lançado em 2013.
Jan Chren - rindeal
3

Você pode usar uniq http://www.computerhope.com/unix/uuniq.htm

uniq relata ou filtra linhas repetidas em um arquivo.

Mahmoud Zalt
fonte
Ao dar uma resposta, é preferível dar uma explicação sobre POR QUE sua resposta é essa. Então, como essa resposta difere de várias respostas anteriores?
Stephen Rauch
1
Na página de manual uniq: Nota: 'uniq' does not detect repeated lines unless they are adjacent. Portanto, você deve primeiro classificá-lo e perder a ordem das linhas não duplicadas.
Vindolin
2

Forros do Python One:

python -c "import sys; lines = sys.stdin.readlines(); print ''.join(sorted(set(lines)))" < InputFile
Rahul Patil
fonte
isso faz com que o arquivo inteiro seja inutilizado na memória e pode não ser um bom ajuste para o problema do OP. Também não é garantido manter a ordem
iruvar 15/09/13
Obrigado pela sugestão, eu tenho apenas aprender python .. apenas tentei isso para aprender propósito .. :)
Rahul Patil
Aqui está um Python 2.7 versão que não é um one-liner, mas (sucintamente) retorna linhas exclusivas fim preservando sem carregar o arquivo inteiro na memória ou a criação de uma única cadeia gigantesca para alimentar a impressão
Iruvar
Obrigado @ 1_CR eu tenho algo aprender hoje :)OrderedDict
Rahul Patil
0

Nenhuma das respostas aqui funcionou para mim no meu Mac, por isso escrevi um script python simples que funciona para mim. Estou ignorando os espaços em branco iniciais / finais e também não me importo com o consumo de memória.

import sys

inputfile = sys.argv[1]
outputfile = sys.argv[2]

with open(inputfile) as f:
    content = f.readlines()

content = [x.strip() for x in content]

my_list = list(set(content))

with open(outputfile, 'w') as output:
    for item in my_list:
        output.write("%s\n" % item)

Salve o acima em unique.py e execute assim:

python unique.py inputfile.txt outputfile.txt
Jared
fonte
-1

Com o bash 4, pode ser usada uma solução pura do bash que aproveita as matrizes associativas . Aqui está um exemplo

unset llist; declare -A llist;
while read -r line; do
if [[ ${llist[$line]} ]]; then
  continue
else 
  printf '%s\n' "$line"
  llist[$line]="x"
fi
done < file.txt
iruvar
fonte
2
Não use readloops para processar grandes arquivos de texto. O bash precisa ler um byte de cada vez para evitar ultrapassar uma nova linha. O Bash também não é muito rápido no processamento de texto em geral, comparado ao awk. Se você usar isso, read -ravai evitar comer barras invertidas em sua entrada. Além disso, não se esqueça de unset llist depois do loop, se você colocar isso em uma função shell ou usá-lo interativamente.
Peter Cordes
2
@PeterCordes, ou você poderia ter apenas referenciada este :-)
Iruvar