基于散列函數(shù)的模式匹配算法

周慶勛

摘 要：本文簡要介紹了利用散列函數(shù)進行模式匹配的原理，散列函數(shù)的構(gòu)造，給出了基于散列函數(shù)的模式匹配算法。

關(guān)鍵詞：散列函數(shù);模式匹配;算法

DOI：10.16640/j.cnki.37-1222/t.2015.21.196

0 引言

模式匹配是數(shù)據(jù)結(jié)構(gòu)中字符串的一種基本運算，給定一個子串，要求在某個字符串中找出與該子串相同的所有子串，這就是模式匹配。

假設(shè)P是給定的子串，T是待查找的字符串，要求從T中找出與P相同的所有子串，這個問題成為模式匹配問題。P稱為模式，T稱為目標(biāo)。如果T中存在一個或多個模式為P的子串，就給出該子串在T中的位置，稱為匹配成功;否則匹配失敗。

模式匹配算法是文本處理領(lǐng)域中比較重要的算法，一個簡單、高效率的模式匹配算法對提高和模式匹配有關(guān)的軟件的效率有很大幫助，本文介紹一種基于散列函數(shù)的模式匹配算法，該算法簡單，易于理解且具有較高的效率。

1 原理

令模式記為x=x[0..m-1]，長度為m，文本串記為y=y[0..n-1]，長度為n。令算列函數(shù)：hash（x[0..m-1]=x[0]*2m-1+x[1]*2m-2+…+x[m-1]） mod q（式中q為系統(tǒng)最大整型值）

該散列函數(shù)具有以下特點：

1.1 易于計算

1.2 易于從hash（y[i，i+m-1]）計算hash（y[i+1，i+m]）

hash（y[i+1，i+m]）=（（ hash（y[i，i+m-1]）-y[i]*2m-1）*2+y[i+m]） mod q

為提高運算速度，乘以2的操作可通過左移1位實現(xiàn)，對于給定的模式x，2m-1是一個常數(shù)。在一個模式匹配的過程中，若模式x在文本y中出現(xiàn)的位置為i，則必定hash（x）=hash（y[i，i+m-1]），但要注意，hash（x）=hash（y[i，i+m-1]）時，x[0..m]和y[i，i+m-1]未必完全匹配。因此，模式匹配的過程就是hash（x）=hash（y[i，i+m-1]）（其中i=0，1，…，n-m）逐個比較的過程，若hash（x）和hash（y[i，i+m-1]），則將x[0..m]和y[i，i+m-1]逐字符比較，若完全相等，則模式匹配的位置為i，否則不匹配，繼續(xù)比較hash（x）和hash（y[i+1，i+m]），直到匹配或比較結(jié)束為止。

2 算法

下面給出用C語言函數(shù)描述的具體算法

int HashMatching（char *x，char *y， int n， int n）

{

int hash_x，hash_y，i，k，k1;

k=1;

for （i=1;i

hash_x=0;

hash_y=0;

for （i=0;i

{

Hash_x=（hash_x<<1）+x[i];

Hash_y=（hash_y<<1）+y[i];

}

for （i=0;i<=n-m;i++）

if （hash_y==hash_x）

{

k1=0;

while （k1

if （x[k1]==y[i+k1]）

k1=k1+1;

else

break;

if （k1==m） return i;

}

else

hash_y=（（hash_y-y[i]*k）<<1）+y[i+m];

return -1

}

3 結(jié)語

在預(yù)期情況下該算法的時間復(fù)雜度為O（n+m），在最壞情況下，該算法的時間復(fù)雜度為O（n*m）。盡管該算法在效率上不是最好，但算法簡單，易于理解，在對時間復(fù)雜度要求不是很苛刻的環(huán)境下，還是一個簡單高效的模式匹配算法。

參考文獻：

[1]羅大光，郝玉潔，劉乃琦.一種非?？焖俚淖址ヅ渌惴╗J].電子科技大學(xué)學(xué)報，2005，34（06）：802-805.

[2]嚴(yán)大治.字符串匹配算法比較與分析[J].計算機光盤軟件與應(yīng)用，2013（02）：138-140.

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1996：79-80.endprint