[Algorithm]Shift or String matching

Shift or 알고리즘에 대해 알아보기로 합니다.  명칭부터가 비트 연산으로 비교할 것 같은 느낌이 물씬 나는데요. . .ㅎㅎ;;

알고리즘을 진행하면서 text, pattern 문자열 외에 필요한 변수는 다음과 같습니다.

 

현재 진행 상태를 나타내는 unsigned long형의 변수

비교할 pattern의 위치를 bit로 표시해줄 unsigned long형의 변수

KMP알고리즘에서도 그랬지만 여기서도 전처리 과정이 필요합니다.

 

첫번째, 현재 진행 상태를 나타내는 변수, 32개 비트를 0으로 초기화 합니다.

 

move_bit = ~1;

 

두번째, 비교할 pattern에서 해당되는 위치는 0, 나머지는 1로 초기화합니다.

for ( i = 0 ~ pattern length )
     pattern_mask[i] = ~0;
for (i = 0 ~ pattern length )
     pattern_mask[pattern[i]] &= ~(1UL << i );

 

text = kana k kasdf kang han asdfkang han gooxvxcva

pattern = kang han goo

을 예로 들어 설명하겠습니다.

 

전처리 후에 준비된 변수는 다음과 같습니다.

 

move_bit = 0000 0000 0000 0000 0000 0000 0000 0000

pattern_mask['k'] = 1111 1111 1111 1111 1111 1111 1111 1110

pattern_mask['a'] = 1111 1111 1111 1111 1111 1111 1011 1101

pattern_mask['n'] = 1111 1111 1111 1111 1111 1111 0111 1011

pattern_mask['g'] = 1111 1111 1111 1111 1111 1101 1111 0111

pattern_mask['h'] = 1111 1111 1111 1111 1111 1111 1101 1111

pattern_mask['n'] = 1111 1111 1111 1111 1111 1111 1111 1111

pattern_mask['o'] = 1111 1111 1111 1111 1111 0011 1111 1111

pattern_mask[' '] = 1111 1111 1111 1111 1111 1110 1110 1111

순서도는 아래와 같습니다

pattern의 길이가 m, text길이가 n이라 할 때

전처리 : O(m+ n )

 

문자열 처리 O(mn) 의 복잡도를 가집니다.

#include <stdio.h>
#include <string.h>
#include <limits.h>

const int LIMIT_TAB=20;

void bit_print(char *buf, unsigned long bit);

const char *bitap_bitwise_search(const char *text, const char *pattern)
{
    int m = strlen(pattern);
    unsigned long move_bit;
    unsigned long pattern_mask[CHAR_MAX+1];
    int i;
    #ifdef _DEBUG
    char buf[50];
    #endif

    if (pattern[0] == '\0') return text;
    if (m > 31) return "The pattern is too long!";

    /* Initialize the bit array R */
    move_bit = ~1;

#ifdef _DEBUG
    printf("goal is move_bit & (1UL<<m) equal 0\n");
#endif

    /* Initialize the pattern bitmasks */
    for (i=0; i <= CHAR_MAX; ++i)
        pattern_mask[i] = ~0;
    for (i=0; i < m; ++i)
        pattern_mask[pattern[i]] &= ~(1UL << i);

    for (i=0; text[i] != '\0'; ++i) {
     /* Update the bit array */
#ifdef _DEBUG
    bit_print("move_bit", move_bit);
    sprintf(buf, "pattern_mask[%c]", text[i]);
    bit_print(buf, pattern_mask[text[i]]);

#endif
        move_bit |= pattern_mask[text[i]];
        move_bit <<= 1;

        if (0 == (move_bit & (1UL << m)))
          return (text + i - m) + 1;
    }

    return NULL;
}
int main()
{
    char *pattern = "kang han goo";
    char * text = "kana k kasdf kang han asdfkang han gooxvxcva";

    const char *find;
    unsigned long t = 32;

    find = bitap_bitwise_search(text, pattern);
    printf("find : %s\n", find);

    //bit_print("sample", t);

    return 0;
}

void bit_print(char *buf, unsigned long bit)
{
    int i;
    int buf_len;
    unsigned long mask;

    mask = (1UL <<31 );

    buf_len = strlen(buf);

    for ( i = 0; i < (LIMIT_TAB - buf_len); i++ )
    {
        printf(" ");
    }
    printf("%s : ", buf);

    for ( i = 0; i < 32; i++ )
    {
        if (i%4 == 0)
        {
            printf("  ");
        }
        printf("%d", (bit & mask) >> (31-i));
        mask >>= 1;
    }
    printf("\n");
}

 

출처 : http://en.wikipedia.org/wiki/Bitap_algorithm

ps. 마지막에 개선된것같은데 이것도 한번 들여다봐야겠습니다.