Efficient Text Searching in Java: Finding the Right String in Any Language

These combining characters need special processing during a comparison. Since \u0301 is only an accent, its collation element has a secondary component but no primary or tertiary component. In a comparison that does not involve accents, we must ignore this element entirely. If we did not, we might end up comparing an accent in one string to a base letter in another string, which would give invalid results. For example, when doing an accent-insensitive comparison "a\u0301b" and "ab", we want to skip the "\u0301" and go on to the next character; otherwise we'd compare "\u0301" and "b".

This logic is relatively straightforward, but it does make the code a bit more complicated. The boolean variables getTarget and getPattern are used to decide whether to fetch the next collation element in the text and the pattern each time through the loop. Normally both variables are true, but one or the other of them can be set to false if we want to skip an element. For example, setting getPattern to false and getTarget to true causes the current pattern element to be re-used and compared with the next text element, thus skipping the current text element.

    boolean match(CollationElementIterator text,

                  CollationElementIterator pattern)

    {

        int mask = getMask(weight);

        int done = CollationElementIterator.NULLORDER & mask;

      

        boolean getPattern = true, getTarget = true;

        int patternElement = 0, targetElement = 0;



        while (true) {

            if (getPattern) patternElement = pattern.next() & mask;

            if (getTarget) targetElement   = text.next()    & mask;

            getTarget = getPattern = true;  // By default get both

    

            if (patternElement == done) {

                break;                  // End of pattern

            } else if (targetElement == 0) {

              getPattern = false;       // skip targetElement

            } else if (patternElement == 0) {

              getTarget = false;        // skip patternElement

            } else if (targetElement != patternElement) {

              return false;                         // Mismatch

            }

        }

        return true;                                // No mismatches

    }

This is about the best you can do with the JDK 1.1 API. You can add bells and whistles, such as searching backward though text by reversing the order of the outer loop that calls match , but you can't really implement a more efficient search without a lot of work.

 |