Remove linhas duplicadas enquanto mantém a ordem das linhas

Question

[root@server]# awk '!seen[$0]++' out.txt > cleaned
awk: (FILENAME=out.txt FNR=8547098) fatal error: internal error
Aborted
[root@server]#

O "" servidor "" possui: RAM de 8 GBytes + SWAP de 16 GByte, x > 300 GBytes de espaço livre, amd64, CPU de desktop. Scientific Linux 6.6. Nada mais é executado para fazer LOAD. O awk aborta depois de alguns segundos .. o out.txt tem ~ 1.6 GByte. GNU Awk 3.1.7.

Pergunta : Como posso remover as linhas duplicadas mantendo a ordem das linhas? Caso é importante também, ex: "A" e "a" são duas linhas diferentes, tem que mantê-lo. Mas "a" e "a" são duplicados, apenas o primeiro é necessário.

Resposta poderia estar em qualquer coisa .. se o awk não é bom para isso .. então perl / sed .. qual poderia ser o problema?

[root@server]# ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 61945
max locked memory       (kbytes, -l) 99999999
max memory size         (kbytes, -m) unlimited
open files                      (-n) 999999
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 99999999
cpu time               (seconds, -t) unlimited
max user processes              (-u) 61945
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited
[root@server]# 

Update: Eu tentei isso em uma máquina RHEL, ele não aborta, mas eu não tive tempo para esperar que ele terminasse .. por que o SL Linux não difere do RHEL?

Update: Eu estou tentando em um virtual do Ubuntu 14 .. até agora funciona! Não é um problema ulimit: mawk 1.3.3

root@asdf-VirtualBox:~# ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 51331
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 51331
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited
root@asdf-VirtualBox:~# 

    

Answer 1

Eu duvido que isso faça a diferença, mas, apenas no caso, aqui está como fazer a mesma coisa em Perl:

perl -ne 'print if ++$k{$_}==1' out.txt

Se o problema é manter as linhas exclusivas na memória, isso terá o mesmo problema que o awk que você tentou. Então, outra abordagem poderia ser:

cat -n out.txt | sort -k2 -k1n  | uniq -f1 | sort -nk1,1 | cut -f2-

Como funciona:

1. Em um sistema GNU, cat -n pré-adicionará o número da linha a cada linha seguindo uma certa quantidade de espaços e seguido por um caractere < tab > . cat canaliza essa representação de entrada para sort .

2. A opção sort -k2 instrui apenas a considerar os caracteres do segundo campo até o final da linha durante a classificação e sort divide os campos por padrão no espaço em branco (ou cat de espaços inseridos e < tab > ) .
   Quando seguido por -k1n , sort considera primeiro o segundo campo e, em segundo lugar, no caso de campos -k2 idênticos, considera o primeiro campo, mas como numericamente ordenado. Assim, as linhas repetidas serão classificadas juntas, mas na ordem em que apareceram.

3. Os resultados são canalizados para uniq - que é instruído a ignorar o primeiro campo ( -f1 - e também separado por espaço em branco) - e que resulta em uma lista de linhas exclusivas em o arquivo original e é redirecionado para sort .
4. Desta vez sort ordena no primeiro campo ( cat inserido o número da linha) numericamente, obtendo a ordem de classificação de volta para o que estava no arquivo original e canaliza esses resultados para cut .
5. Por último, cut remove os números de linha que foram inseridos por cat . Isso é afetado pela impressão cut somente do segundo campo até o final da linha (e o delimitador padrão de cut é um < tab> ) .

Para ilustrar:

$ cat file
bb
aa
bb
dd
cc
dd
aa
bb
cc
$ cat -n file | sort -k2 | uniq -f1 | sort -k1 | cut -f2-
bb
aa    
dd
cc

    

Answer 2

#!/usr/bin/perl 
use DB_File;
tie %h, 'DB_File';

while(<>){ not $h{$_} and print and $h{$_}=1 }

EDIT 1: Isso realmente funciona? (comparando)

Sol1 : Terdon et all Schwartzian-transform-like one-liner
    cat -n _1 | sort -uk2 | sort -nk1 | cut -f2-

Sol2 : perl  + DB_File (this answer)
    perl dbfile-uniq _1

Sol3 : PO (John W. Gill solution has a similar behavior)
    awk '!seen[$0]++' _1

Sol4: Terdon perl
    perl -ne 'print if ++$k{$_}==1' _1

Caso1 : 100_000_000 números aleatórios (5 dígitos cada), 566Mbytes, 31_212 valores diferentes:

$ while true ; do echo $RANDOM; done | head -100000000 > _1

Caso 2 : 50_000_000 números de rand (10 dígitos cada), 516Mbytes, 48_351_464 valores diferentes:

$ shuf _1 |  sed 'N;s/\n/ /' > _11

(os números a seguir não são muito precisos):

┌────────┬────────┬────────────────┬────────┬──────┐
│        │ Sol1   │ Sol2           │ Sol3   │ Sol4 │
│        │ sort...│ perl DB        │ awk    │ perl │
├────────┼────────┼────────────────┼────────┼──────┤
│ case 1 │ 6m15   │ 6m17           │ 0m28   │ 0m28 │
├────────┼────────┼────────────────┼────────┴──────┤
│ case 2 │ 11m15  │ 81m44          │ out of memory │
├────────┼────────┼────────────────┼────────┬──────┤
│ case 2 │        │ 5m54 /cache=2G │        │      │
└────────┴────────┴────────────────┴────────┴──────┘

sol2 com cache é:

use DB_File;
use Fcntl ;

$DB_HASH->{'cachesize'} = 2000_000_000;
tie %h, 'DB_File', "_my.db", O_RDWR|O_CREAT|O_TRUNC, 0640, $DB_HASH;

while(<>){ not $h{$_} and print and $h{$_}=1 }

O Sort também pode otimizar a adição de uma opção cachesize (não concluída).

Uma conclusão rápida:

• sort é um comando fantástico!

Answer 3

Eu usei

awk -v BINMODE=rw '!($0 in a){a[$0];print}' infile >> outfile

BINMODE = rw: para manter os terminadores de fim de linha felizes. (Eu moro em um ambiente misto)

A lógica é simples.

Se a linha atual não estiver no array associativo, adicione-a ao array associativo e imprima para a saída.

Pode haver limitações de memória com essa abordagem. Para arquivos e conjuntos de arquivos muito grandes, usei variações sobre isso, usando o armazenamento de arquivos para superar as limitações.

    

Answer 4

A semântica de preservação de pedidos do seu problema tem uma propriedade maravilhosa: você pode subdividir o problema. Você pode fazer split -l 1000000 no arquivo de entrada; as peças de linha de 1000000 produzidas têm nomes ordenados por ordem lexical, o que é bom; depois, uniqifica as peças; e então (como uma segunda passagem) uniqify as saídas daqueles.

Isso resolve o problema de falta de memória (limitando o requisito de memória) à custa de transformá-lo em uma solução multipasse.

Especificamente:

Gerar dados de entrada:

$ cat make-uniqm-input.py
#!/usr/bin/env python
import random
n = 1000000
for i in xrange(0, n):
    print random.randint(1000, 2000)

$ python make-uniqm-input.py  > uniqm-input.txt

$ wc -l uniqm-input.txt
 1000000 uniqm-input.txt

Divida os dados de entrada:

$ split -l 10000 uniqm-input.txt

$ ls x?? | head
xaa
xab
xac
xad
xae
xaf
xag
xah
xai
xaj

$ ls x?? | wc -l
     100

$ cat x?? | wc -l
 1000000

Execute o uniqifier de uma só vez (retém todas as linhas de entrada exclusivas na memória):

# 'uniqm' is any order-preserving uniq implementation, such as
# gawk '!counts[$0]++'.
$ uniqm < uniqm-input.txt > output-no-splitting.txt

$ wc -l output-no-splitting.txt
    1001 output-no-splitting.txt

Execute o uniqifier em partes divididas (retém apenas linhas de entrada únicas de cada item na memória) e reduza como uma segunda passagem:

$ for x in x??; do uniqm < $x; done | uniqm > output-with-splitting.txt

$ wc -l output-with-splitting.txt
    1001 output-with-splitting.txt

Compare:

$ diff output-no-splitting.txt output-with-splitting.txt

$ head uniqm-input.txt
1506
1054
1623
1002
1173
1400
1226
1340
1824
1091

$ head output-with-splitting.txt
1506
1054
1623
1002
1173
1400
1226
1340
1824
1091

Eu não sei a proporção de linhas únicas para não-únicas em sua entrada, nem quão bem misturadas são as linhas de entrada - então há algum ajuste a ser feito em termos do número de arquivos divididos que você precisa.

    

Answer 5

Outra abordagem (que vale a pena postar como uma resposta separada) é: em vez da abordagem de arquivo dividido que cria arquivos temporários, faça o lote dentro do próprio software uniqifier. Por exemplo, usando uma implementação uniqifier Ruby para fins explicativos:

require 'set'
line_batch_count = 50000 # tunable parameter
lines_seen = Set.new
line_number = 0
ARGF.each do |line|
   line_number += 1
   if (line_number % line_batch_count) == 0
     lines_seen.clear
   end
   unless lines_seen.include? line
      puts line
      lines_seen << line
   end
end

A ideia é limpar o conjunto de hash de vez em quando. Então isso se torna iterativo:

$ cat uniqm-input.txt | ruby uniqm-capped.rb | wc -l
   20021

$ cat uniqm-input.txt | ruby uniqm-capped.rb | ruby uniqm-capped.rb | wc -l
    1001

$ cat uniqm-input.txt | ruby uniqm-capped.rb | ruby uniqm-capped.rb | head
1506
1054
1623
1002
1173
1400
1226
1340
1824
1091

Assim, você pode executar essa versão limitada repetidamente até que a contagem de linhas não mude de uma iteração para a próxima.

Observe que essa técnica com limite ilimitado é independente de linguagem: você pode limpar o array lines_seen a cada N linhas, esteja você usando awk, python, perl, C ++ etc. Há métodos claros para todos esses idiomas ; Acredito que awk delete não é padrão, mas é comum.