基于藏文音節(jié)特征的WM多模式匹配算法·

摘" 要：近年來，隨著互聯(lián)網(wǎng)特別是移動(dòng)互聯(lián)網(wǎng)在西藏的普及和發(fā)展，對涉藏網(wǎng)絡(luò)輿情的治理也變得越發(fā)重要，其中最基本的方式便是敏感詞檢測。而多模式（字符串）匹配算法正是進(jìn)行敏感詞檢測的核心技術(shù)手段。作為一種高效的多模式匹配算法，WM（Wu-Manber）算法以其良好的實(shí)際表現(xiàn)，在許多場景都得到廣泛應(yīng)用，該算法使用字符塊跳轉(zhuǎn)技術(shù)來加速匹配過程。然而藏文作為一種音節(jié)文字，其文本特性與中英文等文字存在顯著差異，若直接將WM算法用于藏文多模式匹配，效果并不理想。針對這一問題，該文充分利用藏文的音節(jié)結(jié)構(gòu)特性，對WM算法進(jìn)行改進(jìn)和優(yōu)化，提出適用于藏文的多模式匹配算法——TWM（Tibetan Wu-Manber）。實(shí)驗(yàn)結(jié)果表明，TWM算法在藏文多模式匹配任務(wù)中，相比原始WM算法在效率和準(zhǔn)確性上都有顯著提高。

關(guān)鍵詞：多模式匹配；WM算法；藏文處理；藏文音節(jié)；音節(jié)結(jié)構(gòu)特性

中圖分類號：TP391.1" " " 文獻(xiàn)標(biāo)志碼：A" " " " " 文章編號：2095-2945（2025）08-0001-05

Abstract： In recent years， with the popularization and development of the Internet， especially the mobile Internet， in Xizang， the governance of Tibetan-related Internet public opinion has become increasingly important. The most basic method is sensitive word detection. The multi-pattern （string） matching algorithm is the core technical means for sensitive word detection. As an efficient multi-pattern matching algorithm， the WM （Wu-Manber） algorithm is widely used in many scenarios because of its good practical performance. The algorithm uses character block jump technology to speed up the matching process. However， as a syllable script， Tibetan has significant differences in text characteristics from Chinese and English characters. If the WM algorithm is directly used for Tibetan multi-pattern matching， the effect is not ideal. To solve this problem， this paper makes full use of the syllable structure characteristics of Tibetan， improves and optimizes the WM algorithm， and proposes a multi-pattern matching algorithm for Tibetan-TWM （Tibetan Wu-Manber）. Experimental results show that the TWM algorithm is significantly improved in efficiency and accuracy compared to the original WM algorithm in Tibetan multi-pattern matching tasks.

Keywords： multi-pattern matching; WM algorithm; Tibetan processing; Tibetan syllable; syllable structure characteristics

習(xí)近平總書記強(qiáng)調(diào)，沒有網(wǎng)絡(luò)安全就沒有國家安全，就沒有經(jīng)濟(jì)社會穩(wěn)定運(yùn)行，廣大人民群眾利益也難以得到保障。網(wǎng)絡(luò)安全與政治安全、經(jīng)濟(jì)安全、文化安全、社會安全和軍事安全等領(lǐng)域相互交融、相互影響，已成為我國面臨的最復(fù)雜、最現(xiàn)實(shí)、最嚴(yán)峻的非傳統(tǒng)安全問題之一，在國家安全體系中的基礎(chǔ)性、戰(zhàn)略性、全局性地位更加凸顯。對于西藏而言，網(wǎng)絡(luò)安全中的網(wǎng)絡(luò)輿情方面，可能涉及民族、宗教或人權(quán)等敏感話題，對民族團(tuán)結(jié)、社會穩(wěn)定、政權(quán)安全和國家形象有著重要影響。而在涉藏網(wǎng)絡(luò)輿情分析中，通常需要識別和處理大量的文本信息，包括新聞報(bào)道、社交媒體帖子、論壇討論等，以了解公眾對涉藏話題的情緒、態(tài)度和意見，在這一過程中識別和監(jiān)控敏感詞是至關(guān)重要的。模式匹配算法可以用來快速而準(zhǔn)確地識別文本中的特定詞匯或短語，因此將成為涉藏網(wǎng)絡(luò)輿情治理的核心技術(shù)手段之一。

在多模式匹配領(lǐng)域，WM算法在實(shí)際場景當(dāng)中的性能優(yōu)異。WM算法是BM算法的一個(gè)變體。WM算法通過繼承和擴(kuò)展BM算法的核心框架，采用字符塊來構(gòu)建SHIFT表，以此替代傳統(tǒng)的壞字符表，實(shí)現(xiàn)快速跳轉(zhuǎn)。在匹配過程中，WM算法利用hash和prefix技術(shù)來計(jì)算前后綴的hash值，從而在眾多候選模式串中迅速識別出可能的匹配項(xiàng)。總體而言，WM算法是一個(gè)高效的文本搜索工具，尤其適用于需要同時(shí)搜索多個(gè)模式串的場景，其在文本處理、數(shù)據(jù)挖掘和信息檢索等多個(gè)領(lǐng)域展現(xiàn)出巨大的應(yīng)用潛力。

盡管WM算法應(yīng)用于ASCII字符集時(shí)表現(xiàn)出色，但當(dāng)處理具有特定文本特性的語言，如藏文等音節(jié)文字時(shí)，其效果并不理想。由于藏文是一種音節(jié)文字，每個(gè)音節(jié)由一個(gè)或多個(gè)字符組成，這些字符在語義上是不可分割的。因此，傳統(tǒng)的基于字符的文本搜索算法在處理藏語文本時(shí)可能無法達(dá)到預(yù)期的效率和準(zhǔn)確性。

為了克服這一問題，本文提出了一種基于藏文音節(jié)節(jié)點(diǎn)的改進(jìn)WM算法。改進(jìn)后的WM算法充分利用了藏文音節(jié)的特性，將音節(jié)作為匹配的基本單元，并構(gòu)建了音節(jié)級別的SHIFT表、HASH表和PREFIX表。通過這種方法，算法能夠更精準(zhǔn)地確定匹配位置和跳轉(zhuǎn)距離，顯著提升了藏文匹配的效率和準(zhǔn)確性。

1" 研究現(xiàn)狀

模式匹配算法在文本檢索、圖像識別、信號和語音處理及生物信息學(xué)等領(lǐng)域有著廣泛應(yīng)用，是解決各種問題的重要工具。比如在基因測序中模式精確匹配與近似比對算法是很關(guān)鍵的2個(gè)組成部分[1]，在病毒檢測技術(shù)[2]中，可以通過提高模式匹配的速度，來提高病毒檢測的速度，進(jìn)而提高系統(tǒng)的安全性[3]。主要的模式匹配算法分為基于字符比較的算法、基于哈希的算法、基于自動(dòng)機(jī)的算法、基于位并行的算法以及混合算法。

AC算法（Aho-Corasick算法）[4]是由Michael A. Aho和Margaret J. Corasick在1975年提出的，這是一種高效的模式匹配算法，能夠在線性時(shí)間內(nèi)匹配一個(gè)有限集合中的所有模式串?；舅枷胧菢?gòu)建一個(gè)確定性有限自動(dòng)機(jī)（DFA），通過遍歷自動(dòng)機(jī)，可以在文本中高效地查找所有模式串的出現(xiàn)位置。其是一個(gè)重要的模式匹配算法，對后續(xù)的模式匹配研究產(chǎn)生了深遠(yuǎn)的影響。

KMP算法[5]是由Donald E. Knuth、James H. Morris Jr.和Vaughan R. Pratt在1977年提出的，其是通過預(yù)處理模式串來避免回溯，從而能夠在線性時(shí)間內(nèi)，從主串中查找模式串的出現(xiàn)位置。同時(shí)，在1977年，Boyer和Moore提出了Boyer-Moore算法[6]，匹配過程中，該算法使用“壞字符”規(guī)則和“好后綴”規(guī)則，來跳過盡可能多的字符，減少比較次數(shù)，大幅提高了匹配效率。Wu-Manber算法[7]是由Sun Wu和Udi Manber在1994年提出的一種多模式匹配的算法。其通過結(jié)合Boyer-Moore算法和Aho-Corasick算法的設(shè)計(jì)思想，實(shí)現(xiàn)了對多個(gè)模式串的同時(shí)匹配。WM算法自提出以來，在多模式匹配領(lǐng)域得到了廣泛應(yīng)用，是處理大規(guī)模模式串匹配任務(wù)的重要算法之一。之后，陸續(xù)有學(xué)者提出了基于WM算法的改進(jìn)算法，2007年由馬偉華等人提出了改進(jìn)算法 QWM（Quick Wu-Manber）算法[8]。結(jié)合了QS算法的思想，使其在處理短模式和大規(guī)模數(shù)據(jù)方面比Wu-Manber算法更優(yōu)。2011年，劉衛(wèi)國、胡勇剛提出雙哈希搜索Wu-Manber算法（DHSWM）[9]，該算法通過構(gòu)建雙哈希表、采用最短后綴優(yōu)先等方法，提高了匹配速度和效率。

另一方面，藏文模式匹配領(lǐng)域的研究相對較少。2022年春燕提出基于BM的單模式匹配算法[10]，2023年王蒙等提出基于藏文元音構(gòu)件的字符串匹配算法[11]和基于AC自動(dòng)機(jī)的多模式匹配算法[12]等，據(jù)筆者所知，基于WM算法的藏文多模式匹配算法，尚未出現(xiàn)相關(guān)研究成果。

2" WM算法介紹

2.1" 基本思想

WM算法的主要特點(diǎn)是能夠高效地處理大量模式串，適用于多模式匹配的場景，如搜索引擎中的查詢詞匹配。WM算法是對BM算法的延伸繼承，使用了BM算法的核心框架，利用字符塊來計(jì)算SHIFT表（取代壞字符表）進(jìn)行跳轉(zhuǎn)。SHIFT表用于確定模式串在文本串中不匹配時(shí)可以滑動(dòng)的最大距離。在匹配過程中，WM算法能夠利用移位表來減少不必要的字符比較，從而提高匹配效率。

WM算法首先對模式串集合進(jìn)行預(yù)處理。

令藏文字符集為∑；B為字符塊長度；h為字符塊的hash值；模式串集合P={P1，P2，…，Pi，…，Pk}，Pi=pi1pi2…pij…pis，pij∈∑（1≤j≤s），令Pi長度為Li，其中最短模式串長定義為m；文本串t=t1t2…tj…tn，tj∈∑（1≤j≤n）。

預(yù)處理階段首先將遍歷集合中的所有模式串，計(jì)算最短模式串長m，并且只考慮每個(gè)模式串Pi的前m個(gè)字符，作為Pi的“特征串”，而后根據(jù)這些特征串構(gòu)建3個(gè)表，SHIFT表、HASH表和PREFIX表。

SHIFT表：跳轉(zhuǎn)表，記錄每個(gè)字符塊在所有特征串中出現(xiàn)的最右端位置與該特征串尾的距離，將其映射為一個(gè)整數(shù)的h作為SHIFT表的索引，用于記錄文本串向右移動(dòng)的長度。SHIFT表計(jì)算方式如下。

1）如果滑動(dòng)窗口中的字符塊在任何特征串中都沒有出現(xiàn)，則SHIFT[h]=m-B+1。

2）如果窗口中的字符塊出現(xiàn)在某些特征串中，找到其在任何模式中的最右出現(xiàn)位置q，則SHIFT[h]=m-q。

HASH表：哈希表，表中每一項(xiàng)鏈接一個(gè)模式串鏈表，鏈接的所有模式串的特征串，其后綴擁有一樣的哈希值，HASH表與SHIFT表大小相同，并使用相同哈希值索引。

PREFIX表：前綴表，表中每一項(xiàng)鏈接一個(gè)具有相同前綴的模式串鏈表。

2.2 匹配過程

具體匹配過程如下。

1）計(jì)算模式串集合中最短模式串長m，m同時(shí)也為滑動(dòng)窗口長度。

2）構(gòu)建SHIFT表、HASH表和PREFIX表。

3）i指向文本T的滑動(dòng)窗口為2的后綴，如果igt;n，算法終止；否則，計(jì)算i指向的字符塊的hash值h。

4）如果SHIFT[h]gt;0，則滑動(dòng)窗口移動(dòng)i+SHIFT[h]，轉(zhuǎn)3）;如果SHIFT[h]=0，說明i指向的后綴與某個(gè)模式串后綴相同，則轉(zhuǎn)5）。

5）查詢HASH表，HASH[h]指向可能與文本T當(dāng)前滑動(dòng)窗口字串所匹配的模式串集合。

6）計(jì)算文本T當(dāng)前滑動(dòng)窗口字串的前綴的hash值，記為T_prefix。

7）對HASH[h]指向的每個(gè)模式串查詢PREFIX表，如果PREFIX[h]=T_prefix，轉(zhuǎn)8）。

8）將px指針指向PAT_POINT[p]，PAT_POINT是用來存儲模式串的起始位置，接著從模式串第一個(gè)字符與文本串進(jìn)行完全匹配，如果匹配，報(bào)告匹配結(jié)果。執(zhí)行i=i+1，轉(zhuǎn)3）。

3" 藏文結(jié)構(gòu)分析

藏文是一種拼音文字，屬輔音字母文字型，分輔音字母、元音符號2個(gè)部分。其中有30個(gè)輔音字母，4個(gè)元音符號，以及5個(gè)反寫字母（用以拼外來語）。藏文字形結(jié)構(gòu)均以一個(gè)字母為核心，其余字母均以此為基礎(chǔ)前后附加和上下疊寫，組合成一個(gè)完整的字表結(jié)構(gòu)。通常藏文字形結(jié)構(gòu)最少為一個(gè)輔音字母，即單獨(dú)由一個(gè)基字構(gòu)成；最多由6個(gè)輔音字母構(gòu)成，元音符號則加在輔音結(jié)構(gòu)的上、下、正中。核心字母叫“基字”，其余字母的稱謂均根據(jù)加在基字的部位而得名。即加在基字前的字母叫“前加字”，加在基字上的字母叫“上加字”，加在基字下面的字母叫“下加字”，加在基字后面的字母叫“后加字”，后加字之后再加字母叫“再后加字”或“重后加字”。如圖1所示。

因?yàn)椴匚臅鴮懛绞绞菑淖笾劣覚M行書寫，而由于音節(jié)不等長，雕版印刷的時(shí)候，經(jīng)常會遇到行尾不能容納一個(gè)音節(jié)的情況，又由于藏文音節(jié)不能從中間拆分，即不能把后加字、重后加字，乃至前加字從字基分開。為此，藏文傳統(tǒng)上采用音節(jié)點(diǎn)填補(bǔ)空白的方法提示該段話語未結(jié)束。

4" TWM算法介紹

4.1" 基本思想

由于傳統(tǒng)的WM算法在匹配藏文時(shí)，計(jì)算機(jī)會將藏文文本分解成基本構(gòu)件，這些構(gòu)件可以是單個(gè)的字母、附加符號或者組合字符，所以若有任一構(gòu)件不匹配，則整個(gè)由音節(jié)點(diǎn)分割的藏文詞語均不匹配，因此傳統(tǒng)的WM算法在匹配時(shí)會有許多冗余操作，使得匹配時(shí)間增長，匹配效率低下。因而本文基于音節(jié)點(diǎn)的特性，對WM算法進(jìn)行改進(jìn)，顯著提升了匹配效率。

首先，計(jì)算模式的最小長度，稱之為m，并且只考慮每個(gè)模式串的前m個(gè)字符。

然后，建立3個(gè)表，SHIFT表、HASH表和PREFIX表。

SHIFT表計(jì)算方式如下。

1）如果窗口中的字符塊在任何模式串中都沒有出現(xiàn)，倘若字符塊中前一個(gè)字符為音節(jié)點(diǎn)，SHIFT[h]=1；若后一個(gè)字符為音節(jié)點(diǎn)，SHIFT[h]=m；若均不為音節(jié)點(diǎn)，SHIFT[h]=X+m（X為失配字符到音節(jié)點(diǎn)的距離）。

2）如果窗口中的字符塊出現(xiàn)在某些模式串中，找到其在任何模式中的最右出現(xiàn)位置q，則SHIFT[h]=m-q。

4.2" 算法框架

1）計(jì)算模式串集合中最短模式串長m，m同時(shí)也為滑動(dòng)窗口長度。

2）構(gòu)建了音節(jié)級別的SHIFT表、HASH表和PREFIX表。

3）i指向文本T的滑動(dòng)窗口后綴，如果igt;n，算法終止，否則，計(jì)算i指向的字符塊的hash值h。

4）如果SHIFT[h]gt;0，則移動(dòng)i+SHIFT[h]，轉(zhuǎn)3）;如果SHIFT[h]=0，說明i指向的后綴與某個(gè)模式串后綴相同，則轉(zhuǎn)5）。

5）查詢HASH表，HASH[h]指向可能與文本T當(dāng)前滑動(dòng)窗口字串所匹配的模式串集合。

6）計(jì)算文本T當(dāng)前滑動(dòng)窗口字串的前綴的hash值，記為T_prefix。

7）對HASH[h]指向的每個(gè)模式串查詢PREFIX表，如果PREFIX[h]=T_prefix，轉(zhuǎn)8）。

8）將px指針指向PAT_POINT[p]，PAT_POINT是用來存儲模式串的起始位置，從模式串第一個(gè)字符與文本串進(jìn)行完全匹配，如果匹配，報(bào)告匹配結(jié)果。執(zhí)行i=i+1，轉(zhuǎn)3）。

5" 實(shí)驗(yàn)結(jié)果與分析

通過實(shí)驗(yàn)對TWM算法和QWM算法以及WM算法進(jìn)行實(shí)際測試，算法使用JAVA語言實(shí)現(xiàn)。測試文本為真實(shí)的藏文電子書，模式串為復(fù)旦大學(xué)自然語言處理實(shí)驗(yàn)室發(fā)布的藏語新聞數(shù)據(jù)集中隨機(jī)生成藏文詞以及自建的藏文敏感詞庫，模式串最短為3字符，最長為145字符。

實(shí)驗(yàn)一：固定模式串?dāng)?shù)量為1萬個(gè)，選取不同長度的文本串（單位為MB）進(jìn)行測試，見表1，分別為TWM、QWM和WM所用時(shí)間，折線圖如圖2所示。

實(shí)驗(yàn)二：固定文本串長度為128 MB，選取不同數(shù)量的模式串（單位為萬個(gè)）進(jìn)行測試，見表2，分別為TWM、QWM和WM所用時(shí)間，折線圖如圖3所示。

實(shí)驗(yàn)三：為了驗(yàn)證TWM算法對于真實(shí)敏感詞的檢測效果，模式集采用包含2 000個(gè)真實(shí)的敏感詞的集合，選取不同長度的文本串（單位為MB）進(jìn)行測試，見表3，分別為TWM、QWM和WM所用時(shí)間，折線圖如圖4所示。

為了評估改進(jìn)后的TWM算法的性能，將原WM算法、QWM算法與改進(jìn)后的TWM算法進(jìn)行比較。實(shí)驗(yàn)中，TWM算法與QWM算法、WM算法皆完成匹配，且匹配準(zhǔn)確。

由上面3組實(shí)驗(yàn)可知，當(dāng)固定模式串?dāng)?shù)量時(shí)，文本串長度越長，TWM算法運(yùn)行時(shí)間比QWM算法和WM算法運(yùn)行時(shí)間更快，時(shí)間性能較WM算法大約提升10%～20%，較QWM算法大約提升6%～15%。當(dāng)固定文本串長度時(shí)，模式串?dāng)?shù)量越多，TWM算法所用時(shí)間比QWM算法、WM算法所用時(shí)間越少，時(shí)間性能較WM算法大約提升7%～10%，較QWM算法大約提升5%～7%。這是因?yàn)門WM算法在失配時(shí)，不再保守跳過WM算法的跳轉(zhuǎn)距離，而是依據(jù)藏文的字形結(jié)構(gòu)特征，在保證匹配準(zhǔn)確的前提下，跳過整個(gè)失配詞，較大地提高了算法的效率。

6" 結(jié)束語

本文在經(jīng)典WM算法上，將藏文字形結(jié)構(gòu)與WM算法結(jié)合，提出了基于藏文音節(jié)點(diǎn)的多模式匹配算法——TWM算法，通過實(shí)驗(yàn)可知TWM算法在保證了匹配的準(zhǔn)確性的前提下，算法更快，效率更高。因此，在一定程度上，TWM算法更加適合藏文環(huán)境。

參考文獻(xiàn)：

[1] 盧衛(wèi)華.基于MPI的多模式串匹配WM算法的應(yīng)用研究[D].哈爾濱：哈爾濱理工大學(xué)，2023.

[2] LE D， NGUYEN， DAC-NHUONG L， et al. A new multiple-pattern matching algorithm for the network intrusion detection system[J].International Journal of Engineering and Technology，2016： 94.

[3] SONG T， ZHANG W， WANG D， et al. A memory efficient multiple pattern matching architecture for network security[C]//INFOCOM 2008. The 27th Conference on Computer Communications. IEEE. IEEE， 2008： 166-170.

[4] AHO M A， CORASICK M J. Efficient string matching： An aid to bibliographic search[J]. Communications of the ACM，1975，18（6）：333-340.

[5] KNUTH D E， MORRIS J H， PRATT V R. Fast pattern matching in strings[J]. SIAM Journal on Computing，1997，6（2）：323-350.

[6] BOYER R S， MOORE J S. A fast string searching algorithm[J]. Communications of the ACM， 1977，20（10）： 762-772.

[7] WU S， MANBER U. A fast algorithm for multi-pattern searching[R]. Department of Computer Science， University of Arizona， Technical Report TR-94-17，1994.

[8] CHEN J， CAI S， ZHU L， et al. An improved string-searching algorithm and its application in component security testing[J]. Tsinghua Science and Technology， 2016， 21（4）： 281-294.

[9] ZHEN C， DI W. Improving Wu-Manber： A multi-pattern matching algorithm[C]//2008 IEEE International Conference on Networking， Sensing and Control， 2008： 812-817.

[10] 春燕.基于藏文音節(jié)特征的模式匹配算法的研究[J].計(jì)算機(jī)光盤軟件與應(yīng)用，2014，17（15）：119-120.

[11] 王蒙，彭展，楊涵刈.基于藏文元音構(gòu)件的字符串匹配算法[J].電子技術(shù)與軟件工程，2022（18）：137-142.

[12] 王蒙，彭展.一種基于AC自動(dòng)機(jī)的藏文多模式匹配算法[J].電子技術(shù)與軟件工程，2023（1）：143-148.