C言語関係掲示板

過去ログ

No．１０９０　BM法について

[戻る]　[ホームページ]
No.14299
BM法について
投稿者---Ｑ児(2004/05/29 22:11:25)		 


<pre>？？？の部分が分かりません。お知恵拝借のほどお願い致しします。
一応自分なりに考えて埋めたプログラムは上、下は問題プログラムです。
私の答えが間違っている可能性もあるので、
下記に問題プログラムを掲載しておきます。
/*
  
  現在位置以降の文字列検索 (Boyer-Moore algorithm : BM 法)
  int bm_search(unsigned char text[], int place, unsigned char pattern[])
      引数   text[]    検索対象文字列 (テキスト), 
             place     現在位置,
             pattern[] 検索文字列 (パターン)
      戻り値 見つかった場合   → 最初に発見した位置(文字列始点)
             見つからない場合 → ERR
*/
#include &lt;stdio.h&gt;
#include &lt;string.h&gt;

#define  SIZE       81
#define  ERR        -1
#define  max(a, b)  ((a) &gt; (b) ? a : b)

int bm_search(unsigned char text[], int place, unsigned char pattern[]);

void main(void)
{
    char data[SIZE];
    char word[SIZE];
    int  i, j, p, w_len, cnt;
    
    printf(&quot;検索対象文字列 : &quot;);
    gets(data);
    
    printf(&quot;検索語 = &quot;);
    gets(word);
    w_len = strlen(word);
    
    cnt = 0;
    for(i = 0; (p = bm_search(data, i, word)) != ERR; i = p + 1){
        puts(data);
        for(j = 0; j &lt; p; j++){
            printf(&quot; &quot;);
        }
        while(j &lt; p + w_len){    /* 検索語にアンダーラインを記す */
            printf(&quot;^&quot;);
            j++;
        }
        printf(&quot;\n&quot;);
        cnt++;
    }
    if(cnt == 0){
        printf(&quot;%s は見つかりません.\n&quot;, word);
    }
    else{
        printf(&quot;%d カ所発見しました.\n&quot;, cnt);
    }
}

/* 文字列 text から文字列 pattern を探索する (BM法) */
int bm_search(unsigned char text[], int place, unsigned char pattern[])
{
    int skip[256]; /* テキストとパターンが不一致のときずらす分量を示す表 */
                   /* 1 バイト文字が 0 -- 255 までの値をとるから大きさ 256 */
    /* 変数 i は注目しているテキストの位置,
       変数 j は注目しているパターンの位置を表す */
    int i, j;
    int pat_len = strlen(pattern), text_len = strlen(text);
    
    /* 表 skip を作成する */
    for(i = 0; i &lt; 256; i++)
        skip[i] = pat_len;
    for(i = 0; i &lt; pat_len - 1; i++)
        skip[text[i]] = /* ??? */;
    
    i = place + pat_len - 1; /* i は (パターン長 - 1) に初期化 */
    
    /* テキストの最後尾に行き当たるまで繰り返す */
    while(i &lt; text_len){
        j = pat_len - 1;   /* j はパターンの末尾を指すようにする */
        while(text[i] == pattern[j]){
            if(j == 0)
                return(i);    /* 探索は成功 */
            i--;
            j--;
        }
        i += max(skip[text[i]], pat_len - j);      /* 不一致, パターンをずらす */
    }
    return(ERR);          /* 結局見つからなかった */
}




//問題プログラム
/*
  
  現在位置以降の文字列検索 (Boyer-Moore algorithm : BM 法)
  int bm_search(unsigned char text[], int place, unsigned char pattern[])
      引数   text[]    検索対象文字列 (テキスト), 
             place     現在位置,
             pattern[] 検索文字列 (パターン)
      戻り値 見つかった場合   → 最初に発見した位置(文字列始点)
             見つからない場合 → ERR
*/
#include &lt;stdio.h&gt;
#include &lt;string.h&gt;

#define  SIZE       81
#define  ERR        -1
#define  max(a, b)  ((a) &gt; (b) ? a : b)

int bm_search(unsigned char text[], int place, unsigned char pattern[]);

void main(void)
{
    char data[SIZE];
    char word[SIZE];
    int  i, j, p, w_len, cnt;
    
    printf(&quot;検索対象文字列 : &quot;);
    gets(data);
    
    printf(&quot;検索語 = &quot;);
    gets(word);
    w_len = strlen(word);
    
    cnt = 0;
    for(i = 0; (p = bm_search(data, i, word)) != ERR; i = p + 1){
        puts(data);
        for(j = 0; j &lt; p; j++){
            printf(&quot; &quot;);
        }
        while(j &lt; p + w_len){    /* 検索語にアンダーラインを記す */
            printf(&quot;^&quot;);
            j++;
        }
        printf(&quot;\n&quot;);
        cnt++;
    }
    if(cnt == 0){
        printf(&quot;%s は見つかりません.\n&quot;, word);
    }
    else{
        printf(&quot;%d カ所発見しました.\n&quot;, cnt);
    }
}

/* 文字列 text から文字列 pattern を探索する (BM法) */
int bm_search(unsigned char text[], int place, unsigned char pattern[])
{
    int skip[256]; /* テキストとパターンが不一致のときずらす分量を示す表 */
                   /* 1 バイト文字が 0 -- 255 までの値をとるから大きさ 256 */
    /* 変数 i は注目しているテキストの位置,
       変数 j は注目しているパターンの位置を表す */
    int i, j;
    int pat_len = strlen(pattern), text_len = strlen(text);
    
    /* 表 skip を作成する */
    for(i = 0; i &lt; 256; i++)
        /* ??? */;
    for(i = 0; i &lt; pat_len - 1; i++)
        skip[/* ??? */] = /* ??? */;
    
    i = place + pat_len - 1; /* i は (パターン長 - 1) に初期化 */
    
    /* テキストの最後尾に行き当たるまで繰り返す */
    while(i &lt; text_len){
        j = pat_len - 1;   /* j はパターンの末尾を指すようにする */
        while(/* ??? */){
            if(/* ??? */)
                return(/* ??? */);    /* 探索は成功 */
            /* ??? */;
            /* ??? */;
        }
        /* ??? */;      /* 不一致, パターンをずらす */
    }
    /* ??? */;          /* 結局見つからなかった */
}



</pre>


No.14300
Re:BM法について
投稿者---boring(2004/05/29 23:05:48)


http://www.tachiki.com/cgi-bin/chatc/ealis.cgi

No.14301
Re:BM法について
投稿者---あかま(2004/05/29 23:09:50)		 


コンバートを2回押したっぽく文字化けしているので代わりにもっかい貼りなおしてみる。

？？？の部分が分かりません。お知恵拝借のほどお願い致しします。
一応自分なりに考えて埋めたプログラムは上、下は問題プログラムです。
私の答えが間違っている可能性もあるので、
下記に問題プログラムを掲載しておきます。
/*
  
  現在位置以降の文字列検索 (Boyer-Moore algorithm : BM 法)
  int bm_search(unsigned char text[], int place, unsigned char pattern[])
      引数   text[]    検索対象文字列 (テキスト), 
             place     現在位置,
             pattern[] 検索文字列 (パターン)
      戻り値 見つかった場合   → 最初に発見した位置(文字列始点)
             見つからない場合 → ERR
*/
#include <stdio.h>
#include <string.h>

#define  SIZE       81
#define  ERR        -1
#define  max(a, b)  ((a) > (b) ? a : b)

int bm_search(unsigned char text[], int place, unsigned char pattern[]);

void main(void)
{
    char data[SIZE];
    char word[SIZE];
    int  i, j, p, w_len, cnt;
    
    printf("検索対象文字列 : ");
    gets(data);
    
    printf("検索語 = ");
    gets(word);
    w_len = strlen(word);
    
    cnt = 0;
    for(i = 0; (p = bm_search(data, i, word)) != ERR; i = p + 1){
        puts(data);
        for(j = 0; j < p; j++){
            printf(" ");
        }
        while(j < p + w_len){    /* 検索語にアンダーラインを記す */
            printf("^");
            j++;
        }
        printf("\n");
        cnt++;
    }
    if(cnt == 0){
        printf("%s は見つかりません.\n", word);
    }
    else{
        printf("%d カ所発見しました.\n", cnt);
    }
}

/* 文字列 text から文字列 pattern を探索する (BM法) */
int bm_search(unsigned char text[], int place, unsigned char pattern[])
{
    int skip[256]; /* テキストとパターンが不一致のときずらす分量を示す表 */
                   /* 1 バイト文字が 0 -- 255 までの値をとるから大きさ 256 */
    /* 変数 i は注目しているテキストの位置,
       変数 j は注目しているパターンの位置を表す */
    int i, j;
    int pat_len = strlen(pattern), text_len = strlen(text);
    
    /* 表 skip を作成する */
    for(i = 0; i < 256; i++)
        skip[i] = pat_len;
    for(i = 0; i < pat_len - 1; i++)
        skip[text[i]] = /* ??? */;
    
    i = place + pat_len - 1; /* i は (パターン長 - 1) に初期化 */
    
    /* テキストの最後尾に行き当たるまで繰り返す */
    while(i < text_len){
        j = pat_len - 1;   /* j はパターンの末尾を指すようにする */
        while(text[i] == pattern[j]){
            if(j == 0)
                return(i);    /* 探索は成功 */
            i--;
            j--;
        }
        i += max(skip[text[i]], pat_len - j);      /* 不一致, パターンをずらす */
    }
    return(ERR);          /* 結局見つからなかった */
}




//問題プログラム
/*
  
  現在位置以降の文字列検索 (Boyer-Moore algorithm : BM 法)
  int bm_search(unsigned char text[], int place, unsigned char pattern[])
      引数   text[]    検索対象文字列 (テキスト), 
             place     現在位置,
             pattern[] 検索文字列 (パターン)
      戻り値 見つかった場合   → 最初に発見した位置(文字列始点)
             見つからない場合 → ERR
*/
#include <stdio.h>
#include <string.h>

#define  SIZE       81
#define  ERR        -1
#define  max(a, b)  ((a) > (b) ? a : b)

int bm_search(unsigned char text[], int place, unsigned char pattern[]);

void main(void)
{
    char data[SIZE];
    char word[SIZE];
    int  i, j, p, w_len, cnt;
    
    printf("検索対象文字列 : ");
    gets(data);
    
    printf("検索語 = ");
    gets(word);
    w_len = strlen(word);
    
    cnt = 0;
    for(i = 0; (p = bm_search(data, i, word)) != ERR; i = p + 1){
        puts(data);
        for(j = 0; j < p; j++){
            printf(" ");
        }
        while(j < p + w_len){    /* 検索語にアンダーラインを記す */
            printf("^");
            j++;
        }
        printf("\n");
        cnt++;
    }
    if(cnt == 0){
        printf("%s は見つかりません.\n", word);
    }
    else{
        printf("%d カ所発見しました.\n", cnt);
    }
}

/* 文字列 text から文字列 pattern を探索する (BM法) */
int bm_search(unsigned char text[], int place, unsigned char pattern[])
{
    int skip[256]; /* テキストとパターンが不一致のときずらす分量を示す表 */
                   /* 1 バイト文字が 0 -- 255 までの値をとるから大きさ 256 */
    /* 変数 i は注目しているテキストの位置,
       変数 j は注目しているパターンの位置を表す */
    int i, j;
    int pat_len = strlen(pattern), text_len = strlen(text);
    
    /* 表 skip を作成する */
    for(i = 0; i < 256; i++)
        /* ??? */;
    for(i = 0; i < pat_len - 1; i++)
        skip[/* ??? */] = /* ??? */;
    
    i = place + pat_len - 1; /* i は (パターン長 - 1) に初期化 */
    
    /* テキストの最後尾に行き当たるまで繰り返す */
    while(i < text_len){
        j = pat_len - 1;   /* j はパターンの末尾を指すようにする */
        while(/* ??? */){
            if(/* ??? */)
                return(/* ??? */);    /* 探索は成功 */
            /* ??? */;
            /* ??? */;
        }
        /* ??? */;      /* 不一致, パターンをずらす */
    }
    /* ??? */;          /* 結局見つからなかった */
}




No.14306
Re:BM法について
投稿者---あかま(2004/05/30 01:22:55)		 


BM法はアタマがこんがらがるので、あってるかどうかは分からないけど
何回かテストして動いたのでのっけてみる。

/* 不一致, パターンをずらす */のところはＱ児さんのでも動いたので
どっちが正しいのか、両方正しいのかも不明。


/* 文字列 text から文字列 pattern を探索する (BM法) */
int bm_search(unsigned char text[], int place, unsigned char pattern[])
{
    int skip[256]; /* テキストとパターンが不一致のときずらす分量を示す表 */
                   /* 1 バイト文字が 0 -- 255 までの値をとるから大きさ 256 */
    /* 変数 i は注目しているテキストの位置,
       変数 j は注目しているパターンの位置を表す */
    int i, j;
    int pat_len = strlen(pattern), text_len = strlen(text);
    
    /* 表 skip を作成する */
    for(i = 0; i < 256; i++)
        skip[i] = pat_len;
    for(i = 0; i < pat_len-1; i++)//
        skip[pattern[i]] = pat_len-i-1;
    
    i = place + pat_len - 1; /* i は (パターン長 - 1) に初期化 */
    
    /* テキストの最後尾に行き当たるまで繰り返す */
    while(i < text_len){
        j = pat_len - 1;   /* j はパターンの末尾を指すようにする */
        //printf("%c:%c\n",text[i],text[j]);
        while(text[i]==pattern[j]){
            
            if(j==0)
                return(i);    /* 探索は成功 */
            j--;
            i--;
        }
        i+= ((pat_len-1)-j)+skip[text[i+((pat_len-1)-j)]];      /* 不一致, パターンをずらす */
    }
    return ERR;          /* 結局見つからなかった */
}


No.14307
Re:BM法について
投稿者---Ｑ児(2004/05/30 12:00:14)


サンプルを実行したところ比較回数がちゃんと合っていました。
どうもありがとうございます。

No.14308
再：BM法について
投稿者---Ｑ児(2004/05/30 13:08:04)		 


text→AABCABxyzw 
pattern→ABCAB
この場合、一致する文字があるにもかかわらず見つかった場合の処理が実行されません。
プログラムをどのように変更すればいいか教えてください。
/*
  現在位置以降の文字列検索 (Boyer-Moore algorithm : BM 法)
  int bm_search(unsigned char text[], int place, unsigned char pattern[])
      引数   text[]    検索対象文字列 (テキスト), 
             place     現在位置,
             pattern[] 検索文字列 (パターン)
      戻り値 見つかった場合   → 最初に発見した位置(文字列始点)
             見つからない場合 → ERR
*/
#include <stdio.h>
#include <string.h>

#define  SIZE       81
#define  ERR        -1
#define  max(a, b)  ((a) > (b) ? a : b)

int count = 0;
int bm_search(unsigned char text[], int place, unsigned char pattern[]);

void main(void)
{
    char data[SIZE];
    char word[SIZE];
    int  i, j, p, w_len, cnt;
    
    printf("検索対象文字列 : ");
    gets(data);
    
    printf("検索語 = ");
    gets(word);
    w_len = strlen(word);
    
    cnt = 0;
    for(i = 0; (p = bm_search(data, i, word)) != ERR; i = p + 1){
        puts(data);
        for(j = 0; j < p; j++){
            printf(" ");
        }
        while(j < p + w_len){    /* 検索語にアンダーラインを記す */
            printf("^");
            j++;
        }
        printf("\n");
        cnt++;
    }
    if(cnt == 0){
        printf("%s は見つかりません.\n", word);
    }
    else{
        printf("%d カ所発見しました.\n", cnt);
    }
    printf("探索回数%d回\n", count);
}

/* 文字列 text から文字列 pattern を探索する (BM法) */
int bm_search(unsigned char text[], int place, unsigned char pattern[])
{
    int skip[256]; /* テキストとパターンが不一致のときずらす分量を示す表 */
                   /* 1 バイト文字が 0 -- 255 までの値をとるから大きさ 256 */
    /* 変数 i は注目しているテキストの位置,
       変数 j は注目しているパターンの位置を表す */
    int i, j;
    int pat_len = strlen(pattern), text_len = strlen(text);
    
    /* 表 skip を作成する */
    for(i = 0; i < 256; i++)
        skip[i] = pat_len;
    for(i = 0; i < pat_len - 1; i++)
        skip[text[i]] = pat_len - i - 1;
    
    for(i = 0; i < pat_len - 1; i++)
        printf("skip[%c] = %d\n", text[i], skip[text[i]]);
        
    i = place + pat_len - 1; /* i は (パターン長 - 1) に初期化 */
    
    /* テキストの最後尾に行き当たるまで繰り返す */
    while(i < text_len){
        j = pat_len - 1;   /* j はパターンの末尾を指すようにする */
        printf("１：text[%d] = %c ⇔ pattern[%d] = %c\n", i, text[i], j, pattern[j]);
        count++;
        while(text[i] == pattern[j]){
            printf("２：text[%d] = %c ⇔ pattern[%d] = %c\n", i, text[i], j, pattern[j]);
            if(j == 0)
                return(i);    /* 探索は成功 */
            i--;
            j--;
            count++;
        }
        
        i += max(skip[text[i]], pat_len - j);      /* 不一致, パターンをずらす */
        //i += ((pat_len-1)-j)+skip[text[i+((pat_len-1)-j)]];
    }
    return(ERR);          /* 結局見つからなかった */
}



No.14310
Re:再：BM法について
投稿者---あかま(2004/05/30 14:04:53)		 


skipの生成が変。
skip[pattern[i]] = pat_len - i - 1;
に。

2つの/* 不一致, パターンをずらす */で比較回数を調べてます？
似たパターンの多い文字列だといくらか差が出ます。
char data[SIZE]={"AABCABBCABBCABBCABABCAB"};
char word[SIZE]={"ABCAB"};


No.14314
Re:再：BM法について
投稿者---Q児(2004/05/30 21:35:58)


>2つの/* 不一致, パターンをずらす */で比較回数を調べてます？
調べています。一応最悪の比較ケースも調べていましたので。
ご指定どおり訂正したら、ちゃんと一致しました。
あかまさんのおかげです。ありがとうございます。