Какой самый быстрый способ подсчитать количество каждого символа в файле?

Я хочу считать символы A's's's's's's's's и «-» в файле, или каждую букву, если это необходимо, есть ли быстрая команда Unix для этого?

Если вам нужна настоящая скорость:

 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; 

Это невероятно быстрый псевдо-лайнер.

Простой тест показывает, что на моем процессоре Core i7 870 @ 2,93 ГГц он составляет чуть более 600 МБ / с:

 $ 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 

В отличие от решений, связанных с сортировкой, этот работает в постоянной (4K) памяти, что очень полезно, если ваш файл намного больше вашего бара.

И, конечно, с небольшим количеством локтевой смазки, мы можем сбрить 0,7 секунды:

 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; 

Сетки чуть более 1,1 ГБ / с заканчиваются в:

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

Для сравнения, я тестировал некоторые другие решения на этой странице, которые, казалось, имели какое-то обещание скорости.

Решение sed / awk сделало отважное усилие, но умерло через 30 секунд. С таким простым регулярным выражением, я ожидаю, что это будет ошибкой в ​​sed (версия GNU версии 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 

Метод perl казался многообещающим, но я сдался после запуска в течение 7 минут

 time perl -e 'while (<>) {$c{$&}++ while /./g} print "$c{$_} $_\n" for keys %c' < bigdna ^C real 7m44.161s user 4m53.941s sys 2m35.593s 

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

Будет делать трюк как один лайнер. Однако необходимо небольшое объяснение.

grep -o foo.text -e A -e T -e C -e G -e N -e - greps файл foo.text для букв a и g и символ - для каждого символа, который вы хотите найти. Он также печатает один символ строки.

sort сортирует его по порядку. Это создает основу для следующего инструмента

uniq -c подсчитывает повторяющиеся последовательные вхождения любой строки. В этом случае, поскольку у нас есть отсортированный список символов, мы получаем опрятный счет, когда символы, которые мы выгрузили на первом шаге

Если foo.txt содержит строку GATTACA- это то, что я получил от этого набора команд

 [[email protected] ~]$ 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 

Попробуйте этот, вдохновленный ответом @ Journeyman.

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

Ключ знает о опции -o для grep . Это разделяет совпадение, так что каждая выходная строка соответствует одному экземпляру шаблона, а не всей строке для любой строки, которая соответствует. Учитывая эти знания, все, что нам нужно, это шаблон для использования и способ подсчета строк. Используя регулярное выражение, мы можем создать дизъюнктивный шаблон, который будет соответствовать любому из символов, которые вы упоминаете:

 A|T|C|G|N|- 

Это означает «соответствие A или T или C или G или N или -». В руководстве описывается синтаксис регулярных выражений, который вы можете использовать .

Теперь у нас есть вывод, который выглядит примерно так:

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

Наш последний шаг – объединить и подсчитать все похожие строки, которые можно просто выполнить с помощью sort | uniq -c sort | uniq -c , как в ответе @ Journeyman. Сортировка дает нам вывод следующим образом:

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

Который, когда он передается через uniq -c , в конце концов напоминает то, что мы хотим:

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

Добавление: если вы хотите суммировать количество символов A, C, G, N, T и – в файле, вы можете вывести grep-выход через wc -l вместо sort | uniq -c sort | uniq -c . Есть много разных вещей, которые вы можете рассчитывать только с небольшими изменениями в этом подходе.

Один лайнер, подсчитывающий все буквы с помощью Python:

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

… создавая дружественный вывод YAML следующим образом:

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

Интересно посмотреть, как Python в течение большей части времени может легко бить даже bash с точки зрения ясности кода.

Подобно методу awk Гуру:

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

После использования UNIX в течение нескольких лет вы очень хорошо разбираетесь в объединении нескольких небольших операций для выполнения различных задач фильтрации и подсчета. У каждого свой стиль – некоторые вроде awk и sed , некоторые вроде cut и tr . Вот как я это сделаю:

Для обработки определенного имени файла:

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

Или как фильтр:

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

Он работает следующим образом:

  1. od -a отделяет файл от символов ASCII.
  2. cut -b 9- исключает префикс od puts.
  3. tr " " \\n преобразует пробелы между символами в строки новой строки, так что в строке есть один символ.
  4. egrep -v "^$" избавляется от всех лишних пустых строк, которые это создает.
  5. sort собирает экземпляры каждого символа вместе.
  6. uniq -c подсчитывает количество повторений каждой строки.

Я накормил его «Привет, мир!». А затем новая строка и получила следующее:

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

Часть sed основывается на ответе @ Guru , вот еще один подход с использованием uniq , аналогичный решению Дэвида Шварца.

 $ 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 

Вы можете комбинировать grep и wc для этого:

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

grep ищет заданный файл (ы) для указанного текста, а опция -o сообщает ему только распечатывать фактические совпадения (т. Е. Символы, которые вы искали), а не по умолчанию, который должен печатать каждую строку, в которой Текст поиска был найден.

wc печатает байты, слова и строки для каждого файла или в этом случае вывод команды grep . Опция -w указывает, что она подсчитывает слова, причем каждое слово является появлением вашего символа поиска. Конечно, опция -l (которая подсчитывает строки) будет работать, так как grep печатает каждое вхождение вашего символа поиска в отдельной строке.

Чтобы сделать это для нескольких символов одновременно, поместите символы в массив и зациклитесь на нем:

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

Пример: для файла, содержащего строку TGC-GTCCNATGCGNNTCACANN- , выход будет:

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

Для получения дополнительной информации см. man grep и man wc .


Недостатком этого подхода, как отмечает пользователь Journeyman Geek ниже в комментарии, является то, что grep нужно запускать один раз для каждого символа. В зависимости от того, насколько велики ваши файлы, это может привести к заметному поражению производительности. С другой стороны, когда это делается, немного проще быстро увидеть, какие символы ищутся, и добавлять / удалять их, поскольку они находятся на отдельной строке от остальной части кода.

Используя строки последовательности из 22hgp10a.txt, разница во времени между grep и awk в моей системе делает использование awk способом …

[Edit]: После того, как скомпилированное решение Dave забудет awk, его завершение через ~ 0,1 секунды в этом файле для полного учета чувствительности к регистру.

 # 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 

Нечувствительная к регистру версия ghostdog завершена за ~ 14 секунд.

Сед объясняется в принятом ответе на этот вопрос .
Бенчмаркинг как в принятом ответе на этот вопрос .
Принятый ответ ghostdog74 был на этот вопрос .

Я думаю, что любая достойная реализация избегает сортировки. Но поскольку это также плохая идея читать все 4 раза, я думаю, что можно каким-то образом создать поток, который проходит через 4 фильтра, по одному для каждого символа, который отфильтровывается и где длины потоков также каким-то образом вычисляются.

 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 

Кумулятивные суммы затем находятся в tmp [0-6] .txt .. так что работа все еще продолжается

В этом подходе всего 13 труб, которые преобразуются в менее 1 Мб памяти.
Конечно, мое любимое решение:

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

Я не знал о uniq и о grep -o , но, поскольку мои комментарии к @JourneymanGeek и @ crazy2be были такими, возможно, я должен был превратить его в своего собственного автора:

Если вы знаете, что в вашем файле есть только «хорошие» символы (те, которые вы хотите подсчитать), вы можете пойти

 grep . -o YourFile | sort | uniq -c 

Если нужно подсчитать только некоторые символы, а другие нет (т.е. разделители)

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

Первый использует подстановочный знак регулярного выражения . , Которые соответствуют любому одиночному символу. Второй использует «набор принятых символов» без определенного порядка, за исключением того, что - должен быть последним ( AC интерпретируется как «любой символ между A и C ). В этом случае необходимы котировки, чтобы ваша оболочка не пыталась расширять это, чтобы проверять односимвольные файлы, если они есть (и вызывать ошибку «нет совпадения», если нет).

Обратите внимание, что «сортировка» также имеет флаг -u nique, так что он только сообщает о событиях один раз, но нет флага компаньона для подсчета дубликатов, поэтому uniq действительно является обязательным.

Глупый:

 tr -cd ATCGN- | iconv -f ascii -t ucs2 | tr '\0' '\n' | sort | uniq -c 
  • tr для удаления ( -d ) всех символов, но ( -c ) ATCGN-
  • iconv для преобразования в ucs2 (UTF16, ограниченный 2 байтами), чтобы добавить 0 байт после каждого байта,
  • Другой tr для перевода этих символов NUL в NL. Теперь каждый персонаж находится на собственной линии
  • sort | uniq -c sort | uniq -c для подсчета каждой строки uniq

Это альтернатива варианту нестандартного (GNU) -o grep.

 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 }' 

Формат вывода не самый лучший …

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

Теория Операции:

  • $ ({Command | command} 2> tmp) перенаправляет stderr потока во временный файл.
  • Dd выводит stdin в stdout и выводит количество байтов, переданных stderr
  • Tr -d фильтрует один символ за раз
  • Grep и sort фильтруют вывод dd в порядке убывания
  • Awk вычисляет разницу
  • Sort используется только на этапе пост-обработки для обработки неопределенности порядка выписки экземпляров dd

Скорость, по-видимому, составляет 60 Мбит / с +

Пример файла:

 $ cat file aix unix linux 

Команда:

 $ 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 

Сочетание нескольких других

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

Добавить | sort -nr | sort -nr чтобы увидеть результаты по порядку частоты.

Короткий ответ:

Если позволяют обстоятельства, сравните размеры файлов с низкими наборами символов с одним без символов, чтобы получить смещение и просто считать байты.

Ах, но запутанные детали:

Это все персонажи Ascii. Один байт за. Файлы, конечно же, содержат дополнительные метаданные, предназначенные для различных материалов, используемых ОС и приложением, которое его создало. В большинстве случаев я ожидал бы, что они занимают одинаковое пространство независимо от метаданных, но я бы постарался поддерживать идентичные обстоятельства, когда вы сначала проверяете подход, а затем проверяете, что у вас есть постоянное смещение, прежде чем не беспокоиться об этом. Другой способ заключается в том, что разрывы строк обычно включают два символа пробела ascii, а любые вкладки или пробелы будут по одному. Если вы можете быть уверены, что они будут присутствовать, и нет никакого способа узнать, сколько заранее, я бы прекратил читать сейчас.

Это может показаться большим количеством ограничений, но если вы можете легко их установить, это будет мне самым легким / лучшим способом, если у вас есть тонна этих взглядов (что кажется вероятным, если это ДНК). Проверка тонны файлов на длину и вычитание константы будет быстрее, чем запуск grep (или аналогичного) на каждом из них.

Если:

  • Это простые несломанные строки в чистых текстовых файлах
  • Они находятся в идентичных файлах, созданных тем же ванильным неформатирующим текстовым редактором, как Scite (вставка в порядке, если вы проверяете пробелы / возвращает) или какую-то базовую программу, которую кто-то написал

И две вещи, которые не могут иметь значения, но я бы испытал сперва

  • Имена файлов имеют одинаковую длину
  • Файлы находятся в одном каталоге

Попробуйте найти смещение, выполнив следующие действия:

Сравните пустой файл с одним с несколькими легкомысленными персонажами с одним символом. Если вычесть пустой файл из двух других файлов, вы получите количество байт, соответствующее счету символов, и все будет готово. Проверьте длину файла и вычитайте пустую сумму. Если вы хотите попытаться определить многострочные файлы, большинство редакторов присоединяют два специальных однобайтовых символа для разрывов строк, поскольку Microsoft обычно игнорирует Microsoft, но вам нужно по крайней мере grep для белых пробелов, в этом случае Вы могли бы также сделать все это с помощью grep.

Способ Haskell :

 import Data.Ord import Data.List import Control.Arrow main :: IO () main = interact $ show . sortBy (comparing fst) . map (length &&& head) . group . sort 

Он работает следующим образом:

 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 ... 

Компиляция и использование:

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

Возможно, не для больших файлов.

Быстрый взлом perl:

 perl -nle 'while(/[ATCGN]/g){$a{$&}+=1};END{for(keys(%a)){print "$_:$a{$_}"}}' 
  • -n : Итерировать по входным строкам, но ничего не печатать для них
  • -l : автоматическая -l полосы или добавление строк
  • While: перебирать все вхождения ваших запрошенных символов в текущей строке
  • END : в конце напечатайте результаты
  • %a A: Хэш, где хранятся значения

Символы, которые вообще не встречаются, не будут включены в результат.

Давайте будем гением компьютера.