6

Say, I have a file, and multiple regexes have to be searched in it and the number of matches for each regex has to be counted.

Thus, I cannot combine the patterns:

grep -Po '{regex_1}|{regex_2}|...|{regex_n}' file | wc -l

... as the number of occurences for each regex is required.

I obviously could:

occurences[i]=$(grep -Po "${regex[i]}" file | wc -l)

... but unfortunately, the files encountered may be quite large (> 1 GB) and there are many of patterns (in the range of thousands) to check for, making the process quite slow, as multiple reads of the same file would be involved.

Is there a way to do this in a fast manner?

  • Firstly you can share by grep -e 'regex_1' -e 'regex_2' ... but much better use -f option and put all regexes in a file by 1 line each one. – Costas Dec 31 '14 at 11:02
  • with GB we can not expect miracles... Can you tell us some more details about your regex and large file? – JJoao Dec 31 '14 at 12:45
5

Probably awk would be fastest shell tool here. You could try:

awk "/$regex1/ { ++r1 }
     /$regex2/ { ++r2 }"'
     END { print "regex1:",r1 "\nregex2:",r2 }' <infile

Of course if you need to use perl regular expressions like your question, then really perl is the only answer. However, awk does use extended expressions (like grep -E) as opposed to basic ones.

  • I think you have a perlism ($) creeping into your regex's... – mr.spuratic Dec 31 '14 at 17:21
  • @mr.spuratic, no the idea was that they would be shell variables, hence the double quotes around that section. – Graeme Dec 31 '14 at 17:25
  • Ah, got it. You could usefully print the regex too. – mr.spuratic Dec 31 '14 at 17:48
4

The fastest solution I can think is flex. Following is an untested skeleton:

%{
  int count[1000];
%}
%%

regex0  {count[0]++; }
regex1  {count[1]++; }
...
.|\n    {}

%%
int main(){
   yylex();
   // printf the counts;
}

flex makes a pretty good job in optimizing the automata and generates fast C code.

You have to recompile it if regexs change...

EDIT: If you implement and try any of the solutions, it would be interesting to see the times.

1

In case Python is an option, you could first memory-map the file and then run an incremental regex search over it, taking advantage of named groups to count pattern occurences. This solution is tolerant of large file sizes

from collections import Counter
import re, mmap, contextlib
c = Counter()
with open('data_file', 'r+') as f:
    with contextlib.closing(mmap.mmap(f.fileno(), 0)) as data:
            for m in re.finditer(r'(?P<pat1>regex1)|(?P<pat2>regex2)|(?P<pat3>regex3)',data):
                    c.update(k for (k, v) in m.groupdict().iteritems() if v)

print c.most_common()
[('pat3', 3), ('pat1', 2), ('pat2', 2)]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.