I have big text-data without spaces and without other rows in one line. In reality, the streams are 0.2 Gb/s, similar situation here, but in this task, counting occurrences which is more challenging computationally than just counting empty lines. The match is

585e0000fe5a1eda480000000d00030007000000cd010000

Example data subset is here called 30.6.2015_data.txt and its full binary data here called 0002.raw. The match occurs 1 time in 30.6.2015_data.txt but 10 times in the full data 0002.raw in one line. I prepared the txt data by xxd -ps 0002.raw > /tmp/1 && fold -w2 /tmp/1 > /tmp/2 && gsed ':a;N;$!ba;s/\n//g' /tmp/2 > /tmp/3. The faster implementation, the better. To prepare the mega string in column, you can use this xxd -ps 0002.raw > /tmp/1 && fold -w2 /tmp/1 > /tmp/2. My current rate is 0.0012 s per match i.e. 0.012 s per ten matches in the full data file, which is slow.

Grep does this in rows so not possible in counting. In Vim, %s/veryLongThing//gn is insufficient for the task. The command wc is giving only character, byte and lines so not correct tool but probably by combining it to something else. Possibly GNU Find and Sed combination but all implementations seems to be too complicated.

Outputs of Mikeserv's answer

$ cat 1.7.2015.sh 
time \
    ( export ggrep="$(printf '^ \376Z\36\332H \r \3 \a \315\1')" \
             gtr='\1\3\a\r\36HZ^\315\332\376'
             LC_ALL=C
      gtr -cs "$gtr" ' [\n*]' |
      gcut -sd\  -f1-6       |
      ggrep -xFc "$ggrep"
    ) <0002.raw

$ sh 1.7.2015.sh 
1

real    0m0.009s
user    0m0.006s
sys 0m0.007s

-----------

$ cat 1.7.2015.sh 
time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  ggrep="$(shift;IFS=\\;printf "\\$*")"    \
                gtr='\0\1\3\a\r\36HXZ^\315\332\376'      \
                LC_ALL=C i=0
        while [ "$((i+=1))" -lt 1000 ]
        do    gcat 0002.raw; done            |
        gtr -cd "$gtr" |gtr 'X\0' '\n '      |
        gcut -c-23    |ggrep -xFc "$ggrep"
    ) 

$ sh 1.7.2015.sh 
9990

real    0m4.371s
user    0m1.548s
sys 0m2.167s

where all tools are GNU coreutils and they have all options you provide in the code. They may however differ with GNU devtools. Mikeserv runs his code 990 times and there are 10 events so total 9990 events is correct.

How can you count the number of matches in a megastring efficiently?

  • 1
    But that's the hex again. Can you get the stream in binary? If you just pass the binary stream through od -An -tx1 you'll get the stream at 16 hexadecimally-econded bytes per line. My own preference is for od -An -tu1, though, which does it all in simple unsigned ints ranged 0 -255. And I'm showing -An there to drop the offset list, but you might keep it and first filter by the offsets you want, then filter for the strings you want. Anyway, to handle the long string thing, first break the stream by line, then find it. ...|fold -w2 – mikeserv Jun 30 '15 at 16:57
  • 1
    Anyway, where's the data? Because I'd like to try this on it. – mikeserv Jun 30 '15 at 17:02
  • 1
    How about LC_ALL=C grep -ao CDA | wc -l? – Stéphane Chazelas Jun 30 '15 at 20:39
  • 1
    @Masi - the string you're looking for - does it only occur the one time in 0002.raw? I get it in .010sec w/ time (export LC_ALL=C; tr 'X\0 \n' '\n X\0' </tmp/0002.raw | cut -c-23 | grep -xFc "$(printf '^ \376Z\36\332H \r \3 \a \315\1 ')"), but i only get one result. Are you definitely looking to count that one string's occurrence? I'm still not totally clear on what is wanted here. The command above should rule out any possibility of finding anything but the data you want. – mikeserv Jul 1 '15 at 2:14
  • 1
    @Masi - of cpurse you get 0 results. you name the variable $gtr and then call it like gtr "$tr". You need tonuse consistent names. – mikeserv Jul 1 '15 at 19:07
up vote 4 down vote accepted

The GNU implementation of grep (also found in most modern BSDs though the latest versions are a complete (mostly compatible) rewrite) supports a -o option to output all the matched portions.

LC_ALL=C grep -ao CDA | wc -l

would then count all the occurrences.

LC_ALL=C grep -abo CDA

to locate them with their byte offset.

LC_ALL=C makes sure grep doesn't try and do some expensive UTF-8 parsing (though here, with a fixed ASCII string search, grep should be able to optimise away the UTF-8 parsing by itself). -a is another GNUism to tell grep to consider binary files.

  • Is the mostly compatible difference about the GNU implementation's dependence on GNU's C libs' perlesque regexp? And the CDA thing - is that because of my comment before, or is it also in 585e0000fe5a1eda480000000d00030007000000cd010000? ...because I didn't try to parse that... I think the CDA thing is relevant, but I'm not certain... – mikeserv Jun 30 '15 at 21:49
  • I am evaluating the performance of these commands. They at least 2x faster than my current command. I get much fluctuation in timing their performance. I am studying how to do timing better here unix.stackexchange.com/q/213230/16920 – Léo Léopold Hertz 준영 Jul 1 '15 at 5:51
  • You can probably speed things up a little with a hand-crafted Boyer-Moore (window sliding can be optimized for infinite streams). But as far as standard tools are concerned, the above is about as fast as it gets. – lcd047 Jul 1 '15 at 8:38
  • 1
    @mikeserv, they diverged slightly after they were rewritten from scratch (different options and option handling (for instance wrt -r IIRC). BSDs grep are now backward compatible to the old version of GNU grep they were originally based on, but no longer to recent versions of GNU grep or even between each other (IIRC Apple's one diverged from FreeBSD for instance). – Stéphane Chazelas Jul 1 '15 at 9:13
  • 2
    @Masi, timing will be affected by the system's caching. If the data is not in cache, then the bottleneck will be disk I/O, not grep. – Stéphane Chazelas Jul 1 '15 at 9:14

So I took your hex string and printed it out to bytes, but I swapped the NULs for <spaces> (mostly because I can't figure on how to get a NUL in a grep pattern):

time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  grep="$(shift;IFS=\\;printf "\\$*")"    \
                tr='\0\1\3\a\r\36HXZ^\315\332\376'      \
                LC_ALL=C i=0
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw; done     |
        tr -cd "$tr" |tr 'X\0' '\n ' |
        cut -c-23    |grep -xFc "$grep"
    )

The tr variable there is made up of octal escapes/ASCII chars for the byte values of your hex string because I wanted tr to -delete its complement. I then made sure that the longest line grep could attempt to match against would be -c-23 bytes with cut, and that the string would always head a line by translating X chars to \newlines while also swapping the NULs for <spaces>.

I'm cating the raw binary at the pipeline 999 times here. Because there are 10 matches in the file, the results are:

9990
1.06s user 0.94s system 65% cpu 3.054 total

Now I also tested...

time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  LC_ALL=C i=0 grep="$(IFS=\\;printf "\\$*")"
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw;  done    |
        tr '\0 ' ' \0'   |
        grep -aFo "$grep"| wc -l
    )

I use wc -l there but in my tests it didn't seem to make any difference execution time-wise to use -caFo and drop wc altogether. The counts were the same either way, anyway. The results for this:

9990
1.56s user 1.46s system 82% cpu 3.648 total

Now these two sets of commands are not equivalent. While it does seem to complete a little faster by squeezing out unwanted bytes w/ tr first, one thing that means is while you can get the count, you cannot get the offsets as you might by adding the -b switch to grep in the second example...

time \
   (    set     x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  LC_ALL=C i=0 grep="$(IFS=\\;printf "\\$*")"
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw;  done    |
        tr '\0 ' ' \0'     |
        grep -baFo "$grep" | sed -n l
   )

...

241133568:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241157720:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241181872:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241206024:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241230176:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241254328:X^  \376Z\036\332H   \r \003 \a   \315\001  $

1.59s user 1.41s system 85% cpu 3.496 total

And so which you choose, I guess, will depend on what you want. For just a count, probably the tr -cd will be better - it reliably completed a half second quicker than the other every time - but it is not as versatile, and so maybe, if your grep will support it, grep -baFo could be what you need instead.

  • 1
    @Masi - All of the tools I used were standard, as far as I know - I didn't take advantage of any nonstandard extensions. They should all work w/ a POSIX toolset. I posted a list of offsets where the string can be found. – mikeserv Jul 1 '15 at 9:30
  • 1
    I swapped the NULs for \<spaces> (mostly because I can't figure on how to get a NUL in a grep pattern) - The shell can't handle NUL, but with GNU grep you can still pass the full binary pattern in a file: LC_ALL=C fgrep -abof needle 0002.raw | tr -cd '\n[:print:]'. This doesn't work with BSD grep though. – lcd047 Jul 1 '15 at 14:10
  • @lcd047 - that's pretty cool, but does doing that make it faster - like does it run as quickly as the tr? – mikeserv Jul 1 '15 at 19:04
  • 1
    @Masi - i pipe the 0002.raw file at the pipeline 999 times, and because there are 10 matches in that file, the result is 9990. – mikeserv Jul 1 '15 at 19:41
  • 1
    @lcd047 - you can feed grep its pattern file over a pipe, if it is otherwise searching a named file, and so, if what you say is true, probably: printf \\0\\1string\\1\\0' | grep -f- file would work as well, yeah? – mikeserv Jul 1 '15 at 20:12

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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