Questão Qual é a maneira mais rápida de contar o número de cada caractere em um arquivo?


Eu quero contar os G's N's e os caracteres "-" do A's T's C em um arquivo, ou cada letra, se necessário, existe um comando Unix rápido para fazer isso?


120


origem


Contando bases em fitas de DNA? - Indrek
Eu amo essa pergunta, tantas abordagens e ferramentas diferentes usadas para resolver o mesmo problema. - Journeyman Geek♦
Heh, este é o código de golfe de fronteira - Earlz
se alguém está interessado na versão do windows powershell: [System.IO.File]::ReadAllText("C:\yourfile.txt").ToCharArray() | Group-Object $_ | Sort Count -Descending - Guillaume86
Ok, eu acho que encontrei o jeito PS puro: Get-Content "C:\eula.3082.txt" | % { $_.ToCharArray() } | Group-Object | Sort Count -Descending - Guillaume86


Respostas:


Se você quiser alguma velocidade real:

echo 'int cache[256],x,y;char buf[4096],letters[]="tacgn-"; int main(){while((x=read(0,buf,sizeof buf))>0)for(y=0;y<x;y++)cache[(unsigned char)buf[y]]++;for(x=0;x<sizeof letters-1;x++)printf("%c: %d\n",letters[x],cache[letters[x]]);}' | gcc -w -xc -; ./a.out < file; rm a.out;

É um incrivelmente rápido pseudo-um-liner.

Um teste simples mostra que no meu Core i7 CPU 870 @ 2.93GHz conta com pouco mais de 600MB / s:

$ du -h bigdna 
1.1G    bigdna

time ./a.out < bigdna 
t: 178977308
a: 178958411
c: 178958823
g: 178947772
n: 178959673
-: 178939837

real    0m1.718s
user    0m1.539s
sys     0m0.171s

Ao contrário das soluções que envolvem ordenação, esta é executada em memória constante (4K), o que é muito útil, se o seu ficheiro for muito maior do que o seu RAM.

E, claro, com um pouco de graxa de cotovelo, podemos cortar 0,7 segundos:

echo 'int cache[256],x,buf[4096],*bp,*ep;char letters[]="tacgn-"; int main(){while((ep=buf+(read(0,buf,sizeof buf)/sizeof(int)))>buf)for(bp=buf;bp<ep;bp++){cache[(*bp)&0xff]++;cache[(*bp>>8)&0xff]++;cache[(*bp>>16)&0xff]++;cache[(*bp>>24)&0xff]++;}for(x=0;x<sizeof letters-1;x++)printf("%c: %d\n",letters[x],cache[letters[x]]);}' | gcc -O2 -xc -; ./a.out < file; rm a.out;

Redes com pouco mais de 1,1 GB / s terminando em:

real    0m0.943s
user    0m0.798s
sys     0m0.134s

Para comparação, testei algumas das outras soluções nesta página que pareciam ter algum tipo de promessa de velocidade.

o sed/awk solução fez um esforço valente, mas morreu depois de 30 segundos. Com um regex tão simples, espero que seja um bug no sed (GNU sed versão 4.2.1):

$ time sed 's/./&\n/g' bigdna | awk '!/^$/{a[$0]++}END{for (i in a)print i,a[i];}' 
sed: couldn't re-allocate memory

real    0m31.326s
user    0m21.696s
sys     0m2.111s

O método perl parecia promissor também, mas eu desisti depois de executá-lo por 7 minutos

time perl -e 'while (<>) {$c{$&}++ while /./g} print "$c{$_} $_\n" for keys %c' < bigdna 
^C

real    7m44.161s
user    4m53.941s
sys     2m35.593s

135



+1 Para uma solução sensata quando há muitos dados e não apenas alguns bytes. Os arquivos estão no cache de disco, não são? - Daniel Beck♦
O interessante é que ele tem uma complexidade de O (N) no processamento e O (1) na memória. Os pipes geralmente possuem O (N log N) no processamento (ou mesmo O (N ^ 2)) e O (N) na memória. - Martin Ueding
Você está esticando bastante a definição de "linha de comando". - gerrit
Enfrentamento épico dos requisitos da questão - Eu aprovo; p. superuser.com/a/486037/10165 <- alguém correu benchmarks, e isso é a opção mais rápida. - Journeyman Geek♦
Eu aprecio um bom uso de C nos lugares certos. - Jeff Ferland


grep -o foo.text -e A -e T -e C -e G -e N -e -|sort|uniq -c

Vai fazer o truque como um forro. Uma pequena explicação é necessária embora.

grep -o foo.text -e A -e T -e C -e G -e N -e - greps o arquivo foo.text para letras aeg eo caractere - para cada caractere que você deseja pesquisar. Também imprime um caractere por linha.

sort ordena em ordem. Isso define o cenário para a próxima ferramenta

uniq -c conta as ocorrências consecutivas duplicadas de qualquer linha. Neste caso, uma vez que temos uma lista ordenada de caracteres, obtemos uma contagem clara de quando os caracteres aparecem no primeiro passo

Se foo.txt continha a string GATTACA-é isso que eu recebo desse conjunto de comandos

[geek@atremis ~]$ grep -o foo.text -e A -e T -e C -e G -e N -e -|sort|uniq -c
      1 -
      3 A
      1 C
      1 G
      2 T

118



Magia unix sangrenta! : D - Pitto
se houver apenas caracteres CTAG nos seus arquivos, o próprio regexp se torna sem sentido, certo? grep -o. | classificar | uniq -c funcionaria igualmente bem, afaik. - sylvainulg
+1 Eu tenho usado grep há 25 anos e não sabia sobre -o. - LarsH
@JourneymanGeek: O problema com isso é que ele gera muitos dados que são encaminhados para classificar. Seria mais barato deixar um programa analisar cada personagem. Veja a resposta de Dave para uma resposta de complexidade de memória O (1) em vez de O (N). - Martin Ueding
@Pitto As versões nativas do Windows de coreutils estão amplamente disponíveis - basta perguntar ao Google ou algo assim - OrangeDog


Experimente este, inspirado na resposta do @ Journeyman.

grep -o -E 'A|T|C|G|N|-' foo.txt | sort | uniq -c

A chave é saber sobre a opção -o para grep. Isso divide a correspondência, de modo que cada linha de saída corresponda a uma única instância do padrão, em vez da linha inteira para qualquer linha que corresponda. Dado esse conhecimento, tudo o que precisamos é um padrão para usar e uma maneira de contar as linhas. Usando uma regex, podemos criar um padrão disjuntivo que corresponderá a qualquer um dos caracteres que você mencionar:

A|T|C|G|N|-

Isso significa "jogo A ou T ou C ou G ou N ou -". O manual descreve vária sintaxe de expressão regular que você pode usar.

Agora temos uma saída parecida com esta:

$ grep -o -E 'A|T|C|G|N|-' foo.txt 
A
T
C
G
N
-
-
A
A
N
N
N

Nosso último passo é mesclar e contar todas as linhas similares, que podem simplesmente ser realizadas com um sort | uniq -c, como na resposta do @ Journeyman. O tipo nos dá saída assim:

$ grep -o -E 'A|T|C|G|N|-' foo.txt | sort
-
-
A
A
A
C
G
N
N
N
N
T

Que, quando canalizada uniq -c, finalmente se parece com o que queremos:

$ grep -o -E 'A|T|C|G|N|-' foo.txt | sort | uniq -c
      2 -
      3 A
      1 C
      1 G
      4 N
      1 T

Adendo: Se você quiser totalizar o número de caracteres A, C, G, N, T e - em um arquivo, você pode canalizar a saída do grep através de wc -l ao invés de sort | uniq -c. Há muitas coisas diferentes que você pode contar apenas com pequenas modificações nessa abordagem.


45



Eu realmente preciso me aprofundar nos rabbitholes que são coreutils e regex. Isso é um pouco mais elegante do que o meu; p - Journeyman Geek♦
@JourneymanGeek: Lear regex vale a pena, já que é útil para muitas coisas. Basta entender suas limitações e não abuse do poder tentando fazer coisas fora do escopo das capacidades de regex, como tentando analisar XHTML. - crazy2be
grep -o '[ATCGN-]' poderia ser um pouco mais legível aqui. - sylvainulg


Um forro contando todas as letras usando Python:

$ python -c "import collections, pprint; pprint.pprint(dict(collections.Counter(open('FILENAME_HERE', 'r').read())))"

... produzindo uma saída amigável do YAML como esta:

{'\n': 202,
 ' ': 2153,
 '!': 4,
 '"': 62,
 '#': 12,
 '%': 9,
 "'": 10,
 '(': 84,
 ')': 84,
 '*': 1,
 ',': 39,
 '-': 5,
 '.': 121,
 '/': 12,
 '0': 5,
 '1': 7,
 '2': 1,
 '3': 1,
 ':': 65,
 ';': 3,
 '<': 1,
 '=': 41,
 '>': 12,
 '@': 6,
 'A': 3,
 'B': 2,
 'C': 1,
 'D': 3,
 'E': 25}

É interessante ver como a maioria das vezes o Python pode facilmente bater até mesmo em termos de clareza de código.


13





Semelhante ao Guru awk método:

perl -e 'while (<>) {$c{$&}++ while /./g} print "$c{$_} $_\n" for keys %c'

11





Depois de usar o UNIX por alguns anos, você se torna muito eficiente na vinculação de várias operações pequenas para realizar várias tarefas de filtragem e contagem. Todo mundo tem seu próprio estilo - alguns como awk e sed, alguns gostam cut e tr. Aqui está a maneira que eu faria:

Para processar um nome de arquivo específico:

 od -a FILENAME_HERE | cut -b 9- | tr " " \\n | egrep -v "^$" | sort | uniq -c

ou como um filtro:

 od -a | cut -b 9- | tr " " \\n | egrep -v "^$" | sort | uniq -c

Funciona assim:

  1. od -a separa o arquivo em caracteres ASCII.
  2. cut -b 9- elimina o prefixo od puts.
  3. tr " " \\n converte os espaços entre os caracteres para novas linhas, então há um caractere por linha.
  4. egrep -v "^$" se livrar de todas as linhas extras em branco que isso cria.
  5. sort reúne instâncias de cada caractere juntos.
  6. uniq -c conta o número de repetições de cada linha.

Eu alimentei "Olá, mundo!" seguido por uma nova linha e recebi isso:

  1 ,
  1 !
  1 d
  1 e
  1 H
  3 l
  1 nl
  2 o
  1 r
  1 sp
  1 w

10





o sed parte sendo baseada em @ Resposta do Guru, aqui está outra abordagem usando uniq, semelhante à solução de David Schwartz.

$ cat foo
aix
linux
bsd
foo
$ sed 's/\(.\)/\1\n/g' foo | sort | uniq -c
4 
1 a
1 b
1 d
1 f
2 i
1 l
1 n
2 o
1 s
1 u
2 x

9



Usar [[:alpha:]] ao invés de . dentro sed para corresponder apenas caracteres e não novas linhas. - Claudius
[[:alpha:]] vai falhar se você também está tentando combinar coisas como -, que foi mencionado na pergunta - Izkata
Corrigir. Pode ser melhor adicionar uma segunda expressão ao sed para primeiro filtrar todo o resto e depois corresponder explicitamente aos caracteres desejados: sed -e 's/[^ATCGN-]//g' -e 's/\([ATCGN-]\)/\1\n/g' foo | sort | uniq -c. No entanto, não sei como me livrar das novas linhas: - Claudius


Você pode combinar grep e wc para fazer isso:

grep -o 'character' file.txt | wc -w

grep pesquisa o (s) arquivo (s) fornecido (s) para o texto especificado e -o opção diz para imprimir apenas as correspondências reais (ou seja, os caracteres que você estava procurando), em vez do padrão que é imprimir cada linha na qual o texto da pesquisa foi encontrado.

wc imprime as contagens de byte, palavra e linha de cada arquivo ou, nesse caso, a saída do grep comando. o -w opção diz para contar palavras, com cada palavra sendo uma ocorrência de seu personagem de pesquisa. Claro, o -l opção (que conta as linhas) também funcionaria, já que grep imprime cada ocorrência do seu caractere de pesquisa em uma linha separada.

Para fazer isso por vários caracteres de uma só vez, coloque os caracteres em uma matriz e faça um loop sobre ela:

chars=(A T C G N -)
for c in "${chars[@]}"; do echo -n $c ' ' && grep -o $c file.txt | wc -w; done

Exemplo: para um arquivo contendo a string TGC-GTCCNATGCGNNTCACANN-, a saída seria:

A  3
T  4
C  6
G  4
N  5
-  2

Para mais informações, veja man grep e man wc.


A desvantagem dessa abordagem, como o usuário Journeyman Geek observa abaixo em um comentário, é que grep tem que ser executado uma vez para cada personagem. Dependendo do tamanho dos seus arquivos, isso pode gerar um impacto notável no desempenho. Por outro lado, quando feito dessa forma, é um pouco mais fácil ver rapidamente quais caracteres estão sendo procurados e adicioná-los / removê-los, pois eles estão em uma linha separada do resto do código.


7



eles precisariam repeti-lo por charecter eles querem ... eu adicionaria. Eu poderia jurar que há uma solução mais elegante, mas precisa de mais cutucando; p - Journeyman Geek♦
@JourneymanGeek Bom ponto. Uma abordagem que vem à mente é colocar os caracteres em uma matriz e passar por ela. Eu atualizei meu post. - Indrek
IMO muito complexo. Apenas use grep -e a-e t e assim por diante. Se você colocá-lo em uma matriz e percorrê-lo, você não teria que percorrer o ciclo grep uma vez por caractere? - Journeyman Geek♦
@JourneymanGeek Você provavelmente está certo. uniq -c também parece ser uma maneira melhor de obter uma saída bem formatada. Eu não sou guru * nix, o acima é exatamente o que eu consegui reunir do meu conhecimento limitado e algumas páginas de manual :) - Indrek
Eu também fiz, p, e uma das minhas tarefas no último termo envolveu a classificação de cerca de 5000 entradas do catálogo de endereços, e o uniq tornou muito mais fácil. - Journeyman Geek♦


Usando as linhas de sequência do 22hgp10a.txt, a diferença de tempo entre grep e awk no meu sistema faz com que o awk seja o caminho a seguir ...

[Editar]: Depois de ter visto a solução compilada de Dave, esqueça o awk também, pois ele completou em ~ 0.1 segundos neste arquivo para contagem completa de maiúsculas e minúsculas.

# A nice large sample file.
wget http://gutenberg.readingroo.ms/etext02/22hgp10a.txt

# Omit the regular text up to the start `>chr22` indicator.
sed -ie '1,/^>chr22/d' 22hgp10a.txt

sudo test # Just get sudo setup to not ask for password...

# ghostdog74 answered a question <linked below> about character frequency which
# gave me all case sensitive [ACGNTacgnt] counts in ~10 seconds.
sudo chrt -f 99 /usr/bin/time -f "%E elapsed, %c context switches" \
awk -vFS="" '{for(i=1;i<=NF;i++)w[$i]++}END{for(i in w) print i,w[i]}' 22hgp10a.txt

# The grep version given by Journeyman Geek took a whopping 3:41.47 minutes
# and yielded the case sensitive [ACGNT] counts.
sudo chrt -f 99 /usr/bin/time -f "%E elapsed, %c context switches" \
grep -o foo.text -e A -e T -e C -e G -e N -e -|sort|uniq -c

A versão insensível a maiúsculas e minúsculas do ghostdog foi concluída em ~ 14 segundos.

O sed é explicado na resposta aceita para essa questão.
O benchmarking é como na resposta aceita essa questão.
A resposta aceita por ghostdog74 era essa questão.


7



Você pode s/cache[letters[x]]/cache[letters[x]]+cache[toupper(letters[x])] meu para torná-lo insensível caso sem afetar sua velocidade. - Dave


Acho que qualquer implementação decente evita o tipo. Mas como também é má ideia ler tudo 4 vezes, acho que de alguma forma poderia gerar um fluxo que passa por 4 filtros, um para cada caractere, que é filtrado e onde os comprimentos de fluxo também são calculados de alguma forma.

time cat /dev/random | tr -d -C 'AGCTN\-' | head -c16M >dna.txt
real    0m5.797s
user    0m6.816s
sys     0m1.371s

$ time tr -d -C 'AGCTN\-' <dna.txt | tee >(wc -c >tmp0.txt) | tr -d 'A' | 
tee >(wc -c >tmp1.txt) | tr -d 'G' | tee >(wc -c >tmp2.txt) | tr -d 'C' | 
tee >(wc -c >tmp3.txt) | tr -d 'T' | tee >(wc -c >tmp4.txt) | tr -d 'N' | 
tee >(wc -c >tmp5.txt) | tr -d '\-' | wc -c >tmp6.txt && cat tmp[0-6].txt

real    0m0.742s
user    0m0.883s
sys     0m0.866s

16777216
13983005
11184107
8387205
5591177
2795114
0

As somas cumulativas são então em tmp [0-6] .txt .. então o trabalho ainda está em andamento

Existem apenas 13 canais nessa abordagem, que são convertidos para menos de 1 Mb de memória.
Claro que a minha solução favorita é:

time cat >f.c && gcc -O6 f.c && ./a.out
# then type your favourite c-program
real    0m42.130s

6



Este é um uso muito bom de tr. - adavid