5
\$\begingroup\$

Part 1 is here. I wrote a Java implementation of the Karp-Rabin semi-numerical string matching algorithm. I incorporated the suggestions of @fge and @maaartinus from the other question into my new code: the match method now returns a boolean so you can write if (KarpRabin.match(pattern, text)), and I changed the underlying algorithm to use arithmetic mod \$2^{32}\$ with an arbitrary base, so that overflow isn't a problem and any character supported by Java's Strings (which are UTF-16) can be understood.

I also added another method, allMatches, which finds all positions in the string which match the given pattern and returns them in a list. It wasn't obvious to me how to split up allMatches and match so I could reuse the code, so most of it is repeated; that's one major issue I'd like suggestions for.

The current implementation of allMatches is not consistently typed because it returns Collections.EMPTY_LIST (with no generic type parameter) when no matches are found, but a List<Integer> when matches are found. I did this because I like using it as in this code:

List<Integer> result = KarpRabin.allMatches(pattern, text);
if (result == Collections.EMPTY_LIST) {
    // do whatever you do when nothing matches
}

better than as in this code:

List<Integer> result = KarpRabin.allMatches(pattern, text);
if (result.size() == 0) {
     // do whatever you do when nothing matches
}

But this breaks generic type consistency and generates a compiler warning, so I'm open to other ways of doing it.

Here's the code:

public class KarpRabin {
    private static final int BASE = 103;  // Arbitrary base for hash.

    /**
       Finds first match, returns true, false if no match found.
    */
    public static boolean match(String pattern, String text) {
        if (pattern.length() > text.length()) {
            return false;
        }
        int out, phash, thash;
        out = 1;

        for (int expt = pattern.length(); expt > 1; --expt) {
            out *= BASE;
        }

        // Calculate fingerprint of pattern and of first
        // pattern.length-length group in text.
        phash = thash = 0;
        for (int i = 0; i < pattern.length(); ++i) {
            phash = phash*BASE + pattern.charAt(i);
            thash = thash*BASE + text.charAt(i);
        }

        for (int s = 0; s < text.length() - pattern.length(); ++s) {
            if (phash == thash) {
                if (pattern.equals(text.substring(s, s+pattern.length()))) {
                    return true;
                }
            }
            assert s < text.length() &&
                s + pattern.length() < text.length() :
            "s is " + s + " and s+pattern.length() is " +
                (s + pattern.length());
            thash = BASE*(thash - out*text.charAt(s)) +
                text.charAt(s+pattern.length());
        }

        // See note [4].
        if (phash == thash) {
            if (pattern.equals(text.substring(text.length() - pattern.length(),
                                              text.length())))
                return true;
        }
        return false;
    }

    /**
       Finds all matches of pattern in text, returns a list of
       matching positions.

       Currently, the code is mostly repeated from match.
    */
    public static List<Integer> allMatches(String pattern, String text) {
        if (pattern.length() > text.length()) {
            return Collections.EMPTY_LIST;
        }
        int out, phash, thash;
        out = 1;

        for (int expt = pattern.length(); expt > 1; --expt) {
            out *= BASE;
        }

        // Calculate fingerprint of pattern and of first
        // pattern.length-length group in text.
        phash = thash = 0;
        for (int i = 0; i < pattern.length(); ++i) {
            phash = phash*BASE + pattern.charAt(i);
            thash = thash*BASE + text.charAt(i);
        }

        List<Integer> matches = new ArrayList<>();
        for (int s = 0; s < text.length() - pattern.length(); ++s) {
            if (phash == thash) {
                if (pattern.equals(text.substring(s, s+pattern.length()))) {
                    matches.add(s);
                }
            }
            assert s < text.length() &&
                s + pattern.length() < text.length() :
            "s is " + s + " and s+pattern.length() is " +
                (s + pattern.length());
            thash = BASE*(thash - out*text.charAt(s)) +
                text.charAt(s+pattern.length());
        }

        // See note [4].
        if (phash == thash) {
            if (pattern.equals(text.substring(text.length() - pattern.length(),
                                              text.length())))
                matches.add(text.length() - pattern.length());
        }
        if (matches.size() == 0) {
            return Collections.EMPTY_LIST;
        }
        return matches;
    }
}

Suggestions for improving readability, robustness, performance, and type safety, as well as for refactoring these methods to get rid of the repeated code, are all welcome and very much appreciated.

\$\endgroup\$
4
\$\begingroup\$

Your concerns about:

List<Integer> result = KarpRabin.allMatches(pattern, text);
if (result == Collections.EMPTY_LIST) {
    // do whatever you do when nothing matches
}

are real. That's a problem. On the other hand, there's the standard isEmpty() helper method:

if (result.isEmpty()) {
    // do whatever you do when nothing matches
}

In this code loop here:

    for (int expt = pattern.length(); expt > 1; --expt) {
        out *= BASE;
    }

it is not obvious why you loop 1-less time than you have characters in the code. Additionally, I am uncertain why the backward-direction loop is useful. Should be:

    for (int i = 1; i < pattern.length(); i++) {
        out *= BASE;
    }

As I say, though, the loop above does 1-less than the number of chars in the pattern, should it be indexed from 0? If not, it should be commented.

As for the duplication of code, you should make the class have a private constructor, and you should create an instance of the class each time you call one of the static 'search' methods.

When you create the instance, you create the various state information (the phash, the thash, etc.). Then, have a next() method that just gets the location of the next match. Your two static methods would then look like:

public static boolean match(String pattern, String text) {
    KarpRabin kr = new KarpRobin(pattern, text);
    return kr.next() >= 0;
}

public static List<Integer> allMatches(String pattern, String text) {
    KarpRabin kr = new KarpRobin(pattern, text);
    List<Integer> matches = new ArrayList<Integer>();
    int pos = 0;
    while ((pos = kr.next()) >= 0) {
        matches.add(pos);
    }
    return matches;
}

Then, what you need to do is make the actual KarpRobin class more 'stateful', it knows where it is in the search, and it finds the next match each time. The code should be fairly easy to copy/paste from your current code.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot, don't know how I missed isEmpty(). Regarding that backwards loop, it does need to be one less than the length of the pattern, as explained in CLRS. The base has to be raised to n-1, not n. I made it backwards because one usually represents a base-b number as a1*b^n-1 + a2*b^n-2 + ... + an*b^0, with the exponents going from n-1 down to 0, but I see what you mean, making it backwards makes it harder to read and adds nothing. Love your suggestion for reducing duplication; it feels like a Python generator. \$\endgroup\$ – tsleyson Nov 17 '14 at 21:26
1
\$\begingroup\$
result == Collections.EMPTY_LIST

This is wrong. It works in your case as you're returning exactly Collections.EMPTY_LIST, but it's too strange and unexpected.

result.equals(Collections.EMPTY_LIST)

wound be better, but it's longer than

result.size() == 0

and much less readable than the already proposed best solution

result.isEmpty()

not consistently typed

This is too bad. You could use

Collections.emptyList()

which returns exactly the same auto-magically casted to proper type.


It wasn't obvious to me how to split up allMatches and match

Without looking at the code: The second can be trivially expressed using the first one. Obviously, you'd lose some efficiency, but how? Mostly by computing additional matches after the result is clear.

The solution is pretty standard: Define allMatches(limit) computing up to limit matches. Make it private and use it by both methods.


I'd rename match to contains, see String.contains. The leads immediately to indexOf, which can also be trivially implemented via allMatches(limit). The implementation of contains should then be based on indexOf.


There's already a nice CR by rolfl, so I stop here.

\$\endgroup\$
  • \$\begingroup\$ Good tip on Collections.empty(). I think rolfl's result.isEmpty() works best here, but I'll keep Collections.empty() in mind for the future. \$\endgroup\$ – tsleyson Nov 18 '14 at 23:15
  • \$\begingroup\$ @tsleyson I'm afraid, I was confusing you. What I've meant is returning Collections.emptyList() instead of Collections.EMPTY_LIST (and there's also an emptySet()). The latter is pre-Java 5 and should be avoided. The former just does the unchecked cast, so you get exactly what you want (no runtime overhead at all). Fixed. \$\endgroup\$ – maaartinus Nov 18 '14 at 23:25
  • 1
    \$\begingroup\$ Ah, makes sense, thanks. I'm surprised they haven't marked Collections.EMPTY_LIST as deprecated, like the Vector and HashTable classes. \$\endgroup\$ – tsleyson Nov 18 '14 at 23:27
0
\$\begingroup\$
  • Your code is not OO at all. Having a bunch of static methods is closer to C or Fortran than an OO language. (@rolfl did not mention OO directly, but talked of "statefulness".)

  • Not only it's not OO, but you are using very long methods. You should break things down in "logical units". The code is easier to read and maintain that way. My rule of thumb is that a method should not be more than 10 lines.

  • Watch out for variable names. In Java verbose names are preferred. phash and thash are a bit short, and out is outright confusing. Usually out would have something to do with output.

Here is my implementation in Java 8, since you were curious about that:

public static class PositionAndHash {
    private final int base;
    private final int basePowerPatternSize;
    private final int position;
    private final int hash;

    public PositionAndHash(int base, int patternSize) {
        this.base = base;
        this.basePowerPatternSize = Collections.nCopies(patternSize, base).stream().reduce(1, (i1, i2) -> i1 * i2);
        this.position = -1;
        this.hash = 0;
    }

    private PositionAndHash(int base, int basePowerSize, int position, int hash) {
        this.base = base;
        this.basePowerPatternSize = basePowerSize;
        this.position = position;
        this.hash = hash;
    }

    public int getPosition() {
        return position;
    }

    public int getHash() {
        return hash;
    }

    public PositionAndHash increment(int newChar, Optional<Integer> removedChar) {
        int newHash = hash * base + newChar - removedChar.orElse(0) * basePowerPatternSize;
        return new PositionAndHash(base, basePowerPatternSize, position + 1, newHash);
    }

    public static int computeSingleHash(String string, int hashBase) {
        return computeRollingHash(string, string.length(), hashBase)
                .skip(string.length() - 1)
                .mapToInt(PositionAndHash::getHash)
                .findFirst().getAsInt();
    }

    public static Stream<PositionAndHash> computeRollingHash(String searchableString, int patternSize, int hashBase) {
        // Kind of messed up to use an AtomicReference here, but Java's Stream does not have fold operations.
        AtomicReference<PositionAndHash> positionAndHashRef = new AtomicReference<>(new PositionAndHash(hashBase, patternSize));
        return searchableString.chars()
                .mapToObj(newChar -> {
                    PositionAndHash prevPositionAndHash = positionAndHashRef.get();
                    int removedCharIndex = prevPositionAndHash.getPosition() - patternSize + 1;
                    Optional<Integer> removedChar = (removedCharIndex >= 0) 
                            ? Optional.of((int) searchableString.charAt(removedCharIndex))
                            : Optional.empty();
                    PositionAndHash newHash = prevPositionAndHash.increment(newChar, removedChar);
                    positionAndHashRef.set(newHash);
                    return newHash;
                });
    }

    @Override
    public String toString() {
        return "PositionAndHash{" + "position=" + position + ", hash=" + hash + '}';
    }

}

public static void main(String[] args) {
    int hashBase = 103;
    String searchableString = "aaasfaaaaiofjwenvaiefowjfaaalsdfl";
    String pattern = "aaa";
    int subStringSize = pattern.length();
    int patternHash = PositionAndHash.computeSingleHash(pattern, hashBase);
    System.out.println("pattern hash: " + patternHash);

    Stream<PositionAndHash> rollingHash = PositionAndHash.computeRollingHash(searchableString, subStringSize, hashBase);
    // rollingHash.forEach(System.out::println);

    IntStream hashMatchPositions = rollingHash.skip(subStringSize - 1)
            .filter(posAndHash -> posAndHash.getHash() == patternHash)
            .mapToInt(PositionAndHash::getPosition)
            .map(pos -> pos - subStringSize + 1);
     //hashMatchPositions.forEach(System.out::println);

    IntStream trueMatchPositions = hashMatchPositions
            .filter(pos -> searchableString.substring(pos, pos + subStringSize).equals(pattern));
    trueMatchPositions.forEach(System.out::println);

    // Or to only print the first match instead of all matches:
    // (Note that Stream is "intelligent" ("lazily evaluated") and 
    //  will not process the whole Stream when only the first element is fetched (findFirst()).)

    // trueMatchPositions.findFirst().ifPresent(System.out::println);
}

I actually don't like my implementation that much. Most of all is that the class PositionAndHash does too many things.

\$\endgroup\$
  • \$\begingroup\$ The big problem is increment, which is O(n), thus completely blowing the performance. I guess, you could implement PositionAndHash simply by referring to the original string instead of using any queues. \$\endgroup\$ – maaartinus Nov 18 '14 at 3:49
  • \$\begingroup\$ What's n? I'm implementing Karp-Rabin too, so I'm only using the new char and the old char to update the hash. Except that I do make a copy of the bounded queue (O(queueSize), the size of the pattern) to keep everything immutable. It's not an issue if the pattern is much shorter than the text. \$\endgroup\$ – toto2 Nov 18 '14 at 4:23
  • \$\begingroup\$ n == queueSize and that's the problem. If the pattern is much shorter than the text, then you need no Karp-Rabin. The complexity of your algorithm is O(text.length() * pattern.length()) just like without Karp-Rabin. Getting rid of the queue solves it, preserving immutability. \$\endgroup\$ – maaartinus Nov 18 '14 at 4:51
  • \$\begingroup\$ Thanks. I fixed it. I also thought of two alternative fixes: 1) I could have zipped the char stream from the text with another char stream from the same text, but delayed by the pattern size. However Java's Stream does not support zipping. 2) I could have used a queue that adds/removes in O(1) and passed it around the updated PositionAndHashs, but that would have destroyed immutability. \$\endgroup\$ – toto2 Nov 18 '14 at 14:24

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.