(See the next iteration.)
I have this small collection of exact string matching algorithms:
The main research question was comparing performance of all the algorithms in two different settings:
- Input which degrades performance of the naïve string matcher (
String.indexOf), where both the text and the pattern are of the formataaaa...aab, - 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.
