Pattern matching in Thousands of files

Question

I've a regex pattern of words like welcome1|welcome2|changeme... which I need to search for in thousands of files (varies between 100 to 8000) ranging from 1KB to 24 MB each, in size.

I would like to know if there's a faster way of pattern matching than doing what I have been trying.

Environment:

1. jdk 1.8
2. Windows 10
3. Unix4j Library

Here's what I tried till now

try (Stream<Path> stream = Files.walk(Paths.get(FILES_DIRECTORY))
                                    .filter(FilePredicates.isFileAndNotDirectory())) {

        List<String> obviousStringsList = Strings_PASSWORDS.stream()
                                                .map(s -> ".*" + s + ".*").collect(Collectors.toList()); //because Unix4j apparently needs this

        Pattern pattern = Pattern.compile(String.join("|", obviousStringsList));

        GrepOptions options = new GrepOptions.Default(GrepOption.count,
                                                        GrepOption.ignoreCase,
                                                        GrepOption.lineNumber,
                                                        GrepOption.matchingFiles);
        Instant startTime = Instant.now();

        final List<Path> filesWithObviousStringss = stream
                .filter(path -> !Unix4j.grep(options, pattern, path.toFile()).toStringResult().isEmpty())
                .collect(Collectors.toList());

        System.out.println("Time taken = " + Duration.between(startTime, Instant.now()).getSeconds() + " seconds");
}

I get Time taken = 60 seconds which makes me think I'm doing something really wrong.

I've tried different ways with the stream and on an average every method takes about a minute to process my current folder of 6660 files.

Grep on mysys2/mingw64 takes about 15 seconds and exec('grep...') in node.js takes about 12 seconds consistently.

I chose Unix4j because it provides java native grep and clean code.

Is there a way to produce better results in Java, that I'm sadly missing?

Answer 1

I don’t know what “Unix4j” provides that isn’t already in the JDK, as the following code does everything with built-in features:

try(Stream<Path> stream = Files.walk(Paths.get(FILES_DIRECTORY))
                               .filter(Files::isRegularFile)) {
        Pattern pattern = Pattern.compile(String.join("|", Strings_PASSWORDS));
        long startTime = System.nanoTime();
        final List<Path> filesWithObviousStringss = stream
                .filter(path -> {
                    try(Scanner s = new Scanner(path)) {
                        return s.findWithinHorizon(pattern, 0) != null;
                    } catch(IOException ex) {
                        throw new UncheckedIOException(ex);
                    }
                })
                .collect(Collectors.toList());
        System.out.println("Time taken = "
            + TimeUnit.NANOSECONDS.toSeconds(System.nanoTime()-startTime) + " seconds");
}

One important property of this solution is that it doesn’t read the whole file, but stops at the first encountered match. Also, it doesn’t deal with line boundaries, which is suitable for the words you’re looking for, as they never contain line breaks anyway.

After analyzing the findWithinHorizon operation, I consider that line by line processing may be better for larger files, so, you may try

try(Stream<Path> stream = Files.walk(Paths.get(FILES_DIRECTORY))
                               .filter(Files::isRegularFile)) {
        Pattern pattern = Pattern.compile(String.join("|", Strings_PASSWORDS));
        long startTime = System.nanoTime();
        final List<Path> filesWithObviousStringss = stream
                .filter(path -> {
                    try(Stream<String> s = Files.lines(path)) {
                        return s.anyMatch(pattern.asPredicate());
                    } catch(IOException ex) {
                        throw new UncheckedIOException(ex);
                    }
                })
                .collect(Collectors.toList());
        System.out.println("Time taken = "
            + TimeUnit.NANOSECONDS.toSeconds(System.nanoTime()-startTime) + " seconds");
}

instead.

You may also try to turn the stream to parallel mode, e.g.

try(Stream<Path> stream = Files.walk(Paths.get(FILES_DIRECTORY))
                               .filter(Files::isRegularFile)) {
        Pattern pattern = Pattern.compile(String.join("|", Strings_PASSWORDS));
        long startTime = System.nanoTime();
        final List<Path> filesWithObviousStringss = stream
                .parallel()
                .filter(path -> {
                    try(Stream<String> s = Files.lines(path)) {
                        return s.anyMatch(pattern.asPredicate());
                    } catch(IOException ex) {
                        throw new UncheckedIOException(ex);
                    }
                })
                .collect(Collectors.toList());
        System.out.println("Time taken = "
            + TimeUnit.NANOSECONDS.toSeconds(System.nanoTime()-startTime) + " seconds");
}

It’s hard to predict whether this has a benefit, as in most cases, the I/O dominates such an operation.

Answer 2

The main reason why native tools can process such text files much faster, is their assumption of one particular charset, especially when it has an ASCII based 8 Bit encoding, whereas Java performs a byte to character conversion whose abstraction is capable of supporting arbitrary charsets.

When we similarly assume a single charset with the properties named above, we can use lowlevel tools which may increase the performance dramatically.

For such an operation, we define the following helper methods:

private static char[] getTable(Charset cs) {
    if(cs.newEncoder().maxBytesPerChar() != 1f)
        throw new UnsupportedOperationException("Not an 8 bit charset");
    byte[] raw = new byte[256];
    IntStream.range(0, 256).forEach(i -> raw[i] = (byte)i);
    char[] table = new char[256];
    cs.newDecoder().onUnmappableCharacter(CodingErrorAction.REPLACE)
      .decode(ByteBuffer.wrap(raw), CharBuffer.wrap(table), true);
    for(int i = 0; i < 128; i++)
        if(table[i] != i) throw new UnsupportedOperationException("Not ASCII based");
    return table;
}

and

private static CharSequence mapAsciiBasedText(Path p, char[] table) throws IOException {
    try(FileChannel fch = FileChannel.open(p, StandardOpenOption.READ)) {
        long actualSize = fch.size();
        int size = (int)actualSize;
        if(size != actualSize) throw new UnsupportedOperationException("file too large");
        MappedByteBuffer mbb = fch.map(FileChannel.MapMode.READ_ONLY, 0, actualSize);
        final class MappedCharSequence implements CharSequence {
            final int start, size;
            MappedCharSequence(int start, int size) {
                this.start = start;
                this.size = size;
            }
            public int length() {
                return size;
            }
            public char charAt(int index) {
                if(index < 0 || index >= size) throw new IndexOutOfBoundsException();
                byte b = mbb.get(start + index);
                return b<0? table[b+256]: (char)b;
            }
            public CharSequence subSequence(int start, int end) {
                int newSize = end - start;
                if(start<0 || end < start || end-start > size)
                    throw new IndexOutOfBoundsException();
                return new MappedCharSequence(start + this.start, newSize);
            }
            public String toString() {
                return new StringBuilder(size).append(this).toString();
            }
        }
        return new MappedCharSequence(0, size);
    }
}

This allows to map a file into the virtual memory and project it directly to a CharSequence, without copy operations, assuming that the mapping can be done with a simple table and, for ASCII based charsets, the majority of the characters do not even need a table lookup, as their numerical value is identical to the Unicode codepoint.

With these methods, you may implement the operation as

// You need this only once per JVM.
// Note that running inside IDEs like Netbeans may change the default encoding
char[] table = getTable(Charset.defaultCharset());

try(Stream<Path> stream = Files.walk(Paths.get(FILES_DIRECTORY))
                               .filter(Files::isRegularFile)) {
    Pattern pattern = Pattern.compile(String.join("|", Strings_PASSWORDS));
    long startTime = System.nanoTime();
    final List<Path> filesWithObviousStringss = stream//.parallel()
            .filter(path -> {
                try {
                    return pattern.matcher(mapAsciiBasedText(path, table)).find();
                } catch(IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            })
            .collect(Collectors.toList());
    System.out.println("Time taken = "
        + TimeUnit.NANOSECONDS.toSeconds(System.nanoTime()-startTime) + " seconds");
}

This runs much faster than the normal text conversion, but still supports parallel execution.

Besides requiring an ASCII based single byte encoding, there’s the restriction that this code doesn’t support files larger than 2 GiB. While it is possible to extend the solution to support larger files, I wouldn’t add this complication unless really needed.

Answer 3

I never used Unix4j yet, but Java provides nice file APIs as well nowadays. Also, Unix4j#grep seems to return all the found matches (as you're using .toStringResult().isEmpty()), while you seem to just need to know whether at least one match got found (which means that you should be able to break once one match is found). Maybe this library provides another method that could better suit your needs, e.g. something like #contains? Without the use of Unix4j, Stream#anyMatch could be a good candidate here. Here is a vanilla Java solution if you want to compare with yours:

private boolean lineContainsObviousStrings(String line) {
  return Strings_PASSWORDS // <-- weird naming BTW
    .stream()
    .anyMatch(line::contains);
}

private boolean fileContainsObviousStrings(Path path) {
  try (Stream<String> stream = Files.lines(path)) {
    return stream.anyMatch(this::lineContainsObviousStrings);
  }
}

public List<Path> findFilesContainingObviousStrings() {
  Instant startTime = Instant.now();
  try (Stream<Path> stream = Files.walk(Paths.get(FILES_DIRECTORY))) {
    return stream
      .filter(FilePredicates.isFileAndNotDirectory())
      .filter(this::fileContainsObviousStrings)
      .collect(Collectors.toList());
  } finally {
    Instant endTime = Instant.now();
    System.out.println("Time taken = " + Duration.between(startTime, endTime).getSeconds() + " seconds");
  }
}

Answer 4

Please try this out too (if it is possible), I am curious how it performs on your files.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Filescan {

    public static void main(String[] args) throws IOException {
        Filescan sc = new Filescan();
        sc.findWords("src/main/resources/files", new String[]{"author", "book"}, true);
    }

    // kind of Tuple/Map.Entry
    static class Pair<K,V>{
        final K key;
        final V value;

        Pair(K key, V value){
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return key + " " + value;
        }
    }

    public void findWords(String directory, String[] words, boolean ignorecase) throws IOException{

        final String[] searchWords = ignorecase ? toLower(words) : words;

        try (Stream<Path> stream =     Files.walk(Paths.get(directory)).filter(Files::isRegularFile)) {
            long startTime = System.nanoTime();
            List<Pair<Path,Map<String, List<Integer>>>> result = stream
                    // you can test it with parallel execution, maybe it is faster
                    .parallel()
                    // searching
                    .map(path -> findWordsInFile(path, searchWords, ignorecase))
                    // filtering out empty optionals
                    .filter(Optional::isPresent)
                    // unwrap optionals
                    .map(Optional::get).collect(Collectors.toList());
            System.out.println("Time taken = " +     TimeUnit.NANOSECONDS.toSeconds(System.nanoTime()
                            - startTime) + " seconds");
            System.out.println("result:");
            result.forEach(System.out::println);
        }
    }

    private String[] toLower(String[] words) {
        String[] ret = new String[words.length];
        for (int i = 0; i < words.length; i++) {
            ret[i] = words[i].toLowerCase();
        }
        return ret;
    }

    private static Optional<Pair<Path,Map<String, List<Integer>>>>     findWordsInFile(Path path, String[] words, boolean ignorecase) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path.toFile())))) {
            String line = br.readLine();
            line = ignorecase & line != null ? line.toLowerCase() : line;
            Map<String, List<Integer>> map = new HashMap<>();
            int linecount = 0;
            while(line != null){
                for (String word : words) {
                    if(line.contains(word)){
                        if(!map.containsKey(word)){
                            map.put(word, new ArrayList<Integer>());
                        }
                        map.get(word).add(linecount);
                    }
                }
                line = br.readLine();
                line = ignorecase & line != null ? line.toLowerCase() : line;
                linecount++;
            }
            if(map.isEmpty()){
                // returning empty optional when nothing in the map
                return Optional.empty();
            }else{
                // returning a path-map pair with the words and the rows where each word has been found
                return Optional.of(new Pair<Path,Map<String, List<Integer>>>(path, map));
            }
        } catch (IOException ex) {
            throw new UncheckedIOException(ex);
        }
    }    
}