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

Question

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 rápido do Unix para fazer isso?

    

Answer 1

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

Diferentemente de soluções envolvendo classificação, esta é executada em memória constante (4K), o que é muito útil, se o seu arquivo for muito maior 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

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

A solução sed / awk fez um esforço valente, mas morreu após 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 também pareceu promissor, mas 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

    

Answer 2

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.

grep -o foo.text -e A -e T -e C -e G -e N -e - greps o arquivo foo.text para as letras a e geo caractere - para cada caractere que você deseja procurar. 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, como temos uma lista ordenada de caracteres, temos uma contagem clara de quando os caracteres aparecem no primeiro passo

Se foo.txt contivesse a string GATTACA- , isso é o que eu obteria 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

    

Answer 3

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 "combinar A ou T ou C ou G ou N ou -". O manual descreve a várias sintaxes de expressões regulares que você pode usar .

Agora temos uma saída semelhante a 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 semelhantes, que podem simplesmente ser realizadas com um sort | uniq -c , como na resposta do @ Journeyman. O tipo nos dá uma 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 canalizado através de 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 em vez de sort | uniq -c . Há muitas coisas diferentes que você pode contar apenas com pequenas modificações nessa abordagem.

    

Answer 4

Um forro contando todas as letras usando o Python:

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

... produzindo uma saída amigável para YAML assim:

{'\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.

    

Answer 5

Semelhante ao método awk do Guru:

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

    

Answer 6

Depois de usar o UNIX por alguns anos, você se torna muito eficiente em vincular várias pequenas operações para realizar várias tarefas de filtragem e contagem. Todo mundo tem seu próprio estilo - alguns como awk e sed , alguns como cut e tr . Aqui está o jeito 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 livra de todas as linhas extras em branco que isso cria.
5. sort reúne instâncias de cada caractere juntas.
6. uniq -c conta o número de repetições de cada linha.

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

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

    

Answer 7

A parte sed sendo baseada na resposta do @Guru , aqui está outra abordagem usando uniq , semelhante a David Schwartz ' solução.

$ cat foo
aix
linux
bsd
foo
$ sed 's/\(.\)/\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

    

Answer 8

Você pode combinar grep e wc para fazer isso:

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

grep procura o (s) arquivo (s) especificado (s) pelo texto especificado, e a opção -o informa para imprimir apenas as correspondências reais (ou seja, os caracteres que você estava procurando), em vez do padrão que é imprima 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 comando grep . A opção -w diz para contar palavras, sendo cada palavra uma ocorrência do seu caractere de pesquisa. É claro que a opção -l (que conta as linhas) também funcionaria, pois grep imprime cada ocorrência de 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, consulte man grep e man wc .

A desvantagem dessa abordagem, como o usuário Journeyman Geek observa abaixo em um comentário, é que grep precisa ser executado uma vez para cada caractere. Dependendo do tamanho dos seus arquivos, isso pode causar 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 pesquisados e adicioná-los / removê-los, pois eles estão em uma linha separada do resto do código.

    

Answer 9

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 esta questão .
O benchmarking é como na resposta aceita a esta questão
. A resposta aceita por ghostdog74 foi pergunta .

    

Answer 10

Acho que qualquer implementação decente evita o tipo. Mas como também é uma má idéia 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 dos fluxos 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

    

Answer 11

Eu não sabia sobre uniq nem sobre grep -o , mas já que meus comentários sobre @JourneymanGeek e @ crazy2be tiveram esse apoio, talvez eu deva transformá-lo em uma resposta própria:

Se você sabe que há apenas "bons" caracteres (aqueles que você deseja contar) no seu arquivo, você pode ir para

grep . -o YourFile | sort | uniq -c

Se apenas alguns caracteres devem ser contados e outros não (ou seja, separadores)

grep '[ACTGN-]' YourFile | sort | uniq -c

O primeiro usa o curinga de expressão regular . , que corresponde a qualquer caractere único. O segundo usa um 'conjunto de caracteres aceitos', sem ordem específica, exceto que - deve vir por último ( A-C é interpretado como 'qualquer caractere entre A e C ). As cotas são necessárias nesse caso para que o seu shell não tente expandir isso para verificar arquivos de caractere único, se houver algum (e produzir um erro "no match" se nenhum).

Observe que "sort" também tem um sinalizador -u nique para que ele relate apenas as coisas uma vez, mas nenhum sinalizador complementar contenha duplicatas, portanto, uniq é de fato obrigatório.

    

Answer 12

Um bobo:

tr -cd ATCGN- | iconv -f ascii -t ucs2 | tr '
tr -cd ATCGN- | iconv -f ascii -t ucs2 | tr '%pre%' '\n' | sort | uniq -c
' '\n' | sort | uniq -c

• tr para excluir ( -d ) todos os caracteres, mas ( -c ) ATCGN -
• iconv para converter para ucs2 (UTF16 limitado a 2 bytes) para adicionar um byte de 0 após cada byte,
• outro tr para traduzir esses caracteres NUL para NL. Agora todo personagem está na sua própria linha
• sort | uniq -c para contar cada linha uniq

Essa é uma alternativa para a opção não padrão (GNU) -o grep.

    

Answer 13

time $( { tr -cd ACGTD- < dna.txt | dd | tr -d A | dd | tr -d C | dd | tr -d G |
dd | tr -d T | dd | tr -d D | dd | tr -d - | dd >/dev/null; } 2>tmp ) &&
grep byte < tmp | sort -r -g | awk '{ if ((s-$0)>=0) { print s-$0} s=$0 }'

O formato de saída não é o melhor ...

real    0m0.176s
user    0m0.200s
sys     0m0.160s
2069046
2070218
2061086
2057418
2070062
2052266

Teoria da operação:

• $ ({comando | comando} 2 > tmp) redireciona o stderr do fluxo para um arquivo temporário.
• dd gera stdin para stdout e gera o número de bytes passados para stderr
• tr -d filtra um caractere por vez
• grep e sort filtra a saída de dd para a ordem decrescente
• o awk calcula a diferença
• a classificação é usada apenas no estágio pós-processamento para lidar com a incerteza da ordem de saída das instâncias do dd

A velocidade parece ser de 60 MBps +

    

Answer 14

Arquivo de amostra:

$ cat file
aix
unix
linux

Comando:

$ sed 's/./&\n/g' file | awk '!/^$/{a[$0]++}END{for (i in a)print i,a[i];}'
u 2
i 3
x 3
l 1
n 2
a 1

    

Answer 15

Combinando alguns outros

chars='abcdefghijklmnopqrstuvwxyz-'
grep -o -i "[$chars]" foo|sort | uniq -c

Adicione | sort -nr para ver os resultados em ordem de frequência.

    

Answer 16

Resposta curta:

Se as circunstâncias permitirem, compare tamanhos de arquivo de conjuntos de caracteres baixos a um sem caracteres para obter um deslocamento e apenas contar bytes.

Ah, mas os detalhes emaranhados:

Esses são todos os caracteres Ascii. Um byte por. Os arquivos, é claro, têm metadados extras inseridos em uma variedade de itens usados pelo sistema operacional e pelo aplicativo que o criou. Na maioria dos casos, eu esperaria que eles ocupassem a mesma quantidade de espaço, independentemente dos metadados, mas tentaria manter circunstâncias idênticas quando você testasse a abordagem pela primeira vez e, em seguida, verificaria que você tem um deslocamento constante antes de não se preocupar com isso. A outra pegadinha é que as quebras de linha normalmente envolvem dois caracteres de espaço em branco ascii e quaisquer guias ou espaços seriam um em cada. Se você puder ter certeza de que elas estarão presentes e não há como saber quantas antes, eu pararia de ler agora.

Pode parecer um monte de restrições, mas se você puder estabelecê-las facilmente, isso me parece a abordagem mais fácil / de melhor desempenho se você tiver uma tonelada delas para analisar (o que parece provável se for o DNA). Verificar uma tonelada de arquivos por tamanho e subtrair uma constante seria mais rápido do que executar grep (ou similar) em cada um.

Se:

• Estas são strings simples e não quebradas em arquivos de texto puro
• Eles estão em tipos de arquivo idênticos criados pelo mesmo editor de texto sem formatação, como o Scite (o colar está bem, desde que você verifique espaços / devoluções) ou algum programa básico que alguém escreveu

E duas coisas que podem não ser importantes, mas eu testaria primeiro

• Os nomes dos arquivos são de tamanho igual
• Os arquivos estão no mesmo diretório

Tente encontrar o deslocamento fazendo o seguinte:

Compare um arquivo vazio a um com alguns caracteres facilmente contados por humanos para um com mais alguns caracteres. Se subtrair o arquivo vazio de ambos os outros dois arquivos, você terá contagens de bytes que correspondem à contagem de caracteres. Verifique os comprimentos de arquivo e subtraia esse valor vazio. Se você quiser tentar descobrir arquivos de várias linhas, a maioria dos editores anexa dois caracteres especiais de um byte para quebras de linha, já que um tende a ser ignorado pela Microsoft, mas você teria que pelo menos usar caracteres em espaço em branco. você pode muito bem fazer tudo com o grep.

    

Answer 17

Haskell :

import Data.Ord
import Data.List
import Control.Arrow

main :: IO ()
main = interact $
  show . sortBy (comparing fst) . map (length &&& head) . group . sort

funciona assim:

112123123412345
=> sort
111112222333445
=> group
11111 2222 333 44 5
=> map (length &&& head)
(5 '1') (4 '2') (3 '3') (2 '4') (1,'5')
=> sortBy (comparing fst)
(1 '5') (2 '4') (3 '3') (4 '2') (5 '1')
=> one can add some pretty-printing here
...

compilando e usando:

$ ghc -O2 q.hs
[1 of 1] Compiling Main             ( q.hs, q.o )
Linking q ...
$ echo 112123123412345 | ./q
[(1,'\n'),(1,'5'),(2,'4'),(3,'3'),(4,'2'),(5,'1')]%       
$ cat path/to/file | ./q
...

não é bom para arquivos enormes, talvez.

    

Answer 18

Quick perl hack:

perl -nle 'while(/[ATCGN]/g){$a{$&}+=1};END{for(keys(%a)){print "$_:$a{$_}"}}'

• -n : Iterar sobre linhas de entrada, mas não imprime nada para elas
• -l : descasque ou adicione quebra de linha automaticamente
• while : iterar todas as ocorrências de seus símbolos solicitados na linha atual
• END : no final, imprima os resultados
• %a : hash onde os valores são armazenados

Caracteres que não ocorrem de forma alguma serão incluídos no resultado.