6
\$\begingroup\$

I wrote an implementation of the Karp-Rabin string matching algorithm in Java 7, based on the discussion in Section 32.2 of Introduction to Algorithms (CLRS). Clearly, I need more experience with numeric programming, because I spent two days wrestling with overflow issues and floating point error, but I believe it works now.

Of course, anything goes, but I'm especially looking for feedback on the following points:

  • Are there any cases left where it would fail?
  • How can I improve the design?
  • How can I make the code more readable?
  • How can I make the code more robust?
  • Did I miss any glaring performance traps?

Here's the class constructor and the match method, which do the bulk of the work.

public class KarpRabin {
    final long q, b;
    public static final int NONE = -1;
    Map<Character, Integer> digitMap;

    public KarpRabin(String alphabet) {
        digitMap = new HashMap<>();
        for (int i = 0; i < alphabet.length(); ++i) {
            digitMap.put(alphabet.charAt(i), i);
        }
        q = 26900927; // A prime such that b*q can reasonably fit in
                      // a word for most values of b.
        b = alphabet.length();
        if (b >= q) {
            throw new IllegalArgumentException("b cannot be larger than " + q);
        }
    }

    public int match(String pattern, String text) {
        // Returns location of first match of pattern in text.
        if (pattern.length() > text.length()) {
            throw new IllegalArgumentException("Pattern longer than text.");
        }
        int[] T = digitValue(text);
        int[] P = digitValue(pattern);
        long h, p, t;
        p = t = 0;
        h = expt(b, pattern.length()-1).mod(BigInteger.valueOf(q)).longValue(); // See note [7].

        // Calculate fingerprint of pattern and of first
        // pattern.length-length group in text.
        for (int i = 0; i < pattern.length(); ++i) {
            p = (b*p + P[i]) % q;
            t = (b*t + T[i]) % q;
        }

        for (int s = 0; s < text.length() - pattern.length(); ++s) {
            if (p == t) {
                if (pattern.equals(text.substring(s, s+pattern.length()))) {
                    return s;
                }
            }
            assert s < T.length && s + pattern.length() < T.length :
                "s is " + s + " and s+pattern.length() is " +
                (s + pattern.length());
            t = (b * (t - T[s]*h) + T[s + pattern.length()]) % q;
            // Handle Java's modulus behavior; see note[2].
            t += q;
            t %= q;
            assert t >= 0 : "t is below 0, has value " + t;
       }
       // See note [4].
       if (p == t) {
           if (pattern.equals(text.substring(
               text.length() - pattern.length(), text.length())))
               return text.length() - pattern.length();
       }
       return NONE;
}

Here's a gist with the rest of the code, including the private helper methods.

Although the current code is Java 7, I plan to switch to Java 8 in the near future, so suggestions for where I could make good use of Java 8 features is also welcome.

\$\endgroup\$
6
  • \$\begingroup\$ Side question: Java 7 or Java 8? \$\endgroup\$
    – fge
    Nov 13 '14 at 1:04
  • \$\begingroup\$ @fge Sorry, it's Java 7. I'll edit to add. I haven't made the move to Java 8 yet. \$\endgroup\$
    – tsleyson
    Nov 13 '14 at 1:07
  • 1
    \$\begingroup\$ OK, I don't fully understand the algorithm, but first things first, imho it'd be better if you returned a boolean for the matchin method; also, well, this is often overlooked but it doesn't seem that this method will handle Unicode code points outside the BMP \$\endgroup\$
    – fge
    Nov 13 '14 at 1:17
  • \$\begingroup\$ @fge So you'd recommend just returning true for a match, and false for no match, instead of the index where the match starts? \$\endgroup\$
    – tsleyson
    Nov 13 '14 at 1:26
  • \$\begingroup\$ At a first glance, yes; however this all depends on what you intend to do with the return value. If you mean to only use this method to return a "yes/no" value then a boolean is better than testing the return value each time \$\endgroup\$
    – fge
    Nov 13 '14 at 1:28
4
\$\begingroup\$

Clearly, I need more experience with numeric programming, because I spent two days wrestling with overflow issues and floating point error

I'd suggest to just avoid it all. Use mod \$2^{32}\$ arithmetic, ignore overflow, forget floating point and forget BigInteger.

I'm afraid, the problem is not the code, but the algorithm. I can see that the Wikipedia really describes all the strange things concerning modular arithmetic, but I'm pretty sure that you took it too literally.

For a rolling hash, all you need is something like

h = BASE_MULTIPLIER * h + inChar + OUT_MULTIPLIER * outChar;

where inChar is the incoming character, BASE_MULTIPLIER is any number co-prime to \$2^{32}\$ (i.e., odd) and OUT_MULTIPLIER is its \$n\$-th power mod \$2^{32}\$, where \$n\$ is the length of the sliding window.


If you insist on using a prime instead of \$2^{32}\$, then you can do it all without BigInteger as long as the prime fits in an int (use long and compute modulus after each operation).

If you're still unsatisfied with the hash function, then there are simple ways to improve it (just ask).


throw new IllegalArgumentException("Pattern longer than text.");

What's illegal here? It's just not there, cf. "x".contains("abc").

throw new IllegalArgumentException("b cannot be larger than " + q);

It can... IIUIC, it's just hashing, so there's no reason to whine because of collisions as long as they're rare.


How can I make the code more robust?

Don't require to specify the alphabet and similar things. It's not necessary.

Did I miss any glaring performance traps?

Both % and BigInteger are performance killers.

Because of the way I implemented the algorithm, supporting general Unicode strings in UCS-2 or UTF-16 would require doing base-65,536 arithmetic.

If you implemented it my way, there'd be no problem.

There's no hard limit on the size, but larger alphabets mean more BigInteger math.

Do no BigInteger at all.


Although the current code is Java 7, I plan to switch to Java 8 in the near future

Just don't. If you see something where Java 8 could obviously help a lot, go for it. Otherwise, I wouldn't care. I'm not saying that Java 8 is no big improvement, it's just that sticking with Java 7 or 6 makes your program more usable.

\$\endgroup\$
5
  • \$\begingroup\$ Thanks for your feedback, it's very helpful. Regarding Java 8, I just meant I planned to upgrade my JDK, not that I was going to gratuitously throw in a bunch of streams and lambdas. \$\endgroup\$
    – tsleyson
    Nov 13 '14 at 19:01
  • \$\begingroup\$ @tsleyson You're welcome. I haven't updated yet to Java 8 as I plan to do something for Android, where it may take a few more years. Actually, I'm using Java 6, but I'm confident it works with 7 and 8, too. \$\endgroup\$
    – maaartinus
    Nov 13 '14 at 20:44
  • \$\begingroup\$ Got this going and added some unit tests for Unicode strings, everything works great. Thanks again. I was on Java 6 until my programming languages prof forced us to upgrade so we could use his language built on top of Java 7...there was no Ubuntu package for Java 7 at the time, so it was pretty painful. \$\endgroup\$
    – tsleyson
    Nov 15 '14 at 18:47
  • \$\begingroup\$ @tsleyson Nice! Feel free to post your new code (in a new question linking to this one). \$\endgroup\$
    – maaartinus
    Nov 15 '14 at 19:49
  • \$\begingroup\$ Done, the new question is here. \$\endgroup\$
    – tsleyson
    Nov 17 '14 at 8:41

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.