Word文本解析和關鍵字快速匹配方法*

廖怨婷，蘭小龍，陳慶春

0 引 言

在大數(shù)據(jù)時代，網(wǎng)絡技術快速發(fā)展帶動著各行各業(yè)朝著信息化方向發(fā)展的同時，網(wǎng)絡安全事件頻繁發(fā)生。如何保護網(wǎng)上信息安全和數(shù)據(jù)安全，具有重要的理論和應用價值[1]。隨著電子文檔的普及應用，現(xiàn)在辦公基本無紙化。企業(yè)的大量重要數(shù)據(jù)和保密信息基本以電子文檔的形式存在，各種敏感信息和保密數(shù)據(jù)時刻受到潛在的泄露風險。這些敏感信息直接或間接地關系到企業(yè)或個人的數(shù)據(jù)安全，甚至關系到國家的信息安全。由此可見，對電子文檔的涉密信息進行保護，或者對敏感數(shù)據(jù)進行防泄漏處理，是保護網(wǎng)上內容信息安全的重要需求[2-3]。

本文提出一種Word文本內容解析及關鍵字快速匹配方法。首先以Microsoft Word文件為背景，研究Office套件中文字處理軟件Word組件的二進制格式。在此基礎上，分析如何在不安裝任何Microsoft Word辦公軟件的情況下，實現(xiàn)對Word文檔格式判別并讀取Word文本內容。同時，為了對文本內容的敏感信息進行保護，提出在讀取文本內容的同時，使用模式匹配算法對敏感信息進行查找。最終，在對現(xiàn)有的BM、BMH以及BMHS等算法進行分析比較的基礎上，提出了一種改進的BMHS算法。研究結果表明，所提方法適用于網(wǎng)絡在線的Word文本內容解析與敏感信息的保護要求。

1 Word文檔解析方法

Microsoft Office文 件 中，Microsoft Word 97-2003文檔（.doc）是一種典型的復合二進制文件[4]。復合文檔的整個文件由一個頭（Header）以及其后的所有扇區(qū)（Sectors）組成，結構如圖1所示。其中，頭（Header）大小為定長512字節(jié)，每個扇區(qū)的大小都相同，其大小由頭指定。根據(jù)頭的前8字節(jié)（D0H CFH 11H E0H A1H B1H 1AH E1H），可判斷接收文件是否為復合文檔[5]。

圖1 復合文檔結構

復合文檔包含很多獨立的數(shù)據(jù)流，這些數(shù)據(jù)流存放在不同的倉庫（Storage）中。流又都被劃分成小數(shù)據(jù)塊，叫做扇區(qū)（Sectors）。目錄（Directory）用來控制復合文檔中獨立的數(shù)據(jù)流，由一系列目錄入口組成。每一個目錄的入口都指向復合文檔的一個倉庫或流。目錄入口以其在目錄流中出現(xiàn)的順序被列舉，一個以0開始的目錄入口索引稱為目錄入口標識（Directory Entry IDentifier，DEID）。每個目錄入口的大小為定長128字節(jié)。

.doc文件的文本內容存儲在“WordDocument”流中。確定文件為復合文檔后，需要找到存放流的目錄入口。遍歷所有目錄入口，直到找到“WordDocument”流。遍歷方法可通過目錄入口的前64字節(jié)判定其入口名字為“WordDocument”。計算第一個目錄流的偏移量的公式為：

其中512指頭的長度；SID（Secror Identifier，扇區(qū)標識）是一個扇區(qū)的索引值，位于頭的第48字節(jié)；s_size是復合文檔中扇區(qū)的大小（ssz），以2的冪形式存儲，位于頭的第30字節(jié)。

對于“WordDocument”流，最重要的是其中包含的FIB（File Information Block，文件信息塊）。FIB從“WordDocument”流的偏移0x00開始。FIB是可變長的，其中FIB最開始為定長32字節(jié)的FibBase結構。根據(jù)FIB的前2字節(jié)（A5H ECH），可判斷接收文件是否為Word二進制文件，即.doc文件。FIB指定文件中所有其他數(shù)據(jù)的位置。位置由一對整數(shù)指定，第一個整數(shù)指定位置，第二個整數(shù)指定大小。這些整數(shù)出現(xiàn)在FIB的子結構中，如FibRgFcLcb97。位置名稱帶有前綴fc，大小名稱帶有前綴lcb。

在確定文檔為.doc文件后，需要讀取Clx結構信息。Clx結構是由零個或多個Prc結構組成的包含屬性信息的數(shù)組，后跟一個Pcdt結構。該結構又包含一個PlcPcd結構。PlcPcd結構將一個字符位置數(shù)組映射到Pcd結構。換言之，它將流中的字符位置映射到文檔文本中的字符。Pcd結構指定文本在“WordDocument”流中的位置，同時指定文本的一些屬性。

Clx相對文本的偏移地址=“Table Steam”流的偏移位置+fcClx （2）

其中，獲取“Table Steam”流的偏移位置同WordDocument”流，其目錄入口名為“1Table”；fcClx在FIB第268個字節(jié)處讀取，指定了Clx相對“Table Steam”流的偏移位置。具體地，確定Clx相對文本的偏移位置流程，如圖2所示。

圖2 Clx相對文本的偏移位置流程圖

Clx的結構如圖3所示，其中RgPrc若為空，第一字節(jié)必為0x02。Pcdt結構如圖4所示，如果clxt=0x02，表明已找到Pcdt，其中l(wèi)cb在FIB第272個字節(jié)處讀取，指定了PlcPcd的大小。

圖3 Clx結構

圖4 Pcdt結構

PlcPcd結構從Pcdt的第5個字節(jié)開始。一個PlcPcd結構包含一個（乃至以上）aCP和一個（乃至以上）aPcd，每個aCP是4字節(jié)，每個aPcd是8字節(jié)。計算aPcd的個數(shù)n，即：

加載這些aPcd數(shù)組和aCp數(shù)組。這些數(shù)組的成員通過索引值彼此對應。對于每個aPcd結構，在當前第46位處讀取fCompressed字段的值。如果fCompressed=0，則Pcd結構指代一個16位的Unicode字符。如果fCompressed=1，則指代一個8位的ANSI字符。如果是Unicode，則文本的起始偏移量等于在“WordDocument”流中的Fc值（位于當前Pcd的第2～5個字節(jié)），且每個字符占2個字節(jié)；如果是ANSI，文本開始于Fc值的一半的偏移量處，且每個字符占1個字節(jié)。至此，.doc文件中的文本內容的位置就可以準確確定。

2 改進的BMHS匹配算法

在Word文檔解析的基礎上，字符串的模式匹配可以應用于搜索和查找特定的字符串位置。對于長度為n的文本串T=T0T1T2…Tn-1，假設模式串P=P0P1P2…Pm-1的長度為m(n≥m)，在T中查找模式串P首次出現(xiàn)的位置。如果在文本串T總存在等于模式串P的子串，則匹配成功，返回模式串P首次出現(xiàn)在文本串T中的位置；否則，稱為匹配失敗。這個過程稱為模式匹配。

目前，國內外已提出了不少模式匹配算法。典型的BF算法[6]是從文本串T的開始位置開始逐個字符依次匹配，算法的時間復雜度是O(n×m)，BF算法雖然簡單但效率很低。KMP算法[7]在匹配過程中遇到不匹配時，不產(chǎn)生回溯，而是根據(jù)已有的部分匹配結果，令P向右滑動到某個位置，然后重新開始進行匹配。這在一定程度上提高了匹配效率，減少了匹配次數(shù)，但時間復雜度依然達到O(n+m)。BM算法[8]是由Robert S. Boyer教授和J Strother Moore教授提出的一種新的字符串匹配算法。該算法從模式串P的尾部與文本串T自右向左開始匹配。如果不匹配，則根據(jù)模式串P決定的好后綴規(guī)則和壞字符規(guī)則進行右移，降低無效的匹配次數(shù)，然后繼續(xù)與文本串T進行匹配，直至匹配成功或者文本串T匹配結束。實踐中，BM算法比KMP算法的實際效率更高，因而得到了廣泛應用。BMH算法[9]進一步解決了BM算法中模式串P有可能左移的問題。在BMH中，無論失配發(fā)生在當前文本串T中的什么位置，都由文本T中和模式串P的尾字符對應的字符決定右移距離。它摒棄了好后綴規(guī)則后，省去了求最大值的計算。

BMH算法的壞字符規(guī)則如下：

當模式串P從右向左與文本串T進行匹配時，若模式串P中某個字符x與文本串T中相對應字符不匹配，即出現(xiàn)壞字符時，則根據(jù)式（4）跳轉：

其中P[ j ]代表模式串P中的第j個字符，max(x)表示字符m出現(xiàn)在模式串P中最右的位置。

2.1 BMHS算法

BMHS算法[10]在BMH算法的基礎上又進一步進行了改進，主要思想是：由文本T中和模式串P的尾字符的下一個字符（即當前匹配窗口的下一個字符）對應的字符決定右移距離。這使得最大和平常情況下，它的速度優(yōu)于BMH。

BMHS算法中壞字符規(guī)則為：

2.2 改進的BMHS算法

通過對模式串P特點的分析以及經(jīng)過實際測試，本文對BMHS算法做出改進。實際應用中，匹配的模式串P多數(shù)情況下是一個英文單詞。通常，英文單詞有相同前綴或后綴的概率較高，而單詞中間部分相同的概率較小，如internet與interaction、sixteen與seventeen等。因此，本文在保留BMHS算法的壞字符規(guī)則和根據(jù)當前匹配窗口的下一個字符決定右移距離的思想的基礎上，針對相同前后綴出現(xiàn)的概率大、中間部分相同的概率小這一特點，對BMHS算法進行改進。具體地，匹配過程中，先匹配模式串P的尾字符，若匹配成功，則匹配模式串P的首字符；若依然匹配，則匹配模式串P中間的字符。最后，從P的第二個字符依次匹配，直至倒數(shù)第二個字符，其中跳過中間的字符。整個過程中，一旦出現(xiàn)不匹配，則根據(jù)式（4）向右移動相應的距離。改進的BMHS算法實現(xiàn)流程如圖5所示。

圖5 改進的BMHS算法基本流程

3 實驗結果

3.1 BMHS和改進BMHS算法比較分析

基于對BMHS算法和改進的BMHS算法進行的簡單說明，下面將從匹配次數(shù)和比對次數(shù)2個方面對BMHS和改進BMHS算法進行詳細比較。實驗平臺是windows 10操作系統(tǒng)，開發(fā)工具是Microsoft Visual Studio 2013。

文本串T=“nagativelasgrelfcivehbdcgm relative”，模式串P=“relative”。根據(jù)模式串P計算的壞字符表，如表1所示。BMHS和改進BMHS算法的詳細匹配過程，分別如圖6、圖7所示。

表1 BMHS和改進的BMHS算法中模式串P的壞字符表

圖6 BMHS算法匹配過程

圖7 改進的BMHS算法匹配過程

可以看出，改進的BMHS算法在匹配過程中，相比于BMHS算法減少了比對次數(shù)。這是因為文本串中出現(xiàn)了前后綴相同的單詞，改進算法有效避開了這類單詞，減少了比對次數(shù)。這種優(yōu)勢在較大的文檔中能更好地體現(xiàn)出來。

下面從時間消耗方面比較BMHS算法和改進BMHS算法的性能。

（1）對同一個大小為575 kB的文檔，用2種匹配算法對模式串P=“l(fā)ife”進行匹配，實驗結果如表2、圖8所示。

表2 文檔匹配耗時比較

圖8 文檔匹配耗時比較結果

表2顯示模式串“l(fā)ife”在文檔中共檢測到75次，用改進BMHS算法匹配完成后，總耗時和平均耗時均小于BMHS算法。

圖8中，對2種匹配算法共進行了各50次匹配實驗，縱坐標表示單詞匹配所消耗的時間，單位為ms，其中黑色為BMHS算法的匹配結果，灰色為改進的BMHS算法的匹配結果。從所耗時間的整體趨勢可以看出，本文提出的算法對BMHS算法有一定程度的改進，耗時縮小。

（2）針對不同長度字符串對BMHS算法和改進BMHS算法的影響，本文對不同模式串長度下兩種匹配算法的耗時進行比較和分析。實驗中，針對長度從2～15的不同模式串用2種算法進行匹配，每次匹配時間的結果比較如表3、圖9所示。

從表3、圖9的比較結果可以看出，對于長度在4～11的模式串，本文提出的改進BMHS算法要比BMHS算法耗時少。因為英文單詞大部分長度都在這個范圍內，前后綴相同的單詞有很大概率在匹配過程中遇到。當模式串長度長于12時，文本中很少遇到這種單詞，因此兩種算法的耗時基本一樣，體現(xiàn)不出優(yōu)越性。

表3 不同長度模式串下兩種匹配算法耗時比較

圖9 不同長度模式串下兩種匹配算法耗時

3.2 Word文本解析及脫敏

通過對Word文本格式的分析，運用改進的BMHS算法，針對測試文檔地址（http∶//xueshu.baidu.com/s?wd=paperuri%3A%28872b584de8d1c2358b1c401caf810527%2 9&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fieeexplore.ieee.org%2Fdocument%2F 6918451%2F&ie=utf-8&sc_us=16970001388366800462）下載Word文檔，后對其“Vehicle”敏感詞匯進行脫敏，結果如圖10所示。可以看到，凡是出現(xiàn)“Vehicle”的地方均變成了****。

圖10 Word文檔解析及脫敏效果展示

4 結 語

本文研究了Word文件的二進制格式，在無需Microsoft Office辦公軟件的條件下，能夠對Word文檔進行格式判別和文本內容解析，方法簡單易行，解析結果準確清晰。本文使用模式匹配算法對文本內容的敏感信息進行快速定位，在研究了BM、BMH以及BMHS等算法的基礎上，提出了一種基于BMHS的改進快速匹配算法。實驗結果顯示，本文提出的改進的BMHS算法相比BMHS算法，匹配次數(shù)有所減少，匹配時間有所降低，更好地提高了匹配效率。

[1] 閆璽璽.開放網(wǎng)絡環(huán)境下敏感數(shù)據(jù)安全與防泄密關鍵技術研究[D].北京:北京郵電大學,2012.YAN Xi-xi.Research on Key Technologies of Security and Anti-leakage of Sensitive Data in Open Network[D].Beijing:Beijing University of Posts and Telecommunications,2012.

[2] 陳天瑩,陳劍鋒.大數(shù)據(jù)環(huán)境下的智能數(shù)據(jù)脫敏系統(tǒng)[J].通信技術,2016,49(07):915-922.CHEN Tian-ying,CHEN Jian-feng.Detective Data Depletion System Based on Big Data Environment[J].Communications Technology,2016,49(07):915-922.

[3] 胡卿.電子文檔防泄密系統(tǒng)研究與實現(xiàn)[D].濟寧:曲阜師范大學,2013.HU Qing.Research and Implementation of Electronic Document Anti-leakage System[D].Jining:Qufu Normal University,2013.

[4] Microsoft.[MS-DOC]:Word(.doc) Binary File Format[EB/OL].(2016-01-01)[2017-11-24].https://msdn.microsoft.com/enus/library/office/cc313153(v=office.12).aspx.

[5] Daniel R.Microsoft Compound Document File Format[EB/OL].(2004-01-01)[2017-11-24].http://www.openoffice.org/sc/compdocfileformat.pdf.

[6] GUO Jiong,Hermelin,Danny,et al.Local Search for String Problems:Brute-force is Essentially Optimal[J].Theoretical Computer Science,2014,525(03):30-41.

[7] WANG Cheng,LIU Jin-gang.An Improved String Matching Algorithm[J].Computer Engineering,2006,32(02):62-64.

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

[9] 劉勝飛,張云泉.一種改進的BMH模式匹配算法[J].計算機科學,2008(11):164-165,173.LIU Sheng-fei,ZHANG Yun-quan.An Improved BMH Pattern Matching Algorithm[J].Computer Science,2008(11):164-165,173.

[10] 朱寧洪.字符串匹配算法Sunday的改進[J].西安科技大學學報,2016,36(01):111-115.ZHU Ning-hong.Improvement of String Matching Algorithm Sunday[J].Journal of Xi'an University of Science and Technology,2016,36(01):111-115.