ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Algorithm]Shift or String matching
    개발하면서 2010.11.21 18:48
    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+)

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


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

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

    댓글 0

Designed by Tistory.