C++로 구현하는 Bitap 알고리즘: 빠른 문자열 매칭 프로그램

이 글에서는 문자열 매칭(String Matching)을 위한 Bitap 알고리즘을 구현하는 C++ 프로그램을 소개합니다. Bitap 알고리즘은 주어진 텍스트 안에 특정 패턴과 '근사적으로 일치'하는 부분 문자열이 존재하는지 판별하는 알고리즘입니다. 여기서 근사 일치는 Levenshtein 거리(편집 거리)를 기준으로 정의되며, 부분 문자열과 패턴 사이의 거리가 주어진 값 k 이내라면 두 문자열은 일치하는 것으로 간주됩니다.

알고리즘은 먼저 패턴의 각 문자에 대해 하나의 비트를 담는 비트마스크(bitmask) 집합을 미리 계산합니다. 이렇게 하면 대부분의 연산을 비트 단위 연산으로 처리할 수 있어 실행 속도가 매우 빠르다는 장점이 있습니다.

알고리즘 동작 과정

시작
    텍스트 문자열 t와 패턴 문자열 p를 입력받는다.
    bitmap_search() 함수를 호출하며 인자로 텍스트 t와 패턴 p를 전달한다.
    비트 배열 A를 초기화한다.
    패턴 비트마스크 배열 p_mask[300]을 초기화한다.
    i = 0부터 299까지
        p_mask[i] = ~0 으로 설정
    i = 0부터 m-1까지 (m은 패턴의 길이)
        p_mask[p[i]] &= ~(1L << i)
    i = 0부터 t.length()-1까지
        A |= p_mask[t[i]]
        A <<= 1
        만약 (A & (1L << m)) == 0 이면
            return i - m + 1
    return -1
끝

예제 코드

#include <string>
#include <map>
#include <iostream>
using namespace std;
int bitmap_search(string t, string p) {
    int m = p.length();
    long p_mask[300];
    long A = ~1;
    if (m == 0)
        return -1;
    if (m >63) {
        cout<<"Pattern is too long!";//패턴이 너무 긴 경우
        return -1;
    }
    for (int i = 0; i <= 299; ++i)
        p_mask[i] = ~0;
    for (int i = 0; i < m; ++i)
        p_mask[p[i]] &= ~(1L << i);
    for (int i = 0; i < t.length(); ++i) {
        A |= p_mask[t[i]];
        A <<= 1;
        if ((A & (1L << m)) == 0)
            return i - m + 1;
    }
    return -1;
}

void findPattern(string t, string p) {
    int position = bitmap_search(t, p);//bitmap_search 함수의 결과로 위치를 초기화
    if (position == -1)
        cout << "\nNo Match\n";
    else
        cout << "\nPattern found at position : " << position;
}

int main(int argc, char **argv) {
    cout << "Enter Text:\n";
    string t;
    cin >>t;
    cout << "Enter Pattern:\n";
    string p;
    cin >>p;
    findPattern(t, p);
}

실행 결과

Enter Text:
Tutorialspoint
Enter Pattern:
point

Pattern found at position : 9

코드 설명

위 코드의 핵심은 bitmap_search() 함수입니다. 이 함수는 다음과 같은 순서로 동작합니다.

1. 초기화: 패턴 길이 m이 0이거나 63비트(long 타입 한계)를 초과하면 검색을 중단하고 -1을 반환합니다. 그런 다음 모든 비트마스크를 ~0(모든 비트가 1)으로 초기화합니다.

2. 비트마스크 생성: 패턴의 각 문자에 대해 해당 문자가 나타나는 위치의 비트를 0으로 설정합니다. 이를 통해 각 문자별 출현 위치 정보를 비트 형태로 저장합니다.

3. 텍스트 스캔: 텍스트를 한 글자씩 읽으면서 비트 배열 A를 갱신하고 왼쪽 시프트합니다. 매 단계마다 A의 m번째 비트를 검사하여 패턴 전체가 일치했는지 확인하고, 일치하면 시작 위치를 반환합니다.

이러한 비트 연산 기반 접근 방식 덕분에 Bitap 알고리즘은 짧은 패턴(64비트 이내)에 대해 매우 효율적으로 동작하며, 근사 문자열 매칭 분야에서 널리 활용됩니다.