適用于PDF文本內(nèi)容的高效模式匹配算法*

朱玲玉，王旌舟，陳慶春

0 引 言

模式匹配在網(wǎng)絡(luò)入侵檢測(cè)、生物序列數(shù)據(jù)庫(kù)比對(duì)（DNA）、信息檢索、生物計(jì)量學(xué)等領(lǐng)域得到了廣泛應(yīng)用。模式匹配按同時(shí)匹配模式串的個(gè)數(shù)，分為單模式匹配和多模式匹配，其中KMP[1]、BM[2]為經(jīng)典單模式匹配，AC[3]、WM[4]算法為經(jīng)典多模式匹配。每種模式匹配算法都有其最優(yōu)、最壞匹配復(fù)雜度，針對(duì)不同模式串的類型，其算法各有優(yōu)點(diǎn)。

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

1 PDF文件格式及編碼規(guī)則

PDF文檔是8 bit字節(jié)序，以二進(jìn)制流保存。深入理解PDF文件的格式，需從其對(duì)象、文件結(jié)構(gòu)（邏輯結(jié)構(gòu)）、文檔結(jié)構(gòu)（物理結(jié)構(gòu)）、內(nèi)容流和編碼4方面理解[6]。

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

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

2 經(jīng)典單模式匹配算法

2.1 模式匹配

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

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

給定模式串P，長(zhǎng)度為m，有：

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

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

2.2 BM算法

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

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

2.2.1 預(yù)處理過(guò)程

預(yù)處理過(guò)程建立壞字符表、后綴表。壞字符是指從左至右進(jìn)行匹配時(shí)，一旦失配，該字符被稱為壞字符。好后綴是指模式串左邊出現(xiàn)了模式串右側(cè)的字符串。以模式串“GCAGAGAG為例”構(gòu)建壞字符表和好后綴表，結(jié)果如表1、表2所示。

壞字符規(guī)則存在2種情況：一是失配字符出現(xiàn)在模式串中，令失配字符對(duì)齊模式串中靠右的字符，如圖1所示；二是失配字符未出現(xiàn)在模式串中，無(wú)論怎么移位，該字符都會(huì)產(chǎn)生失配，即移位至失配字符的下一位，如圖2所示。所以，模式例壞字符表計(jì)算結(jié)果如表1所示。

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

圖2 無(wú)失配字符壞字符移位

表1 BM壞字符表

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

圖3 無(wú)失配字符好后綴移位

圖4 有失配字符發(fā)好后綴移位

表2 BM好后綴表

2.2.2 匹配過(guò)程

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

該算法在文本串長(zhǎng)度為n、定位長(zhǎng)度為m的模式串中，其預(yù)處理階段的時(shí)間、匹配過(guò)程、最優(yōu)時(shí)間復(fù)雜度分別為 O(m+σ)、O(mn)、O(m/n)。

2.3 QS算法

QS算法是Daniel M.Sunday提出的一種簡(jiǎn)單快速單模式匹配算法，也稱Sunday算法。Sunday通過(guò)對(duì)模式串掃描的順序不同給出了三種算法，其中有QS算法、MS算法和OM算法。MS算法的掃描順序?yàn)橐莆坏拇笮〗敌颍琌M算法的掃描順序取決于其字符出現(xiàn)頻率的大小。

QS算法實(shí)質(zhì)是BM算法的一種簡(jiǎn)化版本，其實(shí)現(xiàn)更簡(jiǎn)單，僅利用了BM算法中的壞字符規(guī)則。基本思想：在進(jìn)行字符串匹配時(shí)，無(wú)論匹配方向從左至右還是從右至左，無(wú)需考慮匹配順序，由于發(fā)現(xiàn)不匹配會(huì)至少移動(dòng)一位，因此須考慮該匹配窗口的下一字符是否出現(xiàn)在模式串中，利用BM算法的壞字符規(guī)則計(jì)算其移位后再進(jìn)行匹配。因此，可利用下一字符來(lái)實(shí)現(xiàn)最大跳躍，使之最大位移為m+1。

2.3.1 預(yù)處理過(guò)程

預(yù)處理過(guò)程實(shí)質(zhì)是利用BM壞字符規(guī)則建立移位表。移位表建立也從字符是否在模式串及其位置考慮。若模式串中并未出現(xiàn)下一字符，則移位跳過(guò)該字符，再在匹配窗口進(jìn)行匹配；若在，移位與之對(duì)齊。移位計(jì)算公式為：

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

表3 QS下一字符移位表

2.3.2 匹配過(guò)程

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

該算法在文本串長(zhǎng)度為n、定位長(zhǎng)度為m的模式串中，其預(yù)處理階段的時(shí)間、空間、匹配過(guò)程、最優(yōu)時(shí)間復(fù)雜度分別為 O(m+σ)、O(σ)、O(mn)、O(n/(m+1))。該算法的問(wèn)題在于，當(dāng)出現(xiàn)下一字符移位距離小于失配字符的移位距離時(shí)，將導(dǎo)致QS算法效率大打折扣。

一般情況下，QS算法適用于短模式和大字符集的情形下，實(shí)現(xiàn)簡(jiǎn)單。

3 改進(jìn)算法

3.1 算法思想

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

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

3.2 算法預(yù)處理過(guò)程及匹配過(guò)程

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

匹配過(guò)程如下。從右至左開始匹配，一旦不匹配，立刻利用該匹配窗口的下4個(gè)字符，判斷其最高位的字符是否出現(xiàn)在模式串中的相應(yīng)位置上。如果沒(méi)有，說(shuō)明這4個(gè)字符也不可能與模式串匹配成功，則直接移位m+4；否則，移位模式串到其對(duì)應(yīng)處。

3.3 算法實(shí)例

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

模式串：5339 914d。

首先進(jìn)行預(yù)處理，如表4所示。

表4 Skip表

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

T[6]≠P[6]，則考慮匹配窗口的下4個(gè)字符的高位b。字符b未在模式串相應(yīng)的高位出現(xiàn)，此時(shí)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個(gè)字符的高位5。字符5未在模式串相應(yīng)的高位出現(xiàn)，此時(shí)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個(gè)字符的高位9。字符9在模式串相應(yīng)的高位出現(xiàn)，T[35]≠P[3]，移位8位。

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

發(fā)現(xiàn)匹配，考慮匹配窗口的下4個(gè)字符，發(fā)現(xiàn)字符7未出現(xiàn)在模式串相應(yīng)的高位，即移位后不可能出現(xiàn)匹配，則移位12位。

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

匹配結(jié)束。

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

4 測(cè)試結(jié)果

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

表5 不同模式串長(zhǎng)度、不同算法CPU耗時(shí) /ms

從表5可以看出，改進(jìn)的適合PDF文本內(nèi)容的匹配算法更高效，時(shí)間復(fù)雜度更小，對(duì)比如圖5所示。

圖5 PDF文檔內(nèi)容搜索時(shí)間對(duì)比

針對(duì)不同長(zhǎng)度的模式串，對(duì)BM、QS、改進(jìn)算法的匹配次數(shù)進(jìn)行比較，如圖6所示。

圖6 PDF文檔內(nèi)容匹配次數(shù)對(duì)比

匹配算法效率跟模式串有一定關(guān)系，QS、BM算法匹配效率與模式串長(zhǎng)度密切相關(guān)，QS、BM算法最大移位距離與模式串的長(zhǎng)度m有關(guān)，其最大移位距離為m+1、m。其中，QS是BM的簡(jiǎn)化版，實(shí)現(xiàn)簡(jiǎn)單，但存在下一字符在模式串中導(dǎo)致移位距離相對(duì)于BM減小的情況。

由圖5、圖6可以看出，相比于經(jīng)典算法，改進(jìn)算法的時(shí)間耗時(shí)和匹配次數(shù)最小，整體呈現(xiàn)出長(zhǎng)度越大耗時(shí)越小的趨勢(shì)。

此外，針對(duì)改進(jìn)算法，對(duì)模式串占比情況進(jìn)行匹配次數(shù)和時(shí)間耗時(shí)的測(cè)量，結(jié)果如圖7、圖8所示。

圖7 PDF文檔內(nèi)容搜索時(shí)間

圖8 PDF文檔內(nèi)容匹配次數(shù)對(duì)比

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

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

5 結(jié) 語(yǔ)

本文通過(guò)對(duì)PDF文件格式和文本內(nèi)容的分析，分別闡述了BM算法、QS算法的基本思想及匹配過(guò)程，提出了一種適合用于PDF文件文本內(nèi)容的匹配算法。實(shí)驗(yàn)證明，改進(jìn)算法在時(shí)間性能上有一定提高，實(shí)現(xiàn)也更為簡(jiǎn)單，但存在與QS算法一樣的問(wèn)題。目前，PDF文件的格式越來(lái)越復(fù)雜，還需進(jìn)一步改進(jìn)，使其在實(shí)際應(yīng)用中更實(shí)用。

[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.