ももの知恵の樹

C言語アルゴリズム-BM法

BM法のアルゴリズム

BM法の必要となる手順は「ずらし表の生成」と「末尾からのパターン照合」です。


BM法ずらし表を生成する。

BM法のずらし表（不一致になった文字によって，パターンを何文字ずらすかを決定するテーブル）を作成します。


手順１：パターンに現れる文字のずらし幅を決定します。

パターンの各文字が「末尾から何文字目であるか」を調べます。例えば、パターンが「G, C, T, C, G」の場合では以下の通りです。

パターン G C T C G
ずらし幅 4 3 2 1 0

手順２：テキストとして現れる文字全てのずらし幅を決定します。

パターンに現れない文字は全て「パターン文字列長」だけずらし幅を持たせます。（例えば、ASCIIコード（1バイトの文字）は255個分のずらし幅を設定します。）

パターンに同じ文字が存在する場合には小さい数のずらし幅が優先されます。

最終的なずらし表は以下の通りになります。

パターン T C G それ以外の文字
ずらし幅 2 1 0 5

BM法のパターン照合

BM法では、ずらし幅テーブルを参照しながら、パターンの末尾から先頭に向かって順番に、テキストの文字と比較していきます。

テキストを「GCTCACTGAGCGCTCGT」、パターンを「GCTCG」とした場合の照合手順は以下の通りです。


テキストとパターンを重ねて、パターン末尾位置の文字を照合します。テキストの文字「A」はずらし表における「それ以外の文字」なので、パターンを「５文字進める」ことになります。

テキスト G C T C A C T G A G C G C T C G T
パターン G C T C G - - - - - - - - - - - -

さらに照合を行います。文字「G」が一致したので、前の文字を照合します。文字「A」が現れたので、照合点を基準として、パターンを「５文字進め」ます。

テキスト G C T C A C T G A G C G C T C G T
パターン - - - - - G C T C G - - - - - - -

文字「T」が現れたので、ずらし表を参照して、パターンを「２文字進め」ます。

テキスト G C T C A C T G A G C G C T C G T
パターン - - - - - - - - - G C T C G - - -

パターンの末尾から先頭に向かってテキストの文字と比較していき、完全一致した場合は探索が完了します。

テキスト G C T C A C T G A G C G C T C G T
パターン - - - - - - - - - - - G C T C G -

C言語によるBM法の探索プログラム

以下は探索プログラムです。

コメントの「ループ防止」とは、ずらし幅を決定する際に無限ループしてしまわないように、次の照合文字へ正しく移動できるように対応していることを意味します。 


#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

#define BM_TABLE_SIZE 256

/*!
 * @brief         ずらし表（照合再開位置テーブル）を作成する
 * @param[in/out] table    テーブルへのアドレス
 * @param[in]     pattern  探索文字列
 * @param[in]     pat_len  パターン文字列長
 */
static void
bm_table_init(int *table, const char *pattern, int ptn_len)
{
    int cnt = 0;

    /* パターンに無い文字はパターン文字列長をずらし幅にする */
    for(cnt = 0; cnt < BM_TABLE_SIZE; cnt++){
	table[cnt] = ptn_len;
    }

    /* パターンに含まれる文字のずらし幅を決定する */
    for(cnt = 0; cnt < ptn_len; cnt++){
	table[(int)pattern[cnt]] = ptn_len - cnt - 1;
    }

    /* デバッグ出力 */
    printf("[table]  : default: step=%d\n", ptn_len);
    for(cnt = 0; cnt < BM_TABLE_SIZE; cnt++){
        if(table[cnt] != ptn_len)
            printf("         : char=%c: table[%03d]: step=%d\n",
                   (char)cnt,cnt,(int)table[cnt]);
    }
}

/*!
 * @brief    デバッグ出力
 */
static void
print_compare_process(const char *text, const char *pattern, int i, int j)
{
    int cnt = 0;

    printf("-----------------------------------\n");
    printf("[compare]:(text i=%d)(pattern j=%d)\n", i, j);
    printf(" text    :%s\n", text);

    /* パターンを比較位置で重ねる */
    printf(" pattern :");
    for(cnt = 0;cnt < (i - j); cnt++) printf(" ");
    printf("%s\n", pattern);

    /* 比較点にマークする */
    printf("         :");
    for(cnt = 0;cnt < i; cnt++) printf(" ");
    printf("^\n");
}

/*!
 * @brief      パターンを進める加算値を求める
 * @param[in]  table  ずらし表
 * @param[in]  target 比較点の文字
 * @param[in]  remain パターンの未比較部分の文字列長
 * @return     パターンを進める加算値。
 */
static int
next_step(int *table, char target, int remain)
{
    /* ループ防止のために確認する */
    if(table[(int)target] > remain){
        /* ずらし表から値を取得する */
        return(table[(int)target]);
    }else{
        /* 照合を開始した地点の次の文字に進める */
        return(remain);
    }
}

/*!
 * @brief      文字列を探索する
 * @param[in]  text     検索対象文字列
 * @param[in]  pattern  検索文字列
 * @return     発見位置のポインタを返す。失敗したらNULLを返す。
 */
char *
bm_search(const char *text, const char *pattern)
{
    int table[BM_TABLE_SIZE];
    int txt_len = 0;
    int ptn_len = 0;
    int i = 0; /* テキストの比較位置 */
    int j = 0; /* パターンの比較位置 */

    ptn_len = strlen(pattern);
    txt_len = strlen(text);

    /* ずらし表を作成する */
    bm_table_init(table, pattern, ptn_len);

    /* 比較処理 */
    i = j = ptn_len - 1; /* 比較位置をパターン末尾にする */
    while((i < txt_len) && (j >= 0)){
        print_compare_process(text, pattern, i, j);

        if(text[i] != pattern[j]){
            /* ずらし表を参照して、次の比較位置を設定する */
            i += next_step(table, text[i], (ptn_len - j));
            j = ptn_len - 1;   /* 比較位置をパターン末尾にする */
        }else{
            /* 文字が一致したので、前の文字を照合していく */
            j--;
            i--;
        }
    }

    if(j < 0) return((char *)text + (i + 1));
    return(NULL);
}

int
main(void)
{
    char *text    = "GCTCACTGAGCGCTCGT";
    char *pattern = "GCTCG";
    char *cp = NULL;

    printf("[text]   :%s\n", text);
    printf("[pattern]:%s\n", pattern);

    cp = bm_search(text, pattern);
    if(cp == NULL){
        printf("[result] : not found\n");
    }else{
        printf("[result] : found\n");
        printf("         : text=%s\n", cp);
    }
   
    return(EXIT_SUCCESS);
}

関連ページ