4
\$\begingroup\$

I have this program that compares performance of two algorithm for multiple exact string matching: Given a set of patterns and the text, find in the text all occurrences of any pattern. For example:

Text:     habababa
Patterns: aba, ha

Above, aba occurs 3 times, and ha occurs one time (matches are allowed to overlap).

The first algorithm is Aho-Corasick, and the other one is brute force.

Note, however, that this implementations considers only a, b, c, ..., x, y, z to be the alphabet. Perhaps, I will address this limitation in later posts.

AbstractMultipleExactStringMatcher.java:

package net.coderodde.patternmatching;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * This interface defines the API for multiple exact string matching algorithms.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 1, 2016)
 */
public abstract class AbstractMultipleExactStringMatcher {

    public abstract List<MatchingResult> match(String text, String... patterns);

    protected String[] filterPatterns(String[] patterns) {
        Set<String> filter = new HashSet<>(Arrays.asList(patterns));
        return filter.toArray(new String[filter.size()]);
    }

    /**
     * This class represents a match.
     */
    public static final class MatchingResult {

        /**
         * The index of the pattern being matched.
         */
        public final int patternIndex;

        /**
         * The index of the last character in a pattern indexed by
         * {@code patternIndex}.
         */
        public final int concludingIndex;

        public MatchingResult(int patternIndex, int concludingIndex) {
            this.patternIndex = patternIndex;
            this.concludingIndex = concludingIndex;
        }

        @Override
        public boolean equals(Object o) {
            if (o == null) {
                return false;
            }

            if (!getClass().equals(o.getClass())) {
                return false;
            }

            MatchingResult arg = (MatchingResult) o;

            return patternIndex == arg.patternIndex 
                    && concludingIndex == arg.concludingIndex;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 41 * hash + this.patternIndex;
            hash = 41 * hash + this.concludingIndex;
            return hash;
        }

        public String toString() {
            return "(patternIndex = " + patternIndex + 
                   ", concludingIndex = " + concludingIndex + ")";
        }
    }
}

AhoCorasickMatcher.java:

package net.coderodde.patternmatching.support;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.coderodde.patternmatching.AbstractMultipleExactStringMatcher;

/**
 * This class implements Aho-Corasick algorithm for multiple exact string
 * matching problem.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 1, 2016)
 */
public class AhoCorasickMatcher extends AbstractMultipleExactStringMatcher {

    @Override
    public List<MatchingResult> match(String text, String... patterns) {
        if (patterns.length == 0) {
            throw new IllegalArgumentException("No patterns given.");
        }

        patterns = filterPatterns(patterns);

        Automaton data = constructACAutomaton(patterns);
        TrieNode v = data.root;
        int n = text.length();
        List<MatchingResult> resultList = new ArrayList<>();

        for (int j = 0; j < n; ++j) {
            while (v.getChild(text.charAt(j)) == null) {
                v = data.fail.get(v);
            }

            v = v.getChild(text.charAt(j));

            for (Integer i : data.patterns.get(v)) {
                resultList.add(new MatchingResult(i, j));
            }
        }

        return resultList;
    }

    private static final class TrieNode {

        private final Map<Character, TrieNode> children = new HashMap<>();

        void setChild(char character, TrieNode child) {
            children.put(character, child);
        }

        TrieNode getChild(char character) {
            return children.get(character);
        }
    }

    private Automaton constructACAutomaton(String[] patterns) {
        Automaton ret = new Automaton();
        constructTrie(ret, patterns);
        computeFailureFunction(ret);
        return ret;
    }

    private void constructTrie(Automaton automaton, String[] patterns) {
        TrieNode root = new TrieNode();
        int k = patterns.length;

        for (int i = 0; i < k; ++i) {
            TrieNode v = root;
            int j = 0;
            int patternLength = patterns[i].length();

            while (j < patternLength 
                    && v.getChild(patterns[i].charAt(j)) != null) {
                v = v.getChild(patterns[i].charAt(j));
                ++j;
            }

            while (j < patternLength) {
                TrieNode u = new TrieNode();
                v.setChild(patterns[i].charAt(j), u);
                v = u;
                ++j;
            }

            List<Integer> list = new ArrayList<>();
            list.add(i);
            automaton.patterns.put(v, list);
        }

        automaton.patterns.put(root, new ArrayList<>());
        automaton.root = root;
    }

    private void computeFailureFunction(Automaton automaton) {
        TrieNode fallbackNode = new TrieNode();

        for (char c = 'a'; c <= 'z'; ++c) {
            fallbackNode.setChild(c, automaton.root);
        }

        automaton.fail.put(automaton.root, fallbackNode);
        Deque<TrieNode> queue = new ArrayDeque<>();
        queue.addLast(automaton.root);

        while (!queue.isEmpty()) {
            TrieNode u = queue.removeFirst();

            for (char c = 'a'; c <= 'z'; ++c) {
                if (u.getChild(c) == null) {
                    continue;
                }

                TrieNode v = u.getChild(c);
                TrieNode w = automaton.fail.get(u);

                while (w.getChild(c) == null) {
                    w = automaton.fail.get(w);
                }

                automaton.fail.put(v, w.getChild(c));

                List<Integer> list = 
                        automaton.patterns.get(automaton.fail.get(v));

                if (automaton.patterns.get(v) == null) {
                    automaton.patterns.put(v, list);
                } else {
                    automaton.patterns.get(v).addAll(list);
                }

                queue.addLast(v);
            }
        }

        automaton.patterns.put(automaton.root, new ArrayList<>());
    }

    private static final class Automaton {
        TrieNode root;
        Map<TrieNode, TrieNode> fail = new HashMap<>();
        Map<TrieNode, List<Integer>> patterns = new HashMap<>();
    }
}

BruteForceMatcher.java:

package net.coderodde.patternmatching.support;

import java.util.ArrayList;
import java.util.List;
import net.coderodde.patternmatching.AbstractMultipleExactStringMatcher;

/**
 * This class implements a brute force algorithm for solving multiple exact
 * string matching problem.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 2, 2016)
 */
public class BruteForceMatcher extends AbstractMultipleExactStringMatcher {

    @Override
    public List<MatchingResult> match(String text, String... patterns) {
        List<MatchingResult> ret = new ArrayList<>();

        patterns = filterPatterns(patterns);

        for (int i = 0; i < text.length(); ++i) {
            for (int j = 0; j < patterns.length; ++j) {
                MatchingResult result = tryMatch(text, patterns[j], i, j);

                if (result != null) {
                    ret.add(result);
                }
            }
        }

        return ret;
    }

    private MatchingResult tryMatch(String text, 
                                    String pattern, 
                                    int endIndex,
                                    int patternIndex) {
        int patternLength = pattern.length();

        if (patternLength > endIndex + 1) {
            return null;
        }

        int textCursor = endIndex;
        int patternCursor = patternLength - 1;

        while (patternCursor >= 0) {
            if (text.charAt(textCursor) != pattern.charAt(patternCursor)) {
                return null;
            }

            --textCursor;
            --patternCursor;
        }

        return new MatchingResult(patternIndex, endIndex);
    }
}

Utils.java:

package net.coderodde.patternmatching;

import java.util.Random;

/**
 * This class provides some miscellaneous utilities.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 2, 2016)
 */
public class Utils {

    public static String getText(int size, Random random) {
        StringBuilder sb = new StringBuilder(size);

        for (int i = 0; i < size; ++i) {
            sb.append(randomCharacter('a', 'b', random));
        }

        return sb.toString();
    }

    private static char randomCharacter(char a, char b, Random random) {
        return (char)(a + (random.nextInt(b - a)));
    }
}

PerformanceDemo.java:

import java.util.HashSet;
import net.coderodde.patternmatching.Utils;
import java.util.List;
import java.util.Random;
import java.util.Set;
import net.coderodde.patternmatching.AbstractMultipleExactStringMatcher.MatchingResult;
import net.coderodde.patternmatching.support.AhoCorasickMatcher;
import net.coderodde.patternmatching.support.BruteForceMatcher;

public class PerformanceDemo {

    public static void main(String[] args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);
        String text = Utils.getText(500_000, random);

        System.out.println("Seed = " + seed);

        String[] patterns = new String[]{
            text.substring(1000, 1220),
            text.substring(2000, 2225),
            text.substring(2005, 2225),
            text.substring(20000, 22025),
            text.substring(22000, 22025),
            text.substring(22060, 22100),
        };

        long startTime = System.nanoTime();
        List<MatchingResult> result1 = 
                new AhoCorasickMatcher().match(text, patterns);
        long endTime = System.nanoTime();

        System.out.printf("Aho-Corasick in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        startTime = System.nanoTime();
        List<MatchingResult> result2 = 
                new BruteForceMatcher().match(text, patterns);
        endTime = System.nanoTime();

        System.out.printf("Brute force in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        Set<MatchingResult> set1 = new HashSet<>(result1);
        Set<MatchingResult> set2 = new HashSet<>(result2);

        System.out.println("Same matches: " + set1.equals(set2));
    }
}

MultipleExactStringMatcherTest.java:

package net.coderodde.patternmatching;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import net.coderodde.patternmatching.AbstractMultipleExactStringMatcher.MatchingResult;
import net.coderodde.patternmatching.support.AhoCorasickMatcher;
import net.coderodde.patternmatching.support.BruteForceMatcher;
import static org.junit.Assert.assertTrue;
import org.junit.Test;

public class MultipleExactStringMatcherTest {

    private static final int ITERATIONS = 100;
    private static final int TEXT_LENGTH = 100;
    private static final int MAXIMUM_PATTERN_LENGTH = 30;
    private static final int MAXIMUM_PATTERNS = 10;

    @Test
    public void testMatchers() {

        AbstractMultipleExactStringMatcher matcher1 = new BruteForceMatcher();
        AbstractMultipleExactStringMatcher matcher2 = new AhoCorasickMatcher();

        Set<MatchingResult> set1 = new HashSet<>();
        Set<MatchingResult> set2 = new HashSet<>();

        long seed = System.nanoTime();
        Random random = new Random(seed);

        System.out.println("Seed = " + seed);

        for (int iteration = 0; iteration < ITERATIONS; ++iteration) {
            String text = Utils.getText(TEXT_LENGTH, random);

            String[] patterns = 
                    new String[1 + random.nextInt(MAXIMUM_PATTERNS)];

            for (int i = 0; i < patterns.length; ++i) {
                int startIndex = random.nextInt(text.length());
                int patternLength = 1 + random.nextInt(MAXIMUM_PATTERN_LENGTH);

                String pattern = 
                        text.substring(startIndex,
                                       Math.min(text.length(), 
                                                startIndex + patternLength));
                patterns[i] = pattern;
            }

            set1.clear();
            set2.clear();

            set1.addAll(matcher1.match(text, patterns));
            set2.addAll(matcher2.match(text, patterns));

            if (!set1.equals(set2)) {
                System.out.println("Set1: " + Arrays.toString(set1.toArray()));
                System.out.println("Set2: " + Arrays.toString(set2.toArray()));
            }

            assertTrue(set1.equals(set2));
        }
    }
}

The performance figures I get:

Seed = 44473779525966
Aho-Corasick in 316.28 milliseconds.
Brute force in 2635.01 milliseconds.
Same matches: true

What do you think? Is my API design, naming, coding conventions, performance in order? Any critique is much appreciated.

\$\endgroup\$
2
\$\begingroup\$

First of all, thanks for sharing the code.

This is the most comprehensible example of an Aho Corasick matcher I have found and I've seen a few. I also find your code pretty elegant and concise. Congratulations on that. Good work!

As always, I think there is room for improvement. Naming variables with i,j in a nested loop is a bit tough for example, as i and j almost look the same. I like to give it longer, comprehensible names like "textIndex" or "patternIndex" or "node). This also makes wrong things look wrong. As an example "patterns[textIndex]" would stand out as wrong while "patterns[x]" would not look suspicious, if it should have been "patterns[j]".

I found something that I thought looked like a bug in the Utils.randomCharacter method, where randomCharacter('a','b',random) would just emit 'a' - this is consistent with String#substring(..) methods and array indexes in general, but in this case I had expected that randomCharacter('a','b', random) would emit any character from 'a' to 'b' inclusive, like you would have it in a regular expression like "[a-b]+". This is clearly a matter of taste.

I was looking for a Aho-Corasick implementation for a private project and since I found yours to be best comprehensible, I've adapted your code for my needs: For example I needed to match byte arrays instead of Strings, so I changed it to byte[] matching (still allows matching Strings by using String#getBytes(charset))", I've added searching in a specified sub-range of the input text, I've removed some autoboxing of Integers and since there are only 256 bytes, I've made the tree node children an array of 256 nodes which removes hashing at the cost of some memory - both did not have any noticeable effect on the speed (processors are just so good), so I might reverse the latter. I changed the code from returning a List of Matches to calling a consumer with a match, this way the user can chose whether to put the matches into a Set, a List, a Map or process them in a streaming fashion (like just counting them, not keeping all results in memory). I've replaced the Pattern index with a reference to the pattern itself and I've changed the Match a bit, so one can easily see the start and end index in the text. I also added a "RunStopExeption" that is silently caught. The Performance demo I've removed and added some tests to the test suite that give hints about the performance characteristics. I'm running the code on a machine with 64GB RAM, you might want to turn down the sizes of the test sets a bit (actually I have not checked how much memory they need, but just in case you wonder).

Here's the result:

package net.coderodde.patternmatching;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.function.Consumer;

/**
 * This interface defines the API for multiple exact string matching algorithms.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 2, 2016)
 * @author Wanja Gayk (byte[] instead of String)
 * @version 2.0 (Oct 10, 2016)
 */
public abstract class AbstractMultipleExactStringMatcher {

    public static class RunStopException extends RuntimeException {
        // blank
    }

    public final void match(final byte[] text, final Consumer<MatchingResult> target, final byte[]... patterns) {
        match(text, 0, text.length, target, patterns);
    }

    public abstract void match(byte[] text, int start, int end, final Consumer<MatchingResult> target, byte[]... patterns);

    protected byte[][] uniquePatterns(final byte[][] patterns) {
        final Set<byte[]> filter = new HashSet<>(Arrays.asList(patterns));
        return filter.toArray(new byte[filter.size()][0]);
    }

    /**
     * This class represents a match.
     */
    public static final class MatchingResult {

        public final int startIndex;

        public final int endIndex;

        public final int matchLength;

        public final byte[] pattern;

        public MatchingResult(final int endIndex, final byte[] pattern) {
            startIndex = endIndex - pattern.length;
            this.endIndex = endIndex;
            matchLength = pattern.length;
            this.pattern = pattern;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + Arrays.hashCode(pattern);
            result = prime * result + startIndex;
            return result;
        }

        @Override
        public boolean equals(final Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final MatchingResult other = (MatchingResult) obj;
            if (!Arrays.equals(pattern, other.pattern)) {
                return false;
            }
            if (startIndex != other.startIndex) {
                return false;
            }
            return true;
        }

        @Override
        public String toString() {
            return "MatchingResult [startIndex=" + startIndex + ", endIndex=" + endIndex + ", pattern=" + new String(pattern) + "]";
        }

    }
}

.

package net.coderodde.patternmatching;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.function.Consumer;

/**
 * This class implements Aho-Corasick algorithm for multiple exact string matching problem.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 2, 2016)
 * @author Wanja Gayk (byte[] instead of String + micro-optimizations)
 * @version 2.0 (Oct 10, 2016)
 */
public class AhoCorasickMatcher extends AbstractMultipleExactStringMatcher {

    @Override
    public void match(final byte[] text, final int start, final int end, final Consumer<MatchingResult> target, byte[]... patterns) {
        try {
            if (patterns.length > 0) {
                patterns = uniquePatterns(patterns);
                final Automaton automaton = constructACAutomaton(patterns);
                TrieNode state = automaton.root;
                for (int textIndex = start; textIndex < end; ++textIndex) {
                    // traverse back towards root node, break if we pick up a possible match begin:
                    while (state.getChild(text[textIndex]) == null) {
                        state = automaton.fail.get(state);
                    }

                    state = state.getChild(text[textIndex]);
                    for (final int patternIndex : automaton.patterns.get(state)) {
                        target.accept(new MatchingResult(textIndex + 1, patterns[patternIndex]));
                    }
                }
            }
        } catch (final RunStopException e) {
            // deliberately left blank
        }
    }

    private static final class TrieNode {

        private final TrieNode[] children = new TrieNode[0x100];

        void setChild(final byte character, final TrieNode child) {
            children[Byte.toUnsignedInt(character)] = child;
        }

        TrieNode getChild(final byte character) {
            return children[Byte.toUnsignedInt(character)];
        }
    }

    private Automaton constructACAutomaton(final byte[]... patterns) {
        final Automaton ret = new Automaton();
        constructTrie(ret, patterns);
        computeFailureFunction(ret);
        return ret;
    }

    private void constructTrie(final Automaton automaton, final byte[]... patterns) {
        final TrieNode root = new TrieNode();
        final int k = patterns.length;

        for (int patternIndex = 0; patternIndex < k; ++patternIndex) {
            TrieNode node = root;
            int charIndex = 0;
            final int patternLength = patterns[patternIndex].length;

            while (charIndex < patternLength && node.getChild(patterns[patternIndex][charIndex]) != null) {
                node = node.getChild(patterns[patternIndex][charIndex]);
                ++charIndex;
            }

            while (charIndex < patternLength) {
                final TrieNode u = new TrieNode();
                node.setChild(patterns[patternIndex][charIndex], u);
                node = u;
                ++charIndex;
            }

            automaton.patterns.put(node, new int[] { patternIndex });
        }

        automaton.patterns.put(root, new int[0]);
        automaton.root = root;
    }

    private void computeFailureFunction(final Automaton automaton) {
        final TrieNode fallbackNode = new TrieNode();

        for (int c = 0; c < 0x100; ++c) {
            final byte b = toUnsignedByte(c);
            fallbackNode.setChild(b, automaton.root);
        }

        automaton.fail.put(automaton.root, fallbackNode);
        final Deque<TrieNode> queue = new ArrayDeque<>();
        queue.addLast(automaton.root);

        while (!queue.isEmpty()) {
            final TrieNode head = queue.removeFirst();

            for (int c = 0; c < 0x100; ++c) {
                final byte character = toUnsignedByte(c);

                if (head.getChild(character) != null) {

                    final TrieNode child = head.getChild(character);
                    TrieNode w = automaton.fail.get(head);

                    while (w.getChild(character) == null) {
                        w = automaton.fail.get(w);
                    }

                    automaton.fail.put(child, w.getChild(character));

                    final int[] failTargets = automaton.patterns.get(automaton.fail.get(child));

                    final int[] existingList = automaton.patterns.get(child);
                    if (existingList == null) {
                        automaton.patterns.put(child, failTargets);
                    } else {
                        final int[] extendedList = Arrays.copyOf(existingList, existingList.length + failTargets.length);
                        System.arraycopy(failTargets, 0, extendedList, existingList.length, failTargets.length);
                        automaton.patterns.put(child, extendedList);
                    }
                    queue.addLast(child);
                }
            }
        }

        automaton.patterns.put(automaton.root, new int[0]);
    }

    private static byte toUnsignedByte(final int value) {
        return (byte) (0xFF & value);
    }

    private static final class Automaton {
        TrieNode root;
        Map<TrieNode, TrieNode> fail = new HashMap<>();
        Map<TrieNode, int[]> patterns = new HashMap<>();
    }
}

.

package net.coderodde.patternmatching;

import java.util.function.Consumer;

/**
 * This class implements a brute force algorithm for solving multiple exact string matching problem.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 2, 2016)
 * @author Wanja Gayk (byte[] instead of String)
 * @version 2.0 (Oct 10, 2016)
 */
public class BruteForceMatcher extends AbstractMultipleExactStringMatcher {

    @Override
    public void match(final byte[] text, final int start, final int end, final Consumer<MatchingResult> target, byte[]... patterns) {
        patterns = uniquePatterns(patterns);
        try {
            for (int textIndex = start; textIndex < end; ++textIndex) {
                for (int patternIndex = 0; patternIndex < patterns.length; ++patternIndex) {
                    tryMatch(text, patterns[patternIndex], textIndex, patternIndex, target);
                }
            }
        } catch (final RunStopException e) {
            // deliberately left blank
        }
    }

    private void tryMatch(final byte[] text, final byte[] pattern, final int endIndex, final int patternIndex, final Consumer<MatchingResult> target) {
        final int patternLength = pattern.length;

        if (patternLength <= endIndex + 1) {

            int textCursor = endIndex;
            int patternCursor = patternLength - 1;

            while (patternCursor >= 0) {
                if (text[textCursor] != pattern[patternCursor]) {
                    return;
                }

                --textCursor;
                --patternCursor;
            }

            target.accept(new MatchingResult(endIndex + 1, pattern));
        }
    }
}

.

package net.coderodde.patternmatching;

import static java.util.Arrays.copyOfRange;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

import net.coderodde.patternmatching.AbstractMultipleExactStringMatcher.MatchingResult;

public class MultipleExactStringMatcherTest {

    private AbstractMultipleExactStringMatcher bruteForceMatcher;
    private AbstractMultipleExactStringMatcher ahoCorasickMatcher;
    private Set<MatchingResult> bruteForceSet;
    private Set<MatchingResult> ahoCorasickSet;

    @Before
    public void setup() {
        bruteForceMatcher = new BruteForceMatcher();
        ahoCorasickMatcher = new AhoCorasickMatcher();
        bruteForceSet = new HashSet<>();
        ahoCorasickSet = new HashSet<>();
    }

    @Test
    public void testText() {
        printTestName();

        final byte[] text = "der whiskymixer mixt whisky im whiskymixer".getBytes();
        final byte[][] patterns = { "der".getBytes(), "whisky".getBytes(), "mixer".getBytes(), "whiskymixer".getBytes() };

        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testOverlapping() {

        final byte[] text = "aaaaa".getBytes();
        final byte[][] patterns = { "a".getBytes(), "aa".getBytes(), "aaaa".getBytes() };

        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testRepetitivePattern() {
        printTestName();

        final byte[] text = "abc abc abc abcd abc abcd".getBytes();
        final byte[][] patterns = { "abc".getBytes(), "abc ".getBytes(), "abcd".getBytes(), " abc abc".getBytes() };

        matchAndPrintResult(text, patterns);

        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(0 + patterns[0].length, patterns[0])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(4 + patterns[0].length, patterns[0])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(8 + patterns[0].length, patterns[0])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(12 + patterns[0].length, patterns[0])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(17 + patterns[0].length, patterns[0])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(21 + patterns[0].length, patterns[0])));

        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(0 + patterns[1].length, patterns[1])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(4 + patterns[1].length, patterns[1])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(8 + patterns[1].length, patterns[1])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(17 + patterns[1].length, patterns[1])));

        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(12 + patterns[2].length, patterns[2])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(21 + patterns[2].length, patterns[2])));

        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(3 + patterns[3].length, patterns[3])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(7 + patterns[3].length, patterns[3])));
        Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(16 + patterns[3].length, patterns[3])));
    }

    @Test
    public void testRepetitivePattern2() {
        printTestName();

        final byte[] text = " so long, so long\n [female chorus] # So long, so long\n so long and thanks for all the fish".getBytes();
        final byte[][] patterns = { //
                " so ".getBytes(), //
                " so l".getBytes(), //
                " so lo".getBytes(), //
                " so long".getBytes(), //
                " so long,".getBytes(), //
                " so long, ".getBytes(), //
                " so long, s".getBytes(), //
                " so long, so".getBytes(), //
                " so long, so ".getBytes(), //
                " so long, so l".getBytes(), //
                " so long, so lo".getBytes(), //
                " so long, so lon".getBytes(), //
                " so long, so long".getBytes(), //
        };

        matchAndPrintResult(text, patterns);

        for (int i = 0; i < 4; ++i) {
            Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(0 + patterns[i].length, patterns[i])));
            Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(9 + patterns[i].length, patterns[i])));
            Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(45 + patterns[i].length, patterns[i])));
            Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(54 + patterns[i].length, patterns[i])));
        }
        for (int i = 5; i < patterns.length; ++i) {
            Assert.assertTrue(ahoCorasickSet.contains(new MatchingResult(0 + patterns[i].length, patterns[i])));
        }
    }

    @Test
    public void testRandom() {
        printTestName();

        final Random random = new Random(123);
        for (int t = 0; t < 200; ++t) {

            final byte[] text = Utils.getText(200, 'a', 'c', random).getBytes();
            final byte[][] patterns = new byte[10][];
            for (int p = 0; p < patterns.length; ++p) {
                final byte[] pattern = Utils.getText(5, 'a', 'c', random).getBytes();
                patterns[p] = pattern;
            }

            bruteForceSet.clear();
            ahoCorasickSet.clear();

            bruteForceMatcher.match(text, bruteForceSet::add, patterns);
            ahoCorasickMatcher.match(text, ahoCorasickSet::add, patterns);

            if (!bruteForceSet.equals(ahoCorasickSet)) {
                System.out.println(new String(text));
                System.out.println(bruteForceSet);
                System.out.println(ahoCorasickSet);
            }
            Assert.assertEquals(bruteForceSet, ahoCorasickSet);
            if (bruteForceSet.isEmpty()) {
                --t;
            }
        }
    }

    @Test
    public void testWholeByteRange() {
        printTestName();

        final byte[] text = new byte[0x100];
        for (int b = 0; b < text.length; ++b) {
            text[b] = toUnsignedByte(b);
        }
        final byte[][] patterns = new byte[0x100 / 4][];
        for (int p = 0; p < patterns.length; ++p) {
            final int start = p * 4;
            final int end = start + 4;
            final byte[] pattern = Arrays.copyOfRange(text, start, end);
            patterns[p] = pattern;
        }

        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testBigPatternSize() {
        printTestName();

        final Random random = new Random(123);
        final int textSize = 1 << 21;
        System.out.println("preparing text, size " + textSize);
        final byte[] text = Utils.getText(textSize, 'a', 'c', random).getBytes();

        final byte[][] patterns = new byte[][] { //
                text, //
                Arrays.copyOfRange(text, 0, text.length / 2), //
                Arrays.copyOfRange(text, text.length / 2, text.length), //
                Arrays.copyOfRange(text, 0, text.length / 8), //
        };
        for (final byte[] pattern : patterns) {
            System.out.println("pattern size: " + pattern.length);
        }

        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testSmallPatternInBigText() {
        printTestName();

        final Random random = new Random(123);
        final int textSize = 1 << 30;
        System.out.println("preparing text, size " + textSize);
        final byte[] text = Utils.getText(textSize, 'a', 'c', random).getBytes();

        final byte[][] patterns = new byte[][] { //
                Arrays.copyOfRange(text, 0, 4), //
                Arrays.copyOfRange(text, 100, 116), //
                Arrays.copyOfRange(text, 1000, 1008), //
        };
        for (final byte[] pattern : patterns) {
            System.out.println("pattern size: " + pattern.length);
        }

        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testHugeNumberOfSmallPatterns() {
        printTestName();

        final Random random = new Random(123);
        final int textSize = 1 << 19;
        System.out.println("preparing text, size " + textSize);
        final byte[] text = Utils.getText(textSize, 'a', 'c', random).getBytes();

        final int chunkSize = 16;
        final byte[][] patterns = new byte[text.length / chunkSize / 10][];
        System.out.println("preparing patterns, amount:" + patterns.length);
        for (int p = 0; p < patterns.length; ++p) {
            final int start = p * chunkSize;
            final int end = start + chunkSize;
            final byte[] pattern = Arrays.copyOfRange(text, start, end);
            patterns[p] = pattern;
        }

        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testWorstCaseTextAndSmallSinglePattern() {
        printTestName();

        final Random random = new Random(123);
        final int textSize = 1 << 22;
        System.out.println("preparing text, size " + textSize);
        final byte[] text = Utils.getText(textSize, 'a', 'a', random).getBytes();

        final byte[][] patterns = new byte[][] { Arrays.copyOfRange(text, 0, 10), };
        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testWorstCaseTextAndBigSinglePattern() {
        printTestName();

        final Random random = new Random(123);
        final int textSize = 1 << 20;
        System.out.println("preparing text, size " + textSize);
        final byte[] text = Utils.getText(textSize, 'a', 'a', random).getBytes();

        final byte[][] patterns = new byte[][] { Arrays.copyOfRange(text, 0, 1000), };
        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testWorstCaseTextAndSomeSmallPatterns() {
        printTestName();

        final Random random = new Random(123);
        final int textSize = 1 << 18;
        System.out.println("preparing text, size " + textSize);
        final byte[] text = Utils.getText(textSize, 'a', 'a', random).getBytes();

        final byte[][] patterns = new byte[100][];
        System.out.println("preparing patterns, amount:" + patterns.length);
        for (int p = 0; p < patterns.length; ++p) {
            final byte[] pattern = Arrays.copyOfRange(text, 0, p + 1);
            patterns[p] = pattern;
        }
        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testWorstCaseTextAndSomeBigPatterns() {
        printTestName();

        final Random random = new Random(123);
        final int textSize = 1 << 14;
        System.out.println("preparing text, size " + textSize);
        final byte[] text = Utils.getText(textSize, 'a', 'a', random).getBytes();

        final byte[][] patterns = new byte[100][];
        System.out.println("preparing patterns, amount:" + patterns.length);
        for (int p = 0; p < patterns.length; ++p) {
            final byte[] pattern = Arrays.copyOfRange(text, 0, (p + 1) * 100);
            patterns[p] = pattern;
        }
        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testPerfDemoOrginal() {
        printTestName();

        final long seed = System.nanoTime();
        final Random random = new Random(seed);
        final byte[] text = Utils.getText(500_000, 'a', 'a', random).getBytes();

        System.out.println("Seed = " + seed);

        final byte[][] patterns = new byte[][] { copyOfRange(text, 1000, 1220), copyOfRange(text, 2000, 2225), copyOfRange(text, 2005, 2225),
                copyOfRange(text, 20000, 22025), copyOfRange(text, 22000, 22025), copyOfRange(text, 22060, 22100), };

        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testPerfDemoOrginalAsIntended() {
        printTestName();

        final long seed = System.nanoTime();
        final Random random = new Random(seed);
        final byte[] text = Utils.getText(500_000, 'a', 'b', random).getBytes();

        System.out.println("Seed = " + seed);

        final byte[][] patterns = new byte[][] { copyOfRange(text, 1000, 1220), copyOfRange(text, 2000, 2225), copyOfRange(text, 2005, 2225),
                copyOfRange(text, 20000, 22025), copyOfRange(text, 22000, 22025), copyOfRange(text, 22060, 22100), };

        matchAndPrintResult(text, patterns);
    }

    @Test
    public void testPerfDemoOrginalWiderNumberOfcharacters() {
        printTestName();

        final long seed = System.nanoTime();
        final Random random = new Random(seed);
        final byte[] text = Utils.getText(500_000, 'a', 'z', random).getBytes();

        System.out.println("Seed = " + seed);

        final byte[][] patterns = new byte[][] { copyOfRange(text, 1000, 1220), copyOfRange(text, 2000, 2225), copyOfRange(text, 2005, 2225),
                copyOfRange(text, 20000, 22025), copyOfRange(text, 22000, 22025), copyOfRange(text, 22060, 22100), };

        matchAndPrintResult(text, patterns);
    }

    private void matchAndPrintResult(final byte[] text, final byte[][] patterns) {
        System.out.println("brute force matching");
        final long startB = System.currentTimeMillis();
        bruteForceMatcher.match(text, bruteForceSet::add, patterns);
        final long endB = System.currentTimeMillis();
        System.out.println(endB - startB + "ms");

        System.out.println("aho corasick matching");
        final long startC = System.currentTimeMillis();
        ahoCorasickMatcher.match(text, ahoCorasickSet::add, patterns);
        final long endC = System.currentTimeMillis();
        System.out.println(endC - startC + "ms");

        if (!bruteForceSet.equals(ahoCorasickSet)) {
            System.out.println(new String(text));

            final Comparator<MatchingResult> matchingResultComparator = Comparator.<MatchingResult> comparingInt(m -> m.startIndex)
                    .thenComparingInt(m -> m.endIndex);
            final Set<MatchingResult> bruteForceSetSorted = new TreeSet<>(matchingResultComparator);
            final Set<MatchingResult> ahoCorasickSetSorted = new TreeSet<>(matchingResultComparator);
            bruteForceSetSorted.addAll(bruteForceSet);
            ahoCorasickSetSorted.addAll(ahoCorasickSet);

            System.out.println(bruteForceSetSorted);
            System.out.println(ahoCorasickSetSorted);
        }
        Assert.assertEquals(bruteForceSet, ahoCorasickSet);
    }

    void printTestName() {
        System.out.println("----");
        System.out.println(Thread.currentThread().getStackTrace()[2].getMethodName());
    }

    private static byte toUnsignedByte(final int value) {
        return (byte) (0xFF & value);
    }

}

.

package net.coderodde.patternmatching;

import java.util.Random;

/**
 * This class provides some miscellaneous utilities.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jan 2, 2016)
 * @author Wanja Gayk (bugfix)
 * @version 2.0 (Oct 10, 2016)
 */
public class Utils {

    public static String getText(final int size, final char a, final char b, final Random random) {
        final StringBuilder sb = new StringBuilder(size);

        for (int i = 0; i < size; ++i) {
            sb.append(randomCharacter(a, b, random));
        }

        return sb.toString();
    }

    private static char randomCharacter(final char a, final char b, final Random random) {
        return (char) (a + (random.nextInt((b + 1) - a)));
    }
}
\$\endgroup\$
4
\$\begingroup\$

I tested your code on a set of 100k patterns and an alphabet of 2.5k symbols and automaton construction took ages.

After a closer look, I found that the failure function construction part keeps iterating over the whole alphabet, where instead it could have just used the children of the current trie node -- which are typically like an order of magnitude fewer in number than the size of the alphabet :) (to me it was two orders of magnitude)

This optimization sped up the automaton construction by the corresponding orders of magnitude.

\$\endgroup\$
  • \$\begingroup\$ @coderodde, thank you for posting the question -- and the code. To me it was an answer itself, actually :) Apologies for not having the thanks in the answer text -- the editor decided to remove them for some reason. \$\endgroup\$ – admech Feb 28 '18 at 15:50
  • \$\begingroup\$ Would you be so kind and share the code change to the automaton construction? \$\endgroup\$ – Brixomatic Oct 10 '18 at 7:49
  • \$\begingroup\$ that's been done on a machine that's under an nda i fear -- and also quite a while ago so that I have neither access, nor memories of that :( but given the above description I hope you already re-constructed it... \$\endgroup\$ – admech Oct 29 '18 at 21:51
1
\$\begingroup\$

Is my API design, naming, coding conventions, performance in order? - not intending to delve into performance or to start with constructTrie()/computeFailureFunction().

API

Don't mix use and reuse/construction. Prefer interfaces over abstract class. Have a

public interface Matcher {

    interface Match {
        String getPattern();
        int getConcludingIndex();
    }
// alternatives: NavigableSet<Match>, Stream<Match>
    java.util.Iterator<Match> match(String text);

    static class Utils {
    /** @return new array of distinct {@code pattern}s specified
     * <br/>indexes bound to differ */
    // XXX: what about ""? Throw if unique.size() != patterns.length?
        public static String[] filterPatterns(String[] patterns) {
            java.util.Set<String> unique = new java.util.HashSet<>(
                java.util.Arrays.asList(patterns));
            return unique.toArray(new String[unique.size()]);
        }
    }
}

(or put utilities in net.coderodde.patternmatching.support.)
I don't expect throwing in

public interface MatcherFactory {
    Matcher create(Object ...params);
}

, a registry, implementation/class selection by properties, … to be worth the trouble.

/** This class implements the Aho-Corasick algorithm
 *   for the multiple exact string matching problem.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.x */
public class AhoCorasickMatcher
    implements Matcher //, MatcherFactory
{
    private Automaton data;
    public AhoCorasickMatcher(String ...literals) {
        if (0 == literals.length)
            throw new IllegalArgumentException(
                "No patterns given.");
        data = constructACAutomaton(
            Matcher.Utils.filterPatterns(literals));
    }

    @Override
    public Iterator<Match> match(String text) {
        …
    }
}
\$\endgroup\$
  • \$\begingroup\$ With Java 8, filterPatterns() would better be a member of Matcher. \$\endgroup\$ – greybeard Jan 14 '16 at 0:19
1
\$\begingroup\$

Your equals method of MatchingResult ought to quickly return true for the case o == this.

\$\endgroup\$
0
\$\begingroup\$

Could remove some null conditionals and returns, instead having a predicate method in MatchingResult which denotes the empty state.

Equality test below could opt not to return, instead dying naturally of an NPE and proceeding no further.

public boolean equals(Object o) {
    if (o == null) {
        return false;
}

Removed, thanks @greybeard for API link, info.

Less certain about the following. Use of reflection here:

if (!getClass().equals(o.getClass())) {
    return false;
}

Maybe appropriate to use instanceof instead. Could also serve to guard the cast:

MatchingResult arg = (MatchingResult) o;
\$\endgroup\$
  • \$\begingroup\$ Equality test below could opt […] - from the API description: For any non-null reference value x, x.equals(null) should return false. (You can have a predicate equalTo(Object other).)` \$\endgroup\$ – greybeard Jan 6 '16 at 5:32
  • \$\begingroup\$ Thanks @greybeard for api reference; will have to allow the null to live on. \$\endgroup\$ – kph0x1 Jan 6 '16 at 12:43
  • \$\begingroup\$ instanceof in equals-methods violates the constract of the equals method, namely that a.equals(b) == b.equals(a). If "b extends a" that part of the contract would be violated. \$\endgroup\$ – Brixomatic Mar 11 '17 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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