Efficiently counting tokens column-wise in Bash/Awk/Perl

another awk solution

$ awk 'NR==FNR {for(i=1;i<=NF;i++) c[i,$i]++;next} 
               {f=line=""; 
                for(i=1;i<=NF;i++) 
                  {k=i SUBSEP $i; 
                   if(k in c) 
                     {f=1; line=line sprintf("%d %s",c[k],$i); delete c[k]}; 
                   line=line "\t"} 
                   if(f) print line}' file{,}


4 Lorem 3 dolor 2 sit   2 amet  1 consectetur
        1 ipsum 1 dolor 2 sit   2 ,
                1 ipsum         1 !

Edit by Ed Morton to show the same script pretty-printed by gawk -o-:

NR == FNR {
    for (i = 1; i <= NF; i++) {
        c[i, $i]++
    }
    next
}

{
    f = line = ""
    for (i = 1; i <= NF; i++) {
        k = i SUBSEP $i
        if (k in c) {
            f = 1
            line = line sprintf("%d %s", c[k], $i)
            delete c[k]
        }
        line = line "\t"
    }
    if (f) {
        print line
    }
}

I've written a pure Perl implementation that has one dependency for rendering the output. I've tested it against the complete works of William Shakespeare from Project Gutenberg, which is a 5.5MB text file. On my machine that took about 34s and consumed a max of 180MB of memory.¹

On my machine, this took roughly 5 seconds.

use strict;
use warnings;
use feature 'say';
use Text::Table::Tiny 'generate_table';

# read line by line, split into words on whitespace, count per column
my @counts;
while (<>) {
    my $i;
    $counts[$i++]->{$_}++ for split;
}

# sort columns into a new datastructure
my ( $row_count, @sorted_cols ) = (0);
for (my $col = 0; $col <= $#counts; $col++) {
        push @{ $sorted_cols[$col] },
            map [ $counts[$col]->{$_}, $_ ],
            sort {
                # this sorts on count first, and ascii-betical second
                $counts[$col]->{$b} <=> $counts[$col]->{$a} || $a cmp $b
            } keys %{ $counts[$col] };
        $row_count = $#{ $sorted_cols[$col] }
            if $#{ $sorted_cols[$col] } > $row_count;
}

# output
say generate_table(
    rows => [
        map {
            my $row = $_;
            [
                map $_->[$row] ? @{ $_->[$row] } : (q{}, q{}), @sorted_cols
            ];
        } 0 .. $row_count
    ],
    style       => 'norule'
);

The data is read line by line. Perl's <> operator will either read from STDIN or open and real all filenames passed in as command line arguments.

The first pass over the data counts occurrences of each word per column, builds up a data structure with these and discards the actual text. It takes advantage of the bare form of split, which makes it behave like awk, stripping off any whitespace.

The second block of code will iterate the counts and sort them, producing a new data structure that holds two columns (count and word) per input column. Sorting is done on count descending, and on word ascending. We also figure out how many rows of output we need to generate, because that depends on the longest column here.

Lastly, we use Text::Table::Tiny to generate the output. You can get that from CPAN or your distribution repository.

^{1) See revision history for previous version}

1. If I remove the step with the tempfile, and pipe the original pipeline into the script, I still get an output, but not the expected one. Not sure what's going on.

stdin can only be read once. When you read something then it is gone. This is a problem for for i in {1..3}; do cut -f $i; done. In the first iteration cut reads the whole file but discards most of its columns except the first one. Nevertheless, the other columns were read and are therefore gone. In the next iteration the file is empty and cut -f2 and cut -f3 won't print anything. Since you executed all cuts in parallel using & all of them will read a bit of the input but none will read everything.

2. Any way I can avoid the whole tempfile business? In some cases, the input may be too large to hold in memory.

You can use variables instead of temporary files as long as you have enough memory. With the following approach you don't need to hold the whole input in memory, but only the result. I guess that shouldn't be a problem.

Skeleton of an AWK Solution

awk '{
  for (col = 1; col <= NF; ++col) {
    ++count[col " " $col]
  }
} END {
  for (colWord in count) {
   split(colWord, s, " ")
   col=s[1]
   word=s[2]
   print col " " count[colWord] " " word
  }
}' "$@" | sort -k1,1n -k2,2nr

This prints

1 4 Lorem
2 3 dolor
2 1 ipsum
3 2 sit
3 1 dolor
3 1 ipsum
4 2 amet
4 2 sit
5 2 ,
5 1 !
5 1 consectetur

But transforming this into the final output is hell. I'd advise to use any language that supports real multidimensional arrays and sorting.

First, let's generate a more interesting example. This is easy in Python:

from pathlib import Path 
import string 
import random 

p='/tmp/bigfile.txt'

target=string.digits+string.ascii_letters+'!#$%&()*+,-./:;<=>?@[]^_`{|}~.'
tgt=300_000
toks=set()

while len(toks)<tgt:
    toks.add(''.join(random.choices(target, k=random.randrange(1,15))))
    
toks=list(toks) 

tgt=100_000_000
out={0:[]}
while sum(len(e) for e in out.values())<tgt:
    for key in range(1,11):
        out.setdefault(key, []).append(random.choice(toks))
    out[0].append('foo')
    
with open(p, 'w') as f: 
    for j in range(len(out[0])):
        f.write('\t'.join([out[i][j] for i in range(11)])+'\n')

Since there will be 300,000 unique tokens between 1 and 15 characters long and 100,000,000 total, the average count should be near 300 for each token or roughly 30 for each token in each column.

Now run wc on the resulting file:

$ wc bigfile.txt
 9090910 100000010 885069908 bigfile.txt

The file is 9,090,910 lines, 100,000,010 words and 885,069,908 bytes.

Now you can count uniques with this awk:

$ awk '{for (i=1;i<=NF;i++) cnt[$i]++} END{for (e in cnt) print cnt[e], e}' bigfile.txt | sort -n | tail -n 2
388 e!,#?
9090910 foo

You can also run the same awk though head to see the least frequent. Column 0 has nothing but foo in it and acts as a line count later...

Here is a Ruby to process this file. It uses sparse matrices to hold the counts of tokens and also lines up the digits and tokens of the output into a table.

This will also handle input that has a variable number of columns.

Ruby is a lovely language, but not known for speed. This is likely fairly memory efficient, however, and is processing the file in one pass.

ruby -lane '
BEGIN{ h = Hash.new { |h,k| h[k] = Hash.new(0) } 
        w=Hash.new(0); cols=0; max_cnt=Hash.new(0) }

cols=$F.length()>cols ? $F.length() : cols
$F.each_with_index {|f, i| 
        h[i][f]+=1 
        max_cnt[i]=h[i][f]>max_cnt[i] ? h[i][f] : max_cnt[i]
        w[i]=f.length()>w[i] ? f.length : w[i]
} 

END{ 
    max_cnt.each { |k,v| max_cnt[k]=Math::log10(v).to_i+2 }
    rows=h.max_by{ |k, sl| sl.length() }[1].length()
    h.each {|k,v| h[k]=h[k].sort_by {|k,v| -v }
        .map{|tok,cnt| sprintf("%*d %-*s ",max_cnt[k], cnt, w[k], tok) }
    }
    (0..rows).each {|i| s=""
        (0..cols-1).each {|j| 
            x=h[j][i]==nil ? " "*h[j][0].length : h[j][i] 
            s+=x 
        }
        puts s
    }
}' bigfile.txt >bigproc.txt

With the generated file, the head and tail are:

$ head -n 2 bigproc.txt
 9090910 foo  60 8[K(`=@irD69    59 )*2`t/o         59 =Ez!O           60 V5`;z           61 &_iX]#1         58 ai@Ita+mMl.D    57 W9)6,LB         59 f^>kE#]/]2I.F   58 YH@?nR@xVI.v].  61 <A8            
              60 O5w&]V0I//JQ0   58 ?>HSLYM+        58 ExB`xSt[,Gk     57 SE{e            60 `Aeeb~Wp<+&4R[  56 .aP             57 QoN.W)          58 JoZ<KQrE        57 Xk9             58 (A.O 

And:

$ tail -n 3 bigproc.txt 
              10 N;rZ            10 #kTm            10 yA^&^            9 e<5}=Q8;e.      10 7Hy$             9 OZ36k61<xKo     11 -^@)0y}wQ(s      8 f8ECm.dK9       10 v4u              9 Cxu|/f69$e     
               9 +?r|T;           9 ]qLWb[aM=        9 Jul@xGw          9 =]#zPhy9$w/s!    9 $/YZc7&D|        8 EgA])%(         10 !XYWwuM0y2oO     7 }ty&J[G.Ld^w     8 PPMB@WbL<>E0S    9 spLPi.x)e9     
                                                                                                                                                                                                       

The example file is processed in 1:36 and uses 667 MB peak memory.