How to search for a string in a very large file with very long lines?

Question

It turns out I was accidentally using grep wrong yesterday. I just checked my bash history and saw what I was executing:

grep search-string-here -f large-file-with-long-lines.txt

And that was what was causing the memory exhaustion.

Executing:

grep search-string-here large-file-with-long-lines.txt

...has the desired behavior.

Thanks to @αғsнιη for pointing to the question with a similar mistake, and to @EdMorton and @ilkkachu for correcting my assumptions about the length of the lines and how grep and awk use memory.

Below is the original question (though it seems I was wrong about the long lines not being able to fit in 8 GB of RAM) and @EdMorton's accepted answer.

I have a very large file (over 100 GB) with very long lines (can't even fit in 8 GB RAM) and I want to search it for a string. I know grep can't do it because grep tries to put entire lines into memory.

So far the best solution I've come up with is:

awk '/search-string-here/{print "Found."}' large-file-with-long-lines.txt

I'm actually happy with this solution, but I'm just wondering if there is some more intuitive way to do it. Maybe some other implementation of grep?

Answer 1

Here's simple a partial solution which only works if there's a character that does not appear in the string (or regexp) to search for, but appears often enough on the line so that the interval between occurrences of this character always fits in memory. For example, suppose each line is a very long list of relatively short semicolon-separated fields.

<large-file-with-long-lines.txt tr ';' '\n' | grep 'search-string-here'

---

Here's a different partial solution that works if the occurrences always start at a multiple of N characters after the beginning of the line, for some fixed N. It uses fold to wrap lines and ag to do a multiline search. In this example, the occurrences are known to always start 3*x characters after the beginning of the line.

<large-file-with-long-lines.txt fold -w3 | ag $'cat\ntag\ngag\nact'

This can be generalized to arbitrary string searches by repeating the search for each offset.

<large-file-with-long-lines.txt fold -w3 | ag $'fee\n-fi\n-fo\n-fu\nm|fe\ne-f\ni-f\no-f\num|f\nee-\nfi-\nfo-\nfum'

Note that this can have false positives if the string happened to be almost present, but with a line break in the middle.

Answer 2

This would be slow as it reads the input file several times (once per char in the string you want to find, each time in strings the size of that search string) but it should work on files of any size with lines of any size, using GNU awk for mult-char RS and RT (untested):

awk -v str='search-string-here' '
    BEGIN {
        lgth = length(str)
        RS = sprintf("%*s",lgth,"")
        gsub(/ /,".",RS)
        for (i=1; i<lgth; i++) {
            ARGV[ARGC++] = ARGV[1]
        }
    }
    RT == str {
        print "found"
        exit
    }
' file

It's setting RS to N .s, where N is the length of your search string, reading every chain of N characters from the input starting at char #1 comparing them to the search string and exiting if the current N chars from the input matches the search string. If there's no match on that pass it does the same again but starting from char #2, and so on til it's done that N times and so there are no more strings of length N in the input file to compare to the search string.

Note that the above is doing a string comparison, not a regexp comparison. To do a regexp comparison you'd have to determine the max length of the matching string some other way and then use the regexp comparison operator ~ instead of ==, e.g. if you know the matching string in the input can't be longer than 20 chars then you could do something like:

awk -v regexp='search-regexp-here' '
    BEGIN {
        lgth = 20
        RS = sprintf("%*s",lgth,"")
        gsub(/ /,".",RS)
        for (i=1; i<lgth; i++) {
            ARGV[ARGC++] = ARGV[1]
        }
    }
    RT ~ regexp {
        print "found"
        exit
    }
' file

but that regexp search has some flaws that the string search does not that you'd have to think about, e.g. if your search regexp includes ^ or $ for boundaries then you could get a false match above as it creates string start/end boundaries around every char as the N-chars-long strings are being read.