14
\$\begingroup\$

(See the next iteration.)

I have this small collection of exact string matching algorithms:

  1. Knuth-Morris-Pratt algorithm,
  2. Finite automaton matcher,
  3. Rabin-Karp algorithm,
  4. Z algorithm.

The main research question was comparing performance of all the algorithms in two different settings:

  1. Input which degrades performance of the naïve string matcher (String.indexOf), where both the text and the pattern are of the format aaaa...aab,
  2. Both text and the pattern are random.

The results are:

[WORST CASE OF String.indexOf]
String.indexOf in 6976 milliseconds.
Knuth-Morris-Pratt matcher in 56 milliseconds.
Finite automaton matcher in 98 milliseconds.
Rabin-Karp matcher in 74 milliseconds.
Z matcher in 89 milliseconds.

[RANDOM STRINGS]
[SEED: 1446895693075]
String.indexOf in 238 milliseconds.
Knuth-Morris-Pratt matcher in 303 milliseconds.
Finite automaton matcher in 371 milliseconds.
Rabin-Karp matcher in 909 milliseconds.
Z matcher in 705 milliseconds.

net.coderodde.string.matching.StringMatchers.java:

package net.coderodde.string.matching;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * This class contains different string matching algorithms as static methods.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Nov 7, 2015)
 */
public final class StringMatchers {

    public static final int NOT_FOUND_INDEX = -1;

    public static final class KnuthMorrisPrattMatcher {

        /**
         * This static method implements the 
         * <a href="https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm">
         * Knuth-Morris-Pratt</a> pattern matching algorithm that runs in time
         * {@code O(n + m)}, where {@code n} is the length of the text to search
         * and {@code m} is the length of the pattern to search.
         * 
         * @param text       the text to search in.
         * @param pattern    the pattern to search for.
         * @param startIndex the character index from which to start matching.
         * @return the smallest index no less than {@code startIndex} of the
         *         position where the pattern occurs if there is a match, or
         *         {@code NOT_FOUND_INDEX} if there is no match.
         */
        public static int match(String text, String pattern, int startIndex) {
            if (pattern.isEmpty()) {
                return 0;
            }

            int n = text.length();
            int m = pattern.length();

            if (m > n) {
                return -1;
            }

            int[] prefixFunction = computePrefixFunction(pattern);
            int q = 0;

            for (int i = Math.max(0, startIndex); i < n; ++i) {
                while (q > 0 && pattern.charAt(q) != text.charAt(i)) {
                    q = prefixFunction[q - 1];
                }

                if (pattern.charAt(q) == text.charAt(i)) {
                    ++q;
                }

                if (q == m) {
                    return i - m + 1;
                }
            }

            return NOT_FOUND_INDEX;
        }

        public static int match(String text, String pattern) {
            return match(text, pattern, 0);
        }

        private static int[] computePrefixFunction(String pattern) {
            int m = pattern.length();
            int[] prefixFunction = new int[m];
            int k = 0;

            for (int q = 1; q < m; ++q) {
                while (k > 0 && pattern.charAt(k) != pattern.charAt(q)) {
                    k = prefixFunction[k - 1];
                }

                if (pattern.charAt(k) == pattern.charAt(q)) {
                    ++k;
                }

                prefixFunction[q] = k;
            }

            return prefixFunction;
        }
    }

    public static final class AutomatonMatcher {

        /**
         * This static method implements the algorithm for exact string matching
         * that constructs a finite automaton, and uses it in order to detect
         * a pattern. The running time is {@code n + sm}, where {@code n} is the
         * length of the text to search, {@code m} is the length of the pattern,
         * and {@code s} is the amount of distinct characters in the pattern.
         * 
         * @param text       the text to search in.
         * @param pattern    the pattern to search for.
         * @param startIndex the character index from which to start matching.
         * @return the smallest index no less than {@code startIndex} of the
         *         position where the pattern occurs if there is a match, or
         *         {@code NOT_FOUND_INDEX} if there is no match.
         */
        public static int match(String text, String pattern, int startIndex) {
            if (pattern.isEmpty()) {
                return 0;
            }

            int n = text.length();
            Integer m = pattern.length();

            if (m > n) {
                return NOT_FOUND_INDEX;
            }

            TransitionFunction transitionFunction = 
                    computeTransitionFunction(pattern);

            Integer j = 0;

            for (int i = Math.max(0, startIndex); i < n; ++i) {
                if (j == null) {
                    j = 0;
                }

                j = transitionFunction.getState(j, text.charAt(i));

                if (m.equals(j)) {
                    return i - m + 1;
                }
            }

            return NOT_FOUND_INDEX;
        }

        public static int match(String text, String pattern) {
            return match(text, pattern, 0);
        }

        private static TransitionFunction 
        computeTransitionFunction(String pattern) {
            return new TransitionFunction(pattern);
        }

        private static final class TransitionFunction {

            private final Map<Character, Integer>[] function;

            TransitionFunction(String pattern) {
                int m = pattern.length();
                this.function = new HashMap[m + 1];

                Set<Character> filter = new HashSet(m);

                for (Character c : pattern.toCharArray()) {
                    filter.add(c);
                }

                int numberOfCharacters = filter.size();
                Character[] characterArray = new Character[numberOfCharacters];
                filter.toArray(characterArray);

                for (int i = 0; i < function.length; ++i) {
                    function[i] = new HashMap<>(numberOfCharacters);
                }

                for (int i = 0; i < numberOfCharacters; ++i) {
                    function[0].put(characterArray[i], 0);
                }

                function[0].put(pattern.charAt(0), 1);

                for (int i = 1, lps = 0; i <= m; ++i) {
                    for (int x = 0; x < numberOfCharacters; ++x) {
                        function[i].put(characterArray[x], 
                                        function[lps].get(characterArray[x]));
                    }


                    if (i < m) {
                        function[i].put(pattern.charAt(i), i + 1);
                        lps = function[lps].get(pattern.charAt(i));
                    }
                }
            }

            Integer getState(int currentState, char character) {
                return function[currentState].get(character);
            }

            @Override
            public String toString() {
                StringBuilder sb = new StringBuilder();
                Set<Character> alphabet = new TreeSet<>(function[0].keySet());
                Character[] array = new Character[alphabet.size()];
                alphabet.toArray(array);

                for (Map<Character, Integer> map : function) {
                    for (Character c : array) {
                        sb.append(map.get(c)).append(' ');
                    }

                    sb.append('\n');
                }

                return sb.toString();
            }
        }
    }

    public static final class RabinKarpMatcher {
        /**
         * This static method implements the Rabin-Karp algorithm for exact 
         * string matching: The worst case running time is {@code nm}, where 
         * {@code n} is the length of the text to search and {@code m} is the 
         * length of the pattern.
         * 
         * @param text       the text to search in.
         * @param pattern    the pattern to search for.
         * @param startIndex the character index from which to start matching.
         * @return the smallest index no less than {@code startIndex} of the
         *         position where the pattern occurs if there is a match, or
         *         {@code NOT_FOUND_INDEX} if there is no match.
         */
        public static int match(String text, String pattern, int startIndex) {
            int m = pattern.length();

            if (m == 0) {
                return 0;
            }

            int n = text.length();
            startIndex = Math.max(0, startIndex);

            if (m + startIndex > n) {
                return NOT_FOUND_INDEX;
            }

            Set<Character> alphabet = new HashSet<>();

            for (char c : pattern.toCharArray()) {
                alphabet.add(c);
            }

            long d = alphabet.size();
            long q = 2;
            long h = intpow(d, m - 1) % q;

            long p = 0;
            long t = 0;

            // Beginning of preprocessing.
            for (int i = 0; i < m; ++i) {
                p = (d * p + (long)(pattern.charAt(i))) % q;
                t = (d * t + (long)(text.charAt(i + startIndex))) % q;
            }
            // End of preprocessing.

            // Beginning of matching.
            for (int s = startIndex; s <= n - m;  ++s) {
                if (p == t) {
                    if (hasMatch(pattern, text, s)) {
                        return s;
                    }
                }

                if (s < n - m) {
                    long save_t = t;
                    t = (d * (save_t - (long)(text.charAt(s)) * h) + 
                         (long)(text.charAt(s + m))) % q;

                    if (t < 0) {
                        t = (t + q);
                    }
                }
            }

            return NOT_FOUND_INDEX;
        }

        private static boolean hasMatch(String pattern, 
                                        String text, 
                                        int shift) {
            int m = pattern.length();

            for (int i = 0; i < m; ++i) {
                if (pattern.charAt(i) != text.charAt(i + shift)) {
                    return false;
                }
            }

            return true;
        }

        private static long intpow(long base, int exponent) {
            long ret = 1;

            for (int i = 0; i < exponent; ++i) {
                ret *= base;
            }

            return ret;
        }

        public static int match(String text, String pattern) {
            return match(text, pattern, 0);
        }
    }

    public static final class ZMatcher {

        /**
         * This static method implements the Z-algorithm for exact string 
         * matching. The running time is {@code n + m}, where {@code n} is the
         * length of the text to search and {@code m} is the length of the 
         * pattern. The space complexity is linear.
         * 
         * @param text       the text to search in.
         * @param pattern    the pattern to search for.
         * @param startIndex the character index from which to start matching.
         * @return the smallest index no less than {@code startIndex} of the
         *         position where the pattern occurs if there is a match, or
         *         {@code NOT_FOUND_INDEX} if there is no match.
         */
        public static int match(String text, String pattern, int startIndex) {
            if (pattern.isEmpty()) {
                return 0;
            }

            int n = text.length();
            int m = pattern.length();

            if (m > n) {
                return -1;
            }

            startIndex = Math.max(0, startIndex);

            if (startIndex != 0) {
                text = text.substring(startIndex);
            }

            StringBuilder sb = new StringBuilder(text.length() + 
                                                 pattern.length() + 1 -
                                                 startIndex);

            sb.append(pattern).append(Character.valueOf('\0')).append(text);
            // Do not create a new string from the StringBuilder, but rather
            // use the builder to access the data.
            int[] zArray = computeZArray(sb);

            for (int i = Math.max(0, startIndex); i < zArray.length; ++i) {
                if (zArray[i] == m) {
                    return i - m - 1 + startIndex;
                }
            }

            return NOT_FOUND_INDEX;
        }

        public static int match(String text, String pattern) {
            return match(text, pattern, 0);
        }

        private static int[] computeZArray(StringBuilder sb) {
            int n = sb.length();
            int[] ret = new int[n];

            int l = 0;
            int r = 0;

            for (int i = 1; i < n; ++i) {
                if (i > r) {
                    l = i;
                    r = i;

                    while (r < n && sb.charAt(r - l) == sb.charAt(r)) {
                        ++r;
                    }

                    ret[i] = r - l;
                    --r;
                } else {
                    int k = i - l;

                    if (ret[k] < r - i + 1) {
                        ret[i] = ret[k];
                    } else {
                        l = i;

                        while (r < n && sb.charAt(r - l) == sb.charAt(r)) {
                            ++r;
                        }

                        ret[i] = r - l;
                        --r;
                    }
                }
            }

            return ret;
        }
    }
}

PerformanceDemo.java:

import java.util.Random;
import java.util.function.BiFunction;
import net.coderodde.string.matching.StringMatchers;

public class PerformanceDemo {

    public static void main(final String... args) {
        int N = 3_000_000;
        int M = 3000;
        StringBuilder sb = new StringBuilder(N);

        for (int i = 0; i < N; ++i) {
            sb.append('a');
        }

        String text = sb.append('b').toString();

        sb.delete(0, sb.length());

        for (int i = 0; i < M; ++i) {
            sb.append('a');
        }

        String pattern = sb.append('b').toString();

        System.out.println("[WORST CASE OF String.indexOf]");
        demo(text, pattern);

        long seed = System.currentTimeMillis();
        Random random = new Random(seed);
        text = getRandomText(random);
        pattern = getRandomPattern(random);

        System.out.println();
        System.out.println("[RANDOM STRINGS]");
        System.out.println("[SEED: " + seed + "]");

        demo(text, pattern);
    }

    private static String getRandomText(Random random) {
        int n = 10_000_000;
        StringBuilder sb = new StringBuilder(n);

        for (int i = 0; i < n; ++i) {
            sb.append('a' + random.nextInt(26));
        }

        return sb.toString();
    }

    private static String getRandomPattern(Random random) {
        int n = 1_000;
        StringBuilder sb = new StringBuilder(n);

        for (int i = 0; i < n; ++i) {
            sb.append('a' + random.nextInt(26));
        }

        return sb.toString();
    }

    private static void profile(BiFunction<String, String, Integer> matcher,
            String text,
            String pattern,
            int expectedIndex,
            String matcherName) {
        long startTime = System.currentTimeMillis();
        int index = matcher.apply(text, pattern);
        long endTime = System.currentTimeMillis();

        if (index != expectedIndex) {
            throw new IllegalStateException(
                    matcher.getClass() + " failed. Returned: " + index
                    + ", expected: " + expectedIndex);
        }

        System.out.println(matcherName + " in "
                + (endTime - startTime) + " milliseconds.");
    }

    private static void demo(String text, String pattern) {
        long startTime = System.currentTimeMillis();
        int expectedIndex = text.indexOf(pattern);
        long endTime = System.currentTimeMillis();

        System.out.println("String.indexOf in " + (endTime - startTime)
                + " milliseconds.");

        profile(StringMatchers.KnuthMorrisPrattMatcher::match,
                text,
                pattern,
                expectedIndex,
                "Knuth-Morris-Pratt matcher");

        profile(StringMatchers.AutomatonMatcher::match,
                text,
                pattern,
                expectedIndex,
                "Finite automaton matcher");

        profile(StringMatchers.RabinKarpMatcher::match,
                text,
                pattern,
                expectedIndex,
                "Rabin-Karp matcher");

        profile(StringMatchers.ZMatcher::match,
                text,
                pattern,
                expectedIndex,
                "Z matcher");
    }
}

StringMatchersTest.java:

package net.coderodde.string.matching;

import org.junit.Test;
import static org.junit.Assert.*;
import static net.coderodde.string.matching.StringMatchers.*;

public class StringMatchersTest {

    @Test
    public void testKnuthMorrisPrattMatcher() {
        assertEquals(-1, KnuthMorrisPrattMatcher.match("aaa", "aaaa"));
        assertEquals(0,  KnuthMorrisPrattMatcher.match("aaaa", "aaaa"));
        assertEquals(-1, KnuthMorrisPrattMatcher.match("aaaa", "bb"));
        assertEquals(1,  KnuthMorrisPrattMatcher.match("abbb", "bb"));
        assertEquals(2,  KnuthMorrisPrattMatcher.match("abcc", "cc"));

        assertEquals(5, KnuthMorrisPrattMatcher.match("aaaaaaab", "aab"));
        assertEquals(4, KnuthMorrisPrattMatcher.match("ababababaca", 
                                                      "ababaca"));

        assertTrue("".indexOf("") == KnuthMorrisPrattMatcher.match("", ""));
        assertTrue("".indexOf("a") == KnuthMorrisPrattMatcher.match("", "a"));
        assertTrue("a".indexOf("") == KnuthMorrisPrattMatcher.match("a", ""));
        assertTrue("hello".indexOf("ello", -2) == 
                KnuthMorrisPrattMatcher.match("hello", "ello", -2));

        assertEquals(-1, KnuthMorrisPrattMatcher.match("aabaab", "aab", 5));
        assertEquals(-1, KnuthMorrisPrattMatcher.match("aabaab", "aab", 4));
        assertEquals(3, KnuthMorrisPrattMatcher.match("aabaab", "aab", 3));
        assertEquals(3, KnuthMorrisPrattMatcher.match("aabaab", "aab", 2));
        assertEquals(3, KnuthMorrisPrattMatcher.match("aabaab", "aab", 1));
        assertEquals(0, KnuthMorrisPrattMatcher.match("aabaab", "aab", 0));
        assertEquals(0, KnuthMorrisPrattMatcher.match("aabaab", "aab", -1));
        assertEquals(0, KnuthMorrisPrattMatcher.match("aabaab", "aab", -2));
    }

    @Test
    public void testAutomatonMatcher() {
        assertEquals(0, AutomatonMatcher.match("acacaga", "acacaga"));
        assertEquals(-1, AutomatonMatcher.match("aaa", "aaaa"));
        assertEquals(0,  AutomatonMatcher.match("aaaa", "aaaa"));
        assertEquals(-1, AutomatonMatcher.match("aaaa", "bb"));
        assertEquals(1,  AutomatonMatcher.match("abbb", "bb"));
        assertEquals(2,  AutomatonMatcher.match("abcc", "cc"));

        assertEquals(5, AutomatonMatcher.match("aaaaaaab", "aab"));
        assertEquals(4, AutomatonMatcher.match("ababababaca", "ababaca"));

        assertTrue("".indexOf("") == AutomatonMatcher.match("", ""));
        assertTrue("".indexOf("a") == AutomatonMatcher.match("", "a"));
        assertTrue("a".indexOf("") == AutomatonMatcher.match("a", ""));
        assertTrue("hello".indexOf("ello", -2) == 
                AutomatonMatcher.match("hello", "ello", -2));

        assertEquals(-1, AutomatonMatcher.match("aabaab", "aab", 5));
        assertEquals(-1, AutomatonMatcher.match("aabaab", "aab", 4));
        assertEquals(3, AutomatonMatcher.match("aabaab", "aab", 3));
        assertEquals(3, AutomatonMatcher.match("aabaab", "aab", 2));
        assertEquals(3, AutomatonMatcher.match("aabaab", "aab", 1));
        assertEquals(0, AutomatonMatcher.match("aabaab", "aab", 0));
        assertEquals(0, AutomatonMatcher.match("aabaab", "aab", -1));
        assertEquals(0, AutomatonMatcher.match("aabaab", "aab", -2));
    }

    @Test
    public void testRabinKarpMatcher() {
        assertEquals(0, RabinKarpMatcher.match("acacaga", "acacaga"));
        assertEquals(-1, RabinKarpMatcher.match("aaa", "aaaa"));
        assertEquals(0,  RabinKarpMatcher.match("aaaa", "aaaa"));
        assertEquals(-1, RabinKarpMatcher.match("aaaa", "bb"));
        assertEquals(1,  RabinKarpMatcher.match("abbb", "bb"));
        assertEquals(2,  RabinKarpMatcher.match("abcc", "cc"));

        assertEquals(5, RabinKarpMatcher.match("aaaaaaab", "aab"));
        assertEquals(4, RabinKarpMatcher.match("ababababaca", "ababaca"));

        assertTrue("".indexOf("") == RabinKarpMatcher.match("", ""));
        assertTrue("".indexOf("a") == RabinKarpMatcher.match("", "a"));
        assertTrue("a".indexOf("") == RabinKarpMatcher.match("a", ""));
        assertTrue("hello".indexOf("ello", -2) == 
                RabinKarpMatcher.match("hello", "ello", -2));

        assertEquals(-1, RabinKarpMatcher.match("aabaab", "aab", 5));
        assertEquals(-1, RabinKarpMatcher.match("aabaab", "aab", 4));
        assertEquals(3, RabinKarpMatcher.match("aabaab", "aab", 3));
        assertEquals(3, RabinKarpMatcher.match("aabaab", "aab", 2));
        assertEquals(3, RabinKarpMatcher.match("aabaab", "aab", 1));
        assertEquals(0, RabinKarpMatcher.match("aabaab", "aab", 0));
        assertEquals(0, RabinKarpMatcher.match("aabaab", "aab", -1));
        assertEquals(0, RabinKarpMatcher.match("aabaab", "aab", -2));
        assertEquals(6, RabinKarpMatcher.match("aaaaaaaab", "aab"));
    }

    @Test
    public void testZMatcher() {
        assertEquals(0, ZMatcher.match("acacaga", "acacaga"));
        assertEquals(-1, ZMatcher.match("aaa", "aaaa"));
        assertEquals(0,  ZMatcher.match("aaaa", "aaaa"));
        assertEquals(-1, ZMatcher.match("aaaa", "bb"));
        assertEquals(1,  ZMatcher.match("abbb", "bb"));
        assertEquals(2,  ZMatcher.match("abcc", "cc"));

        assertEquals(5, ZMatcher.match("aaaaaaab", "aab"));
        assertEquals(4, ZMatcher.match("ababababaca", "ababaca"));

        assertTrue("".indexOf("") == ZMatcher.match("", ""));
        assertTrue("".indexOf("a") == ZMatcher.match("", "a"));
        assertTrue("a".indexOf("") == ZMatcher.match("a", ""));
        assertTrue("hello".indexOf("ello", -2) == 
                ZMatcher.match("hello", "ello", -2));

        assertEquals(-1, ZMatcher.match("aabaab", "aab", 5));
        assertEquals(-1, ZMatcher.match("aabaab", "aab", 4));
        assertEquals(3, ZMatcher.match("aabaab", "aab", 3));
        assertEquals(3, ZMatcher.match("aabaab", "aab", 2));
        assertEquals(3, ZMatcher.match("aabaab", "aab", 1));
        assertEquals(0, ZMatcher.match("aabaab", "aab", 0));
        assertEquals(0, ZMatcher.match("aabaab", "aab", -1));
        assertEquals(0, ZMatcher.match("aabaab", "aab", -2));
        assertEquals(6, ZMatcher.match("aaaaaaaab", "aab"));
    }
}

As of this writing, all matchers pass the same set of tests, and they agree in the demonstration, so I guess there is not much to add to the correctness. However, the code is not quite cohesive, so I would like to hear about that.

\$\endgroup\$
12
\$\begingroup\$

The Matcher implementations

You group all these matchers in a StringMatchers class. Other than grouping the matchers together, this class adds no real benefit. All macher's match() methods are static. Yet all have the same match() methods. This just aches to be refactored to all matchers implementing the same interface.

public interface StringMatcher {

    int NOT_FOUND_INDEX = -1;

    int match(String text, String pattern, int startIndex);

    default int match(String text, String pattern) {
        return match(text, pattern, 0);
    }
}

The StringMatchers class can still house the 4 implementations, but rather than exposing the implementation classes, we'll make the classes private and add factory methods to the StringMatchers class.

public final class StringMatchers {

    public static StringMatcher knuthMorrisPrattMatcher() {
        return new KnuthMorrisPrattMatcher();
    }

    public static StringMatcher automatonMatcher() {
        return new AutomatonMatcher();
    }

    public static StringMatcher rabinKarpMatcher() {
        return new RabinKarpMatcher();
    }

    public static StringMatcher zMatcher() {
        return new ZMatcher();
    }

    private static final class KnuthMorrisPrattMatcher implements StringMatcher { ... }

    private static final class AutomatonMatcher implements StringMatcher { ... }

    private static final class RabinKarpMatcher implements StringMatcher { ... }

    private static final class ZMatcher implements StringMatcher { ...}
}

Ultimately you could even refactor this to an enum.

In all algorithms you use single letter variable names. As a rule this is not done. For well documented algorithms it could be permissable if the published algorithm defines these variables. I've checked the KnuthMorrisPrattMatcher, and found that the referenced material uses different variable names. So either correct that, or use meaningful variable names. Otherwise, in 6 months time, even you will be scratching your head when reviewing this code.

The StringMatchers test

All StringMatcher implementations should pass the same tests. Since they now have a common interface, we can test against the interface. We could make an abstract test class and 4 subclasses to test each implementation.

public abstract class StringMatchersTest {

    abstract StringMatcher getMatcherToTest();

    @Test
    public void testMatcher() {
        assertEquals(0, getMatcherToTest().match("acacaga", "acacaga"));
        assertEquals(-1, getMatcherToTest().match("aaa", "aaaa"));
        assertEquals(0,  getMatcherToTest().match("aaaa", "aaaa"));
        assertEquals(-1, getMatcherToTest().match("aaaa", "bb"));
        assertEquals(1,  getMatcherToTest().match("abbb", "bb"));
        assertEquals(2,  getMatcherToTest().match("abcc", "cc"));

        assertEquals(5, getMatcherToTest().match("aaaaaaab", "aab"));
        assertEquals(4, getMatcherToTest().match("ababababaca", "ababaca"));

        assertTrue("".indexOf("") == getMatcherToTest().match("", ""));
        assertTrue("".indexOf("a") == getMatcherToTest().match("", "a"));
        assertTrue("a".indexOf("") == getMatcherToTest().match("a", ""));
        assertTrue("hello".indexOf("ello", -2) ==  getMatcherToTest().match("hello", "ello", -2));

        assertEquals(-1, getMatcherToTest().match("aabaab", "aab", 5));
        assertEquals(-1, getMatcherToTest().match("aabaab", "aab", 4));
        assertEquals(3, getMatcherToTest().match("aabaab", "aab", 3));
        assertEquals(3, getMatcherToTest().match("aabaab", "aab", 2));
        assertEquals(3, getMatcherToTest().match("aabaab", "aab", 1));
        assertEquals(0, getMatcherToTest().match("aabaab", "aab", 0));
        assertEquals(0, getMatcherToTest().match("aabaab", "aab", -1));
        assertEquals(0, getMatcherToTest().match("aabaab", "aab", -2));
    }

}

public class KnuthMorrisPrattMatcherTest extends StringMatchersTest {
    @Override
    StringMatcher getMatcherToTest() {
        return StringMatchers.knuthMorrisPrattMatcher();
    }
}

Or (even better) we can use the Parameterized Junit runner :

@RunWith(Parameterized.class)
public class StringMatchersTest {

    @Parameterized.Parameters
    public static List<Object[]> getParameters() {
        return asList(
                new Object[]{ StringMatchers.knuthMorrisPrattMatcher() },
                new Object[]{ StringMatchers.automatonMatcher() },
                new Object[]{ StringMatchers.rabinKarpMatcher() },
                new Object[]{ StringMatchers.zMatcher() }
        );
    }

    private final StringMatcher matcher;

    public StringMatchersTest(StringMatcher matcher) {
        this.matcher = matcher;
    }

    @Test
    public void testMatcher() { ... }
}

Either way, you'll want to make a separate test method for each assertion. That way it's immediately clear which specific test case fails.

PerformanceDemo

You measure elapsed time using System.currentTimeMillis(). Use System.nanoTime instead.

Here as well, you can eliminate some repeated code by exploiting the fact that all implementations now implement a common interface. The profile() method can now accept StringMatcher as a parameter, rather than a BiFunction.

getRandomText() and getRandomPattern() are the same methods, once you make the desired length a parameter.

\$\endgroup\$
  • \$\begingroup\$ He, I can do that ;-) \$\endgroup\$ – GhostCat Nov 20 '18 at 7:29
6
\$\begingroup\$

Variable sized tests

Currently, your program uses a text of size 10,000,000 and randomized patterns of size 1,000. I would have liked to see variations in these sizes, perhaps controlled by command line arguments.

Boyer Moore

I would have liked to see your program include Boyer Moore, which I consider to be superior to the other algorithms. Just to see what would happen, I pasted in the java version of Boyer Moore from wikipedia into your program, and here are the results:

[WORST CASE OF String.indexOf]
String.indexOf in 4576 milliseconds.
Knuth-Morris-Pratt matcher in 32 milliseconds.
Boyer Moore in 31 milliseconds.
Finite automaton matcher in 47 milliseconds.
Rabin-Karp matcher in 62 milliseconds.
Z matcher in 47 milliseconds.

[RANDOM STRINGS]
[SEED: 1446921427388] String.indexOf in 133 milliseconds.
Knuth-Morris-Pratt matcher in 203 milliseconds.
Boyer Moore in 46 milliseconds.
Finite automaton matcher in 312 milliseconds.
Rabin-Karp matcher in 614 milliseconds.
Z matcher in 361 milliseconds.

\$\endgroup\$
  • \$\begingroup\$ Boyer Moore implemented and on its way whenever it's (and if) time for a follow up. \$\endgroup\$ – coderodde Nov 7 '15 at 18:59

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.