Matching many files against many patterns in Java

Question

Here is what i want to do: on the one side, i have a text file with ~100.000 string patterns (each String is in a new line), most of them are about 40-200 characters long. On the other side, i have ~130.000 files with sizes anywhere from a just a few kiloBytes up to large files with several hundered megaBytes (however, 95% of the files are just a few 100kB).

Now, i want to match every one of the 130k files against all of the 100k patterns.

Right now i am doing the matching using the .contains() method, here is some example code:

String file = readFile(somefile.pdf); // see benchmark below
String[] patterns = readFile(patterns.txt).split("\n"); // read 100k patterns into an array
for(int i = 0; patterns.length-1; i++){
    if(file.contains(patterns[i])){
        // pattern matched 
    }else{
        // patttern not matched
    }
}

I am running this on a rather powerful desktop system (4core 2.9ghz, 4GB memory, SSD) and i get very poor performance:

When somefile.pdf is a 1.2mb file, a match against all 100k patterns takes ~43 seconds. A 400kb is ~14seconds. A 50kb file is ~2 Seconds

This is way too slow, i need something with 40x-50x times the performance. What can i do?

Answer 1

Creating a search index over these 130k files would probably the most sustainable approach.

A similar question was answered over here: Searching for matches in 3 million text files

Libraries / Tools that are typically used in Java environments:

• Lucene
• Solr
• elasticsearch

Answer 2

You can introduce some shortcuts if you haven't already.

If a file needs to match all patterns, you can return false as soon as it doesn't match a pattern. Order your patterns to put the ones most likely to fail at the top.
(If a file on the other hand needs to match any pattern, you can return true as soon as the first pattern matches. In this case, order your patterns to put the ones most likely to match at the top.)

If you want all files to match all patterns, make sure you load the smallest files first. That way, you process the ones that are the easiest to compare first. You could also try to load them so that you process the ones most likely to fail first, but that seems (to me) harder to do for the files as for the patterns.

---

Also, make sure you load your patterns only once.

Answer 3

If you're only comparing words, one possible optimization could be to index the 130'000 files beforehand. In the most simple case this would go like (pseudo-code):

for file in files
  read file as string
  split string into tokens (e.g. by white-space)
  set = all tokens in a HashSet
  for every pattern in patterns
      if set.contains(pattern)
          // pattern found
      else
          // pattern not found

The problem with your current solution is the usage of arrays, which lead to a full-table scan in database jargon (what you really are sets, or more sphisticated solutions like Apache Lucene).

Answer 4

You might want constructing and checking out performance of a gigantic regex (i.e. Pattern.compile("word1|word2|word3|...") as it builds a FSA which should have a much better performance than a naive approach.

Similar question:

What's the most efficient way to find one of several substrings in Python?

Answer 5

You have a factor of 100,000x sitting in your for loop, where you apply each pattern sequentially.

You need to find a way to compose your 100K independent patterns into one pattern that can be processed efficiently. ".contains" hunts for specific text string; you can do that with a regex match, too. With a regex matcher, you can combine your individual regex patterns into a large one, precompile that, and apply that one. (See Java regex docs http://docs.oracle.com/javase/tutorial/essential/regex/)

This leaves the problem of determining which pattern got hit, if you care. If you examine lexing tools like FLEX, they provide an answer. You give them what amounts to a set of regexes, and they generate a single fast matcher which will tell you which pattern(s) hit.