適用于PDF文本內容的高效模式匹配算法*

朱玲玉，王旌舟，陳慶春

0 引 言

模式匹配在網絡入侵檢測、生物序列數據庫比對（DNA）、信息檢索、生物計量學等領域得到了廣泛應用。模式匹配按同時匹配模式串的個數，分為單模式匹配和多模式匹配，其中KMP[1]、BM[2]為經典單模式匹配，AC[3]、WM[4]算法為經典多模式匹配。每種模式匹配算法都有其最優、最壞匹配復雜度，針對不同模式串的類型，其算法各有優點。

隨著信息時代和大數據時代的快速發展，網絡安全監管快速興起，網絡空間安全成為了熱點。PDF是Portable Document Format（便攜文件格式）的縮寫，是全世界電子版文檔分發的公開實用標準。作為一種通用文件格式，PDF能夠保存任何源文檔的所有字體、格式、顏色和圖形，而不關心創建該文檔使用的應用程序和平臺。網絡中越來越多的文件開始傾向于采用PDF這一主流的文本保存格式。隨著PDF文檔的廣泛使用，PDF文件內容的保密性和安全性問題日益凸顯。本文結合PDF文件格式及其編碼規則，分析研究BM、QS[5]算法，并分析了一類適用于PDF文件的高效匹配算法，以支持涉密PDF文件內容的高效管控應用。

1 PDF文件格式及編碼規則

PDF文檔是8 bit字節序，以二進制流保存。深入理解PDF文件的格式，需從其對象、文件結構（邏輯結構）、文檔結構（物理結構）、內容流和編碼4方面理解[6]。

PDF文件實質由一系列對象構成，這些對象分別有8種基本數據類型，即邏輯對象、名字對象、字典對象、字符串對象、流對象、數組對象、數值對象和空對象。這些基本數據類型的對象是直接對象，可被標識，以便作為間接對象被其他對象引用。文件結構（物理結構）由文件頭（head）、文件體（body）、交叉引用表（xref）和文件尾（trailer）構成。PDF文件具有層次化結構，其根部為文檔目錄字典對象，根據其引用的對象獲得其他對象內容，進而找到文本內容。例如，可以從文件尾部找到根/root，找到其引用對象的catalog，再通過字典目錄中的信息/pages找到頁面對象pages，依次找到page對象，最后通過/content找到其文本內容流和編碼信息。

PDF文本內容在操作符TJ/Tj的前面，其文本內容以16進制表示，一般情況表示在一對尖括號里面，如＜2B0955853D96＞TJ，其編碼一般有unicode編碼、GBK編碼和CID編碼[7]。大多數PDF文件的文本內容都存在一個映射關系，如GBK編碼的，TJ前面16進制的文本內容可通過cmap文件（GBK編碼映射）映射到真正文本的內容。由于中文字符是寬字符（多字節字符）且數量巨大，為減小PDF文件的大小，中文漢字使用CID編碼，即PDF文件的文本內容不是Unicode編碼。為了得到能夠顯示的Unicode編碼，需要一個從CID編碼到Unicode編碼的轉換過程。無論怎么映射，其文本內容顯示基本就是以16進制表示的，4個字符為一個字。進行敏感信息（關鍵字）查找時，也是從TJ前面的內容出發。以下首先概要介紹一些經典的模式匹配算法，然后在此基礎上，提出一種適合PDF文本內容匹配的高效算法。

2 經典單模式匹配算法

2.1 模式匹配

迄今為止，國內外學者在KMP、BM等經典匹配算法的基礎上，提出了不少改進的單模式匹配算法，如BMH、QS等。此外，存在大量利用移位表、匹配方向的改進算法。這里介紹經典的單模式匹配算法，如基于后綴比較的BM算法和基于下一字符的QS算法。

所謂模式匹配即給定字符集ξ，給定文本串T，長度為n，有：

給定模式串P，長度為m，有：

在文本串T中匹配到給定的字符串P，若字符串P出現在文本串T中，即：

則匹配成功且匹配的位置為i。

2.2 BM算法

BM算法是Robert S. Boyer和J.Strother Moore于1977年共同提出的一種亞線性的單模式匹配算法。實際應用中，BM算法相對于其他算法，被普遍認為是一類高效算法。它的基本思想：基于后綴匹配，從右至左進行匹配，通過已獲得的信息（移位表）跳過文本串中的某些字符，實現最大程度的移位。

BM算法分為2部分——預處理和匹配過程。預處理階段利用模式串信息構建移位表，即BM壞字符表（bmBc）和BM好后綴（bmGs）。這是該算法的核心。

2.2.1 預處理過程

預處理過程建立壞字符表、后綴表。壞字符是指從左至右進行匹配時，一旦失配，該字符被稱為壞字符。好后綴是指模式串左邊出現了模式串右側的字符串。以模式串“GCAGAGAG為例”構建壞字符表和好后綴表，結果如表1、表2所示。

壞字符規則存在2種情況：一是失配字符出現在模式串中，令失配字符對齊模式串中靠右的字符，如圖1所示；二是失配字符未出現在模式串中，無論怎么移位，該字符都會產生失配，即移位至失配字符的下一位，如圖2所示。所以，模式例壞字符表計算結果如表1所示。

圖1 有失配字符壞字符移位

圖2 無失配字符壞字符移位

表1 BM壞字符表

好后綴的計算規則也存在2種情況：一是模式串中左側存在已匹配全部字符，移位對齊已匹配的字符且前一字符不等于失配字符，如圖3所示；二是左側存在已匹配的部分字符（后綴），移位與之對齊，如圖4所示。所以，模式例的好后綴表的計算結果如表2所示。

圖3 無失配字符好后綴移位

圖4 有失配字符發好后綴移位

表2 BM好后綴表

2.2.2 匹配過程

建立好后綴壞字符表后，從右至左開始匹配。一旦發生失配，比較好后綴和壞字符表，取最大值進行移位，進行下一次匹配，而對已匹配成功的返回其位置。

該算法在文本串長度為n、定位長度為m的模式串中，其預處理階段的時間、匹配過程、最優時間復雜度分別為 O(m+σ)、O(mn)、O(m/n)。

2.3 QS算法

QS算法是Daniel M.Sunday提出的一種簡單快速單模式匹配算法，也稱Sunday算法。Sunday通過對模式串掃描的順序不同給出了三種算法，其中有QS算法、MS算法和OM算法。MS算法的掃描順序為移位的大小降序，OM算法的掃描順序取決于其字符出現頻率的大小。

QS算法實質是BM算法的一種簡化版本，其實現更簡單，僅利用了BM算法中的壞字符規則。基本思想：在進行字符串匹配時，無論匹配方向從左至右還是從右至左，無需考慮匹配順序，由于發現不匹配會至少移動一位，因此須考慮該匹配窗口的下一字符是否出現在模式串中，利用BM算法的壞字符規則計算其移位后再進行匹配。因此，可利用下一字符來實現最大跳躍，使之最大位移為m+1。

2.3.1 預處理過程

預處理過程實質是利用BM壞字符規則建立移位表。移位表建立也從字符是否在模式串及其位置考慮。若模式串中并未出現下一字符，則移位跳過該字符，再在匹配窗口進行匹配；若在，移位與之對齊。移位計算公式為：

以BM算法的模式串為例，其移位表qsBc如表3所示。

表3 QS下一字符移位表

2.3.2 匹配過程

建立好下一字符移位表后，無需像KMP、BM算法按順序進行字符比較，即一旦發生不匹配，考慮該匹配窗口的下一字符，判斷是否存在于模式串中，移位后繼續進行匹配。

該算法在文本串長度為n、定位長度為m的模式串中，其預處理階段的時間、空間、匹配過程、最優時間復雜度分別為 O(m+σ)、O(σ)、O(mn)、O(n/(m+1))。該算法的問題在于，當出現下一字符移位距離小于失配字符的移位距離時，將導致QS算法效率大打折扣。

一般情況下，QS算法適用于短模式和大字符集的情形下，實現簡單。

3 改進算法

3.1 算法思想

基于BM算法中的壞字符移位規則思想和QS算法的下一字符思想，結合PDF文件文本內容的編碼特點，提出了一種適用于PDF文檔內容匹配的快速算法。

該算法匹配順序和BM算法一樣，采納后綴匹配，即在模式匹配窗口中，從右自左進行字符的比較。若模式串已經和文本串成功匹配，將利用QS的下一字符思想，比較該匹配窗口的下4個字符和模式串的前4個字符。一旦發生不匹配，必然會發生移位，且至少移動4位（PDF文本內容的一個字為4個字符）。因此，利用QS算法的下一字符思想，該匹配窗口的下4個字符可以考慮是否出現在模式串相應位置，然后利用BM算法的壞字符計算規則得到移位表進行移位，使最大移位為m+4，提高匹配的效率。

3.2 算法預處理過程及匹配過程

該算法包含預處理過程和模式匹配過程。預處理階段，需要計算壞字符移位函數Skip。移位函數計算和BM壞字符表的計算有一定區別。改進算法中無需計算模式串中的每一字符的移位。由于是從右至左開始匹配，不匹配移位至少4位。由于是大字符集，所以考慮每一字的最高位字符的移位表。移位表計算如下：

匹配過程如下。從右至左開始匹配，一旦不匹配，立刻利用該匹配窗口的下4個字符，判斷其最高位的字符是否出現在模式串中的相應位置上。如果沒有，說明這4個字符也不可能與模式串匹配成功，則直接移位m+4；否則，移位模式串到其對應處。

3.3 算法實例

以PDF文檔為例，考慮如下的文本串：

模式串：5339 914d。

首先進行預處理，如表4所示。

表4 Skip表

第一次：4e00 79cd 5feb 901f 7684 5355 6a21 5f0f 5339 914d 7b97 6cd5 5339 914d

T[6]≠P[6]，則考慮匹配窗口的下4個字符的高位b。字符b未在模式串相應的高位出現，此時T[11]≠P[3]≠P[7]，移位12位。

第二次：4e00 79cd 5feb 901f 7684 5355 6a21 5f0f 5339 914d 7b97 6cd5 5339 914d

T[19]≠P[7]，則考慮匹配窗口的下4個字符的高位5。字符5未在模式串相應的高位出現，此時T[23]≠P[3]≠P[7]，移位12位。

第三次：4e00 79cd 5feb 901f 7684 5355 6a21 5f0f 5339 914d 7b97 6cd5 5339 914d

T[31]≠P[7]，則考慮匹配窗口的下4個字符的高位9。字符9在模式串相應的高位出現，T[35]≠P[3]，移位8位。

第四次：4e00 79cd 5feb 901f 7684 5355 6a21 5f0f 5339 914d 7b97 6cd5 5339 914d

發現匹配，考慮匹配窗口的下4個字符，發現字符7未出現在模式串相應的高位，即移位后不可能出現匹配，則移位12位。

第五次：4e00 79cd 5feb 901f 7684 5355 6a21 5f0f 5339 914d 7b97 6cd5 5339 914d

匹配結束。

改進算法與QS算法一樣，可能存在一個問題，即當下4個字符存在于模式串且可能靠模式串右邊一點，但該匹配窗口的最右端的字符并未出現在模式串中，這時只根據下4字符判斷移位，可能會使移位距離減小，增加比較的次數。因此，可考慮利用BMH算法[8]的最后一個字符的移位表和下4字符的移位表進行比較，選擇最大移位。某些情況下，選兩者進行比較，可能會提高效率。

4 測試結果

模式匹配需高效定位模式串。為了更好地對以上提到的算法及改進的算法進行性能分析，對其整個匹配過程所需時間進行了測試。實驗環境為win7 64位操作系統，配置為Intel（R）Core（TM）i7-2670QM CPU @2.20 GHz 2.19 GHz，內存為4 GB，C語言編程。由于PDF文件解析過程相對復雜，這里實驗文本采用模擬PDF文本內容的txt文本進行實驗，其文件大小為8.76 MB，內容為2 296 856個漢字，即9 187 584個字符，然后對其分別進行字符長度為 4、8、12、16、20、24、28、32、36、40的模式串匹配。為減小誤差，分別對每種匹配算法、不同長度模式串測試10次取其平均值，測試結果如表5所示。

表5 不同模式串長度、不同算法CPU耗時 /ms

從表5可以看出，改進的適合PDF文本內容的匹配算法更高效，時間復雜度更小，對比如圖5所示。

圖5 PDF文檔內容搜索時間對比

針對不同長度的模式串，對BM、QS、改進算法的匹配次數進行比較，如圖6所示。

圖6 PDF文檔內容匹配次數對比

匹配算法效率跟模式串有一定關系，QS、BM算法匹配效率與模式串長度密切相關，QS、BM算法最大移位距離與模式串的長度m有關，其最大移位距離為m+1、m。其中，QS是BM的簡化版，實現簡單，但存在下一字符在模式串中導致移位距離相對于BM減小的情況。

由圖5、圖6可以看出，相比于經典算法，改進算法的時間耗時和匹配次數最小，整體呈現出長度越大耗時越小的趨勢。

此外，針對改進算法，對模式串占比情況進行匹配次數和時間耗時的測量，結果如圖7、圖8所示。

圖7 PDF文檔內容搜索時間

圖8 PDF文檔內容匹配次數對比

由圖7、圖8可以看出，模式串長度越大、模式串占比越小，時間耗時越小；但同樣占比情況下，模式串的長度越大，匹配次數一般先減小后增大，但總體性能都較好。

改良算法利用BM、QS各自的優點，結合PDF文本內容編碼方式，利用BM的壞字符規則和QS的下一字符思想，只生成每個字高位的移位距離，使最大移位距離為m+4。由圖5、圖6可知，所提算法的匹配效率高于BM、QS都高，提高了PDF文本環境中仿真性能。

5 結 語

本文通過對PDF文件格式和文本內容的分析，分別闡述了BM算法、QS算法的基本思想及匹配過程，提出了一種適合用于PDF文件文本內容的匹配算法。實驗證明，改進算法在時間性能上有一定提高，實現也更為簡單，但存在與QS算法一樣的問題。目前，PDF文件的格式越來越復雜，還需進一步改進，使其在實際應用中更實用。

[1] Knuth D E,Morris J H,Pratt V R.Fast Pattern Matching in Strings[J].SIAM J. Comput.,1977,6(01):323-350.

[2] Boyer R S.A Fast String Searching Algorithm[J].Communications of the Acm,1977,20(10):762-772.

[3] Aho A V,Corasick M J.Efficient String Matching:An Aid to Bibliographic Search[J].Communications of the Acm,1975,18(06):333-340.

[4] Wu S,Manber U.A Fast Algorithm for Multi-pattern Searching[Z].Report TR-94-17,Department of Computer Science,University of Arizona,Tucson,AZ,1994.

[5] Sunday D M.A Very Fast Substring Search Algorithm[J].Communications of the Acm,1990,33(08):132-142.

[6] Inc A S.PDF Reference:Version 1.7[Z].2006.

[7] Adobe Systems Inc.Adobe Technote 5014:Adobe CMap and CIDFont Files Specification,Version1.0[EB/OL].Adobe Systems Inc.http://partners.adobe.com/public/developer/en/font/5014.CIDFont_Spec.pdf.

[8] Horspool R N.Practical Fast Searching in Strings[J].Softw. Pract. Exp.,1980,10(06):501-506.