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

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

關鍵詞：多模式匹配；WM算法；藏文處理；藏文音節；音節結構特性

中圖分類號：TP391.1" " " 文獻標志碼：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

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

在多模式匹配領域，WM算法在實際場景當中的性能優異。WM算法是BM算法的一個變體。WM算法通過繼承和擴展BM算法的核心框架，采用字符塊來構建SHIFT表，以此替代傳統的壞字符表，實現快速跳轉。在匹配過程中，WM算法利用hash和prefix技術來計算前后綴的hash值，從而在眾多候選模式串中迅速識別出可能的匹配項?？傮w而言，WM算法是一個高效的文本搜索工具，尤其適用于需要同時搜索多個模式串的場景，其在文本處理、數據挖掘和信息檢索等多個領域展現出巨大的應用潛力。

盡管WM算法應用于ASCII字符集時表現出色，但當處理具有特定文本特性的語言，如藏文等音節文字時，其效果并不理想。由于藏文是一種音節文字，每個音節由一個或多個字符組成，這些字符在語義上是不可分割的。因此，傳統的基于字符的文本搜索算法在處理藏語文本時可能無法達到預期的效率和準確性。

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

1" 研究現狀

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

AC算法（Aho-Corasick算法）[4]是由Michael A. Aho和Margaret J. Corasick在1975年提出的，這是一種高效的模式匹配算法，能夠在線性時間內匹配一個有限集合中的所有模式串?；舅枷胧菢嫿ㄒ粋€確定性有限自動機（DFA），通過遍歷自動機，可以在文本中高效地查找所有模式串的出現位置。其是一個重要的模式匹配算法，對后續的模式匹配研究產生了深遠的影響。

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

另一方面，藏文模式匹配領域的研究相對較少。2022年春燕提出基于BM的單模式匹配算法[10]，2023年王蒙等提出基于藏文元音構件的字符串匹配算法[11]和基于AC自動機的多模式匹配算法[12]等，據筆者所知，基于WM算法的藏文多模式匹配算法，尚未出現相關研究成果。

2" WM算法介紹

2.1" 基本思想

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

WM算法首先對模式串集合進行預處理。

令藏文字符集為∑；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）。

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

SHIFT表：跳轉表，記錄每個字符塊在所有特征串中出現的最右端位置與該特征串尾的距離，將其映射為一個整數的h作為SHIFT表的索引，用于記錄文本串向右移動的長度。SHIFT表計算方式如下。

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

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

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

PREFIX表：前綴表，表中每一項鏈接一個具有相同前綴的模式串鏈表。

2.2 匹配過程

具體匹配過程如下。

1）計算模式串集合中最短模式串長m，m同時也為滑動窗口長度。

2）構建SHIFT表、HASH表和PREFIX表。

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

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

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

6）計算文本T當前滑動窗口字串的前綴的hash值，記為T_prefix。

7）對HASH[h]指向的每個模式串查詢PREFIX表，如果PREFIX[h]=T_prefix，轉8）。

8）將px指針指向PAT_POINT[p]，PAT_POINT是用來存儲模式串的起始位置，接著從模式串第一個字符與文本串進行完全匹配，如果匹配，報告匹配結果。執行i=i+1，轉3）。

3" 藏文結構分析

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

因為藏文書寫方式是從左至右橫行書寫，而由于音節不等長，雕版印刷的時候，經常會遇到行尾不能容納一個音節的情況，又由于藏文音節不能從中間拆分，即不能把后加字、重后加字，乃至前加字從字基分開。為此，藏文傳統上采用音節點填補空白的方法提示該段話語未結束。

4" TWM算法介紹

4.1" 基本思想

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

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

然后，建立3個表，SHIFT表、HASH表和PREFIX表。

SHIFT表計算方式如下。

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

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

4.2" 算法框架

1）計算模式串集合中最短模式串長m，m同時也為滑動窗口長度。

2）構建了音節級別的SHIFT表、HASH表和PREFIX表。

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

4）如果SHIFT[h]gt;0，則移動i+SHIFT[h]，轉3）;如果SHIFT[h]=0，說明i指向的后綴與某個模式串后綴相同，則轉5）。

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

6）計算文本T當前滑動窗口字串的前綴的hash值，記為T_prefix。

7）對HASH[h]指向的每個模式串查詢PREFIX表，如果PREFIX[h]=T_prefix，轉8）。

8）將px指針指向PAT_POINT[p]，PAT_POINT是用來存儲模式串的起始位置，從模式串第一個字符與文本串進行完全匹配，如果匹配，報告匹配結果。執行i=i+1，轉3）。

5" 實驗結果與分析

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

實驗一：固定模式串數量為1萬個，選取不同長度的文本串（單位為MB）進行測試，見表1，分別為TWM、QWM和WM所用時間，折線圖如圖2所示。

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

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

為了評估改進后的TWM算法的性能，將原WM算法、QWM算法與改進后的TWM算法進行比較。實驗中，TWM算法與QWM算法、WM算法皆完成匹配，且匹配準確。

由上面3組實驗可知，當固定模式串數量時，文本串長度越長，TWM算法運行時間比QWM算法和WM算法運行時間更快，時間性能較WM算法大約提升10%～20%，較QWM算法大約提升6%～15%。當固定文本串長度時，模式串數量越多，TWM算法所用時間比QWM算法、WM算法所用時間越少，時間性能較WM算法大約提升7%～10%，較QWM算法大約提升5%～7%。這是因為TWM算法在失配時，不再保守跳過WM算法的跳轉距離，而是依據藏文的字形結構特征，在保證匹配準確的前提下，跳過整個失配詞，較大地提高了算法的效率。

6" 結束語

本文在經典WM算法上，將藏文字形結構與WM算法結合，提出了基于藏文音節點的多模式匹配算法——TWM算法，通過實驗可知TWM算法在保證了匹配的準確性的前提下，算法更快，效率更高。因此，在一定程度上，TWM算法更加適合藏文環境。

參考文獻：

[1] 盧衛華.基于MPI的多模式串匹配WM算法的應用研究[D].哈爾濱：哈爾濱理工大學，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] 春燕.基于藏文音節特征的模式匹配算法的研究[J].計算機光盤軟件與應用，2014，17（15）：119-120.

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

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