ShiftOr 알고리즘

이번 시간에는 ShiftOr이라는 근사 문자열 매칭 알고리즘에 대하여 이야기해보고자 합니다.

 

unix 계열의 agreap이라는 명령어에서 사용하고 있습니다.

https://en.wikipedia.org/wiki/Agrep

agrep - Wikipedia

 

대상이 되는 문자열에 패턴의 길이만큼 비트값으로 저장한 후, 이를 비트연산을 통하여 계산하면서 찾고자 하는 문자열의 위치를 찾는 알고리즘입니다.

public static int shiftOr(String text, String pattern) {
        long patternMask[] = new long[65536];

        Arrays.fill(patternMask, ~0L);

        long lim = 0, j = 1;
        for(int i = 0; i < pattern.length(); i++, j <<= 1){
            patternMask[pattern.charAt(i)] &= ~j;
            lim |= j;
        }

        lim = ~(lim >> 1);

        long state = ~0;
        for (int i = 0; i < text.length(); i++) {
            state = (state << 1) | patternMask[text.charAt(i)];

            if (state < lim) {
                return i + 1;
            }
        }
        return -1;
    }

 

해당 알고리즘은 이해하기 쉽고, 구현하기 비교적 간단하다는 장점을 가지고 있지만, 단순 매칭알고리즘의 형태로 사용하기에는 속도적인 측면에서 기본 JAVA알고리즘들에 비하여 많이 느리다는 단점을 가지고 있습니다.

 

대상 / pattern / 반복 횟수	ShiftOr	(java) indexOf	(java) contains
"abcdef" / "ab" / 100,000	3.328(s)	0.003(s)	0.007(s)

 

보시다시피, 매칭 알고리즘 용도로는 기본 내장 라이브러리 함수보다 많이 느린 것을 확인할 수 있습니다.

 

https://juggernaut.tistory.com/entry/%EC%89%AC%ED%94%84%ED%8A%B8OR-%EB%AC%B8%EC%9E%90%EC%97%B4-%EA%B2%80%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%98-%EC%84%A4%EB%AA%85Shift-OR-Algorithm

쉬프트-OR 문자열 검색 알고리즘의 설명(Shift OR Algorithm)

해당 블로그를 참고하였습니다.