How can I match this text in awk, printing line numbers for matches?

Question

I have a text file thousands (roughly 148,000 lines long) that consists of a lot of sequences like this:

b 29.
b 52.
c 84.
c 83.
c 94.
c 93.
c 61.
b 38.
c 81.
c 92.
c 28.
c 37.
c 27.

... and since the file is so large, I want to be able to search for patterns like this (non-functional one-liner):

grep "b\ 34.\nc53.\nb\ 54.\na\ 45.\nd\ 44.\nd\ 63.\nd\ 64.\n" filename

It seems like awk is a good choice.

How can I do that, and print line numbers for matches too?

Answer 1

Here's an awk script that searches a multiline string (matches must consist of whole lines). It receives the text to search for in the variable needle. The script works by building a window of w lines (where w is the number of lines in needle) and comparing that against needle.

awk -v needle='b 38.\nc 81.\nc 92.\n' '
    BEGIN {
        if (substr(needle, length(needle)) == "\n")
            needle = substr(needle, 1, length(needle)-1);
        w = split(needle, needles, "\n");
        getline window
        for (i = 2; i < w; i++) {getline; window = window "\n" $0}
    }
    { window = window "\n" $0 }
    window == needle {print NR - w + 1}
    { window = substr(window, index(window, "\n") + 1) }
' <data.txt

This is not the most efficient way to search for a substring, because each line in the data file is compared with each line in the pattern. There are more efficient algorithms that manage to perform fewer comparisons by making some precomputations in the pattern, such as Knuth-Morris-Pratt.

For a file that fits comfortably in memory, I would read it all at once and perform the search in memory. If all you're looking for is a pattern match, this is easily done in Perl, but Perl lacks primitives to efficiently keep track of lines. Here's a Python script that looks for a multiline string (which must be passed as such).

import re, sys
needle = sys.argv[1]
haystack = sys.stdin.read()
pos = 0
line = 1
for m in re.finditer(needle, haystack):
    line += haystack.count("\n", pos, m.start())
    pos = m.start()
    print line

Usage: python -c '…' $'b 38.\nc 81.\nc 92.\n' <data.txt

Answer 2

I'd write it like this:

awk -v seven_lines="b 34.c 53.b 54.a 45.d 44.d 63.d 64." '
    seven_lines == l6 l5 l4 l3 l2 l1 $0 {print "pattern found at line " (NR-6)}
    {l6=l5; l5=l4; l4=l3; l3=l2; l2=l1; l1=$0}
'