Karp-Rabin String Matching, Part 2

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

• 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.