JAVA에서의 Boyer-Moore

해당 글은 보이어 무어 알고리즘을 사용하고 있는 JAVA의 내부 코드에 대해 이야기하고자 합니다.

Boyer-Moore에 대해서는 해당 글 참조 부탁드립니다.

https://lms0806.tistory.com/210

A Fast StringSearching Algorithm 리뷰

 

해당 글의 마지막에 보이어 무어 알고리즘을 사용하고 있는 BMPatter.java에 대해 링크를 남긴적이 있습니다.

이제는 저희가 자주 사용중인 내부 라이브러리 함수 중에 Boyer-Moore 알고리즘을 사용중인 것에 대해 이야기해보고자 합니다.

 

"123".replaceAll("1", "");

가장 먼저 자주 사용하시는 replaceAll의 내부 함수에서 Boyer-Moore 알고리즘을 사용하고 있습니다.

 

replaceAll(regex, replacement);

Pattern.compile(regex).matcher(this).replaceAll(replacement);

replaceAll 함수는 내부적으로 Pattern의 compile 함수의 matcher 함수의 replaceAll 함수를 사용하고 있습니다.

 

그 중, matcher 함수를 확인해보면, 다음과 같습니다.

public Matcher matcher(CharSequence input) {
    if (!compiled) {
        synchronized(this) {
            if (!compiled)
                compile();
        }
    }
    Matcher m = new Matcher(this, input);
    return m;
}

 

해당 함수의 compile() 함수의 내부를 들여다보면 다음과 같습니다.

// Peephole optimization
if (matchRoot instanceof Slice) {
    root = BnM.optimize(matchRoot);
    if (root == matchRoot) {
        root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);
    }
} else if (matchRoot instanceof Begin || matchRoot instanceof First) {
     root = matchRoot;
} else {
     root = hasSupplementary ? new StartS(matchRoot) : new Start(matchRoot);
}

해당 소스는 compile() 함수의 일부분만 가져왔습니다.

 

여기서 BnM이 Boyer-Moore로 이루어진 class입니다.

/**
     * Attempts to match a slice in the input using the Boyer-Moore string
     * matching algorithm. The algorithm is based on the idea that the
     * pattern can be shifted farther ahead in the search text if it is
     * matched right to left.
     * <p>
     * The pattern is compared to the input one character at a time, from
     * the rightmost character in the pattern to the left. If the characters
     * all match the pattern has been found. If a character does not match,
     * the pattern is shifted right a distance that is the maximum of two
     * functions, the bad character shift and the good suffix shift. This
     * shift moves the attempted match position through the input more
     * quickly than a naive one position at a time check.
     * <p>
     * The bad character shift is based on the character from the text that
     * did not match. If the character does not appear in the pattern, the
     * pattern can be shifted completely beyond the bad character. If the
     * character does occur in the pattern, the pattern can be shifted to
     * line the pattern up with the next occurrence of that character.
     * <p>
     * The good suffix shift is based on the idea that some subset on the right
     * side of the pattern has matched. When a bad character is found, the
     * pattern can be shifted right by the pattern length if the subset does
     * not occur again in pattern, or by the amount of distance to the
     * next occurrence of the subset in the pattern.
     *
     * Boyer-Moore search methods adapted from code by Amy Yu.
     */
     
     /**
 * Boyer-Moore 문자열을 사용하여 입력의 슬라이스를 일치시키려고 시도합니다.
 * 일치 알고리즘. 알고리즘은 다음과 같은 아이디어를 기반으로 합니다.
 * 패턴이 다음과 같은 경우 검색 텍스트에서 더 앞으로 이동할 수 있습니다.
 * 오른쪽에서 왼쪽으로 일치합니다.
 * <p>
 * 패턴은 한 번에 한 문자씩 입력된 것과 비교됩니다.
 * 왼쪽 패턴에서 가장 오른쪽 문자. 캐릭터의 경우
 * 모두 일치하는 패턴이 발견되었습니다. 문자가 일치하지 않는 경우,
 * 패턴은 최대 2만큼 오른쪽으로 이동합니다.
 * 기능, 잘못된 문자 이동 및 좋은 접미사 이동. 이것
 * Shift는 입력을 통해 일치 시도 위치를 이동합니다.
 * 한 번에 한 위치씩 순진하게 확인하는 것보다 빠르게.
 * <p>
 * 잘못된 문자 이동은 해당 텍스트의 문자를 기반으로 합니다.
 * 일치하지 않습니다. 패턴에 문자가 나타나지 않으면
 * 패턴은 나쁜 캐릭터를 넘어 완전히 바뀔 수 있습니다. 만약
 * 문자가 패턴에 나타나면 패턴을 다음으로 이동할 수 있습니다.
 * 해당 문자가 다음에 나타나는 패턴을 정렬합니다.
 * <p>
 * 좋은 접미사 이동은 일부 하위 집합이 오른쪽에 있다는 생각에 기초합니다.
 * 패턴의 측면이 일치했습니다. 나쁜 캐릭터가 발견되면,
 * 하위 집합이 오른쪽으로 이동하는 경우 패턴은 패턴 길이만큼 오른쪽으로 이동할 수 있습니다.
 * 패턴이나 거리에 따라 다시 발생하지 않습니다.
 * 패턴에서 하위 집합의 다음 발생.
 *
 * Amy Yu의 코드를 적용한 Boyer-Moore 검색 방법.
 */

해당 주석은 BnM class의 상단 주석으로 되어 있는 부분을 구글 번역기를 통해 번역한 결과입니다.

 

상단의 compile()함수를 보자면 다음과 같습니다.

/**
         * Pre calculates arrays needed to generate the bad character
         * shift and the good suffix shift. Only the last seven bits
         * are used to see if chars match; This keeps the tables small
         * and covers the heavily used ASCII range, but occasionally
         * results in an aliased match for the bad character shift.
         */
        static Node optimize(Node node) {
            if (!(node instanceof Slice)) {
                return node;
            }

            int[] src = ((Slice) node).buffer;
            int patternLength = src.length;
            // The BM algorithm requires a bit of overhead;
            // If the pattern is short don't use it, since
            // a shift larger than the pattern length cannot
            // be used anyway.
            if (patternLength < 4) {
                return node;
            }
            int i, j;
            int[] lastOcc = new int[128];
            int[] optoSft = new int[patternLength];
            // Precalculate part of the bad character shift
            // It is a table for where in the pattern each
            // lower 7-bit value occurs
            for (i = 0; i < patternLength; i++) {
                lastOcc[src[i]&0x7F] = i + 1;
            }
            // Precalculate the good suffix shift
            // i is the shift amount being considered
NEXT:       for (i = patternLength; i > 0; i--) {
                // j is the beginning index of suffix being considered
                for (j = patternLength - 1; j >= i; j--) {
                    // Testing for good suffix
                    if (src[j] == src[j-i]) {
                        // src[j..len] is a good suffix
                        optoSft[j-1] = i;
                    } else {
                        // No match. The array has already been
                        // filled up with correct values before.
                        continue NEXT;
                    }
                }
                // This fills up the remaining of optoSft
                // any suffix can not have larger shift amount
                // then its sub-suffix. Why???
                while (j > 0) {
                    optoSft[--j] = i;
                }
            }
            // Set the guard value because of unicode compression
            optoSft[patternLength-1] = 1;
            if (node instanceof SliceS)
                return new BnMS(src, lastOcc, optoSft, node.next);
            return new BnM(src, lastOcc, optoSft, node.next);
        }

 

BnM class는 다음과 같고

BnM(int[] src, int[] lastOcc, int[] optoSft, Node next) {
            this.buffer = src;
            this.lastOcc = lastOcc;
            this.optoSft = optoSft;
            this.next = next;
        }

 

BnMS class는 다음과 같습니다.

BnMS(int[] src, int[] lastOcc, int[] optoSft, Node next) {
            super(src, lastOcc, optoSft, next);
            for (int cp : buffer) {
                lengthInChars += Character.charCount(cp);
            }
        }

BnMS class는 BnM class를 상속하고 있습니다.

 

보이어 무어 알고리즘은 PS(Problem Solving)에서는 사용하고 있지 않지만, 보시는 바와 같이 JAVA 내부 등 여러 방면에서 해당 알고리즘을 사용하고 있는 것을 볼 수 있습니다.