今日は昨日の話題に続き、BM アルゴリズムについてお話しします。BM は KMP アルゴリズムの後継とも言える優れた文字列マッチングアルゴリズムです。BM は Boyer-Moore のアルゴリズムの傑作であり、そのため BM アルゴリズムと呼ばれています。KMP アルゴリズムと比べて効率が向上しており、BM アルゴリズムはマッチングする文字のセットと同じサイズの補助空間を必要とします。これは KMP よりも多くのスペースを浪費しますが、これが BM の特徴であり、異なる文字セットで使用することができます。2 つの文字セットの場合は、文字セットと同じサイズの補助空間を使用するだけで十分です。現在、C# などの多くの高級言語では BM およびその改良版のアルゴリズム（AC-BM アルゴリズム）が使用されています。KMP と比較して、2 つの中国語の文字の半角結果のマッチング時間が少なくなります。私は BM を好む傾向があります。スペースを浪費することはありますが、線形以下の消費に近い実装が可能です。これも客観的な事実です。
BM アルゴリズムには AC-BM アルゴリズムなど、多くの派生アルゴリズムがあります。これらは数学的な手法を使用して最適化されており、最良の場合には定数レベルでの向上が見られ、インデックスの利用効率が向上しています。次回は時間があるときに詳しく書きます。アルゴリズムの原理は、文字列の末尾からスキャンし、マッチングサフィックスと無効な文字の置換原則を利用しています。全体的な効率はかなり向上しています。以下にアルゴリズムを示します。具体的なアルゴリズムのコメントは追加されています。わからない場合は、コメントを残すか、私に連絡してください。時間があればできるだけ解答します。
デバッグは歓迎です。TC 環境では、時間がなくてデバッグできませんが、修正すれば問題ないはずです。BM 文字列マッチングアルゴリズム：
/*BM 文字列マッチングアルゴリズム */
/*code by CG lidaren.com
* ACM yctc
*2008 12 20
*/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define LEN 256
/*LEN は文字セットのサイズです。ASCII エンコーディングでは 1 バイトで文字を表します。UNICODE の場合は別途考慮する必要がありますが、BM アルゴリズムの利点です。*/
/*BM () BM アルゴリズムの基本機能関数
* 入力:
* char *s マッチング文字列
* char *p パターン文字列
* int index マッチング開始インデックス
* int post [] 補助配列
* 戻り値:
* int 次のマッチング開始インデックス。マッチング失敗時は - 1 を返す
*/
int BM(char *s, char *p, int index, int post[]) {
int len = strlen(s);
int i,j, next;
i = strlen (p)-1;/* 文字列の長さから 1 を引く */
j = index+strlen (p)-1;/* 最初の BM () 呼び出し時、index = 0 なので、以下の for ループはパターン文字列の末尾から比較を開始するため、マッチング文字列の初期比較位置はパターン文字列の長さだけ進める必要があります。*/
for(; i>=0; i--, j--) {
if (s [j] != p [i]){/* 最初の文字のマッチング */
break;
}
}/*for*/
if (i<0) /* マッチング完了？*/
return 0; /* マッチング成功 */
else if(post[s[j]]>0)
/* マッチング失敗時、マッチング文字列の現在位置の文字がパターン文字列に出現するかどうかをチェックする */
next = index + i - post[s[j]];
/*index は現在のマッチング文字列のオフセット、i はパターン文字列の残りの比較文字列の数、post [s [j]] は最初のマッチングしない文字の位置です。
* 次回の比較はマッチング文字列の中で s [j] が出現する位置から開始します。*/
else next = index + 1;
if(next > LEN-strlen(p))
return -1; /* マッチング失敗、次のマッチングができない */
else
return next; /* マッチング失敗、次のマッチングが必要 */
}/*BM*/
/* テスト、マッチング文字列とパターン文字列はすべて小文字で使用します。*/
int main()
{
int post [LEN]={0}; /* 補助配列 = 文字セットのサイズ */
char \*src="aaaabbbaababababbabb";/\*テスト文字列\*/
char \*patten="aabbabb";
int i, next, index=-2, pos=0;/\*インデックスフラグの初期化\*/
for(i=0; i
index = BM(src, patten, 0, post);/\*最初のマッチング、0の位置から開始し、NEXTを取得\*/
while(!(index == -1 || index == 0)) /\*マッチング成功するまでループ\*/
{
next = index;
index = BM(src, patten, next, post);/\*次のBMマッチング\*/
}/\*while\*/
if(index == -1){ /\*失敗\*/
printf("マッチング失敗n");
}
if(index == 0){ /\*成功\*/
printf("インデックスは: %d.n", next);
}
return 0;
}/*main*/
インターネットで BM アルゴリズムに関する情報を検索しました。詳細はこちらを参照してください。