[성능개선]KMP알고리즘 활용하여 50% 성능개선 해보기

최근 진행 중인 프로젝트에서 서명, 검증 기능을 개발하는 부분을 담당하고 있습니다. 
이번 포스트에서는 제가 어떻게 KMP 알고리즘을 이용하여 50%이상 성능개선을 이룰 수 있었는지 정리해보고자 합니다.

 

문제 상황

기존상황은 아래와 같습니다. 

검증하기 위해서는 byte[]로 되어 있는 구조체 전체에서 사내에서 정한 Delimiter(구분자)를 찾아야 했습니다. 

여기에서 제가 맞이한 문제는 아래와 같았습니다.

1. 구조체의 크기가 매우 크다.(최대 2GB)
2. 기존의 Delimiter를 찾는 방식은 O(M*N)의 시간복잡도를 가진다.

 

기존 탐색알고리즘

기존의 Delimiter를 찾는 방식은 아래와 같았습니다.

public static Integer getPatternIndex(byte[] parent, byte[] pattern){
    int parentSize = parent.length;
    int patternSize = pattern.length;


    //i is parent index
    for(int i = 0; i <= parentSize - patternSize; i++){
        Boolean found = Boolean.TRUE;
        //j is pattern index
        for(int j = 0; j < patternSize; j++){
            if(parent[i + j] != pattern[j]){
                found = Boolean.FALSE;
                break;
            }
        }

        if(found.equals(Boolean.TRUE)) return i;
    }
    //pattern 찾기 실패 시 -1 리턴
    return -1;
}

 

해당 방식은 이중 for문으로 O(M*N)시간 복잡도를 가진다는 것을 알 수 있습니다.

 

---

해결책

0. 효율적 알고리즘 선택

위의 비효율성을 해결하기 위해 우선 탐색알고리즘을 구글링 해봤습니다. 문자열 매칭알고리즘으로 KMP알고리즘과 Rabin-Karp알고리즘을 많이 쓴다는 것을 확인 할 수 있었습니다. 

 

이 중 저는 KMP알고리즘을 사용하기로 결정 했습니다. 

그 이유는 아래와 같습니다.

1. Delimiter는 4byte의 고정된 크기를 가진다 → KMP 테이블 생성에 있어 시간, 공간적 부담이 없다.
2. java byte의 overflow걱정을 할 필요 없다.(Rabin-Karp를 이용할 경우, hash 할 때, byte overflow문제를 고려해줘야 한다.)
3. 두 알고리즘의 worst-case 시간복잡도는 O(m+n)정도로 비슷하다.
   (이는 매우 특수한 값인 Delimiter를 사용했기에, Rabin-Karp의 superious hits는 없다고 가정할 경우이다.)

---

해결책 - KMP 알고리즘 구현 및 사내 최적화

이제 KMP알고리즘에 대해 간단히 알아보고 이를 구현해보도록 하겠습니다. 

1-1. KMP 알고리즘 - KMP Table 생성

아래의 내용은 KMP알고리즘 링크를 보고 정리한 내용입니다.

KMP알고리즘은 prefix(접두사)와 suffix(접미사)를 활용하여 naive 알고리즘을 개선한 알고리즘입니다.

그럼 가장 먼저 prefix, suffix가 무엇인지 정확히 알아보겠습니다.

 

a, b, c, d, a, b, c 라는 문자열이 있다고 가정 해 봅시다.

여기서 접두사는 a, ab, abc, abcd, abcda, abcdab, abcdabc가 됩니다.

그리고 접미사는 c, bc, abc, dabc, cdabc, bcdabc, abcdabc가 될 것입니다. 

 

어렵지 않은 개념이니 금방 이해할 수 있을 것이라 생각합니다.

 

KMP알고리즘은 prefix와 suffix가 일치하는 가장 긴 길이인 LPS(Longest Prefix, suffix)를 이용합니다.

아래표는 LPS테이블이 어떻게 구성되는지 보여줍니다. 

KMP Table

 

이 테이블을 생성하는 함수는 아래처럼 구현할 수 있습니다. 

public static byte[] getKMPTable(byte[] pattern) {
    int patternSize = pattern.length;

    if (patternSize > 256) {
        throw new RuntimeException("Pattern should be smaller than 255 bytes.");
    }

    // java에서 byte[]는 default로 0으로 초기화 된다.
    byte[] result = new byte[patternSize];

    int j = 0;
    for (int i = 1; i < patternSize; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = result[j - 1];
        }

        if (pattern[i] == pattern[j]) {
            result[i] = (byte) (++j);
        }
    }
    return result;
}

 

---

1-2. KMP 알고리즘 - 알고리즘 구현

아래 예를 통해 어떻게 개선했는지 알아보도록 하겠습니다.

naive algorithm

위 사진을 보면 5번째 Index에서 Text와 Pattern이 일치하지 않았습니다.

이 상황에서 기존의 naive 알고리즘을 사용한다면, Text의 Index 1부터, Pattern은 0부터 다시 일치하는지 하나씩 맞춰 볼 것입니다. 

KMP알고리즘은 이 상황에서 Text 4번째 인덱스 까지는 다시 볼 필요가 없다는 점을 이용하여 시간복잡도를 개선합니다. 
어떻게 4번째 인덱스까지는 볼 필요가 없다는 사실을 알 수 있을까요?

 

 

아래 표를 한번 살펴보겠습니다.

KMP algorithm - process1

KMP 알고리즘은 Text[i]와 Pattern[j]가 일치 하지 않았을 때, j를 Table[j-1]으로 옮겨줍니다. 
위 사진에서 i, j는 5이므로, j를 Table[5-1]의 값 0으로 옮겨주는 것입니다. 

이 상황에서(i = 5, j = 0) 다시 Text와 Pattern의 비교를 시작합니다. 

어떤가요? 다시 Text Index(i) 1부터 탐색하지 않고, 우리의 탐색을 이어갈 수 있습니다.

KMP algorithm - process2

그리고 이렇게 Pattern의 길이만큼 일치하는 Text를 찾았을 때, i - patternSize + 1을 리턴하면 Pattern의 위치를 찾을 수 있습니다.

여기에서는 5가 되겠죠.

 

 

이 로직은 아래 코드로 구현할 수 있습니다.

public static Integer findPatternByKmp(byte[] parent, byte[] pattern){
    int parentSize = parent.length;
    int patternSize = pattern.length;
    byte[] kmpTable = getKMPTable(pattern);

    int j = 0;
    for(int i = 0; i < parentSize; i++){
        while(j > 0 && parent[i] != pattern[j]){
            j = kmpTable[j - 1];
        }

        if(parent[i] == pattern[j]){
            if(j == patternSize - 1){
                return i - patternSize + 1;
            }
            j++;
        }
    }
    return null;
}

 

---

2-1. 구조체 구조에 따른 최적화

지금까지 일반적인 KMP알고리즘을 어떻게 구현할 수 있는지 알아봤습니다. 

이제 이 알고리즘을 제 검증 로직에서 사용하기 위해 최적화 시켜보도록 하겠습니다.

일반적인 알고리즘이 아닌 사내 최적화 코드는 공개가 어려운점 양해 부탁드립니다.

 

우선, Delimiter가 포함되어 있는 구조체는 대략 아래와 같은 구조를 가지고 있습니다.(사실 훨씬 복잡한 구조를 가지고 있지만...)
여기서 앞에 위치한 파일데이터가 매우 큰 사이즈를 가지고 있습니다.

구조체 구성

KMP알고리즘을 그대로 사용한다면 매우 큰 사이즈의 파일데이터부터 탐색을 시작하겠지만, 우리가 찾는 데이터는 항상 기타데이터 부분에 위치하고 있습니다. 즉, 스킵해도 될 파일데이터를 탐색하며 시간을 낭비하는 것 입니다.

 

이를 해결하기 위해 뒤에서부터 KMP 알고리즘 탐색을 하도록 하는 함수를 따로 구현하였습니다. 
전체 파일 사이즈를 기준으로 하여 일정 사이즈 이하는 기존 KMP알고리즘을 그대로 사용하고,
기준 사이즈를 초과한다면 뒤에서부터 탐색을 하도록 로직을 짜니, 기존의 방식보다 평균적으로 약 50%이상 성능 개선할 수 있었습니다. 

 

---

느낀점

항상 알고리즘 공부를 하면서 이런 알고리즘을 실제로 내가 쓸 일이 있을까? 라는 생각이 들때가 많았는데, 예전에 공부했던 알고리즘을 실제 비지니스 로직에 녹여 성능을 유의미하게 개선하는 경험은 정말 재밌었습니다.

 

 

결론 재밌다!