基于散列函數的模式匹配算法

周慶勛

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

關鍵詞：散列函數;模式匹配;算法

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

0 引言

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

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

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

1 原理

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

該散列函數具有以下特點：

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位實現，對于給定的模式x，2m-1是一個常數。在一個模式匹配的過程中，若模式x在文本y中出現的位置為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，否則不匹配，繼續比較hash（x）和hash（y[i+1，i+m]），直到匹配或比較結束為止。

2 算法

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

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 結語

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

參考文獻：

[1]羅大光，郝玉潔，劉乃琦.一種非常快速的字符串匹配算法[J].電子科技大學學報，2005，34（06）：802-805.

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

[3]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，1996：79-80.endprint