編碼與同義詞替換結合的可逆文本水印算法

林新建 ,唐向宏,2 ,王 靜

(1. 杭州電子科技大學 通信工程學院，浙江 杭州 310018；2. 杭州電子科技大學 信息工程學院，浙江 杭州 310018)

?

編碼與同義詞替換結合的可逆文本水印算法

林新建1,唐向宏1,2,王 靜1

(1. 杭州電子科技大學 通信工程學院，浙江 杭州 310018；2. 杭州電子科技大學 信息工程學院，浙江 杭州 310018)

從通信編碼的角度，該文探討一種利用編碼方法和同義詞替換相結合的可逆文本篡改檢測水印算法。以可替換同義詞為標志對文本進行分組，提取分組文本特征生成認證水印信息；利用霍夫曼編碼和糾錯編碼對同義詞庫各詞進行編碼，利用同義詞替換技術完成水印的嵌入。在接收端，利用分組文本特征和霍夫曼編碼，實現水印文本的篡改定位，利用糾錯碼實現可替換同義詞的還原恢復。仿真實驗表明，算法嵌入的水印具有良好的不可見性和較強的魯棒性，在實現對文本篡改定位的同時，較好地實現了可替換同義詞無損還原。

編碼；同義詞替換；可逆文本水印；定位篡改

1 引言

為了克服自然語言的文本水印算法中因同義詞替換不具有可逆性[1-4]造成的文本語義的偏離問題，一種稱為可逆文本水印的技術近幾年得到了廣泛的關注。所謂可逆文本水印是指算法不僅能夠從文本載體中提取出嵌入的水印，同時還能夠完全恢復原始文本載體。

現今國內外學者對可逆水印的篡改定位和恢復研究主要集中在圖像領域[5-9], 對可逆文本水印算法研究相對較少。目前，針對中文文本可逆文本水印的研究主要集中在對同義詞的可逆替換，實現水印的可逆嵌入。Luis[10]等提出一種篡改文本的恢復算法，對一些刪除、篡改替換等攻擊均可實現文本內容的定位以及恢復。Anamitra[11]等利用IWT和DCT兩種技術提出一種可檢測篡改和恢復的水印算法，該算法對內容修改有著較強的魯棒性以及定位恢復能力。然而，文獻[10-11]所提算法的前提條件是將文本文檔轉為文本圖像，因此嚴格意義上說該類算法還是屬于圖像領域。姜傳賢等[12]提出了一種魯棒可逆文本水印算法，該算法通過同義詞替換評價模型尋找替換同義詞，將替換同義詞與原生同義詞的詞典編碼異或值作為可逆恢復數據。該算法充分考慮了同義詞替換對文本產生的語義偏離，然而在提取水印和恢復原始文本時需要大量的冗余信息。同年，劉志杰等[13]在基于圖像可逆水印的基礎上，提出了兩種可逆水印方案，基于整數可逆變換的文本可恢復水印算法和一種改進的差值擴展的文本可恢復水印算法。兩種方案首先都對同義詞編號進行像素值模擬，之后利用整數可逆變換和差值擴展對這些模擬像素值進行水印嵌入，水印嵌入完成后再將模擬像素值還原為同義詞編號，依據編號找到對應同義詞替換原始文本中同義詞得到水印文本，兩種算法充分借鑒了圖像可逆水印的思想，但是都沒考慮在改變詞語嵌入水印時，對文本產生的語義偏差。費文斌等[14]提出了基于預測誤差擴展的文本可逆水印算法，該算法考慮了水印嵌入后可能造成的文本歧義性。文獻[12-14]所提出的可逆文本水印算法都很好地定位了可替換同義詞是否被篡改替換，并實現可替換同義詞還原，實現原始文本內容的無損恢復。然而，三種算法卻無法判斷和定位出可替換同義詞以外區域文本的篡改情況。

為此，本文從通信編碼的角度，探討一種編碼技術和同義詞替換相結合的可逆文本水印算法。算法通過搜索文本得到所有可替換同義詞及其對應的同義詞庫，以可替換同義詞為標志對文本進行分組；提取可替換同義詞的相鄰分組文本的特征構造水印信息；對同義詞庫中各詞進行霍夫曼編碼和糾錯編碼。嵌入端用霍夫曼編碼與水印一致的同義詞替換原始同義詞，完成水印的嵌入。在提取端通過對比提取的水印信息和定位信息是否一致，判斷和定位出可替換同義詞是否篡改，以及文本區域被篡改情況；對每個同義詞碼字進行糾錯解碼，完成被替換同義詞的恢復。

2 編碼原理

為實現分組文本的篡改定位，本文對每個可替換同義詞對應的同義詞庫中的各詞進行霍夫曼編碼。眾所周知，霍夫曼編碼依據字符的出現概率進行編碼[15]，概率大的字符其碼長相對較短，概率小的字符其碼長相對較長。假設某一可替換同義詞對應的同義詞庫中有n個詞，考慮同義詞替換的語義影響[16]，對各詞的霍夫曼編碼算法如下。

① 計算同義詞庫中各詞在句子上下文的搭配度CDi[3]，搭配度小于閾值thr的同義詞從詞庫中刪除，最后得到詞庫滿足條件的有m(m≤n)個詞，同時得到這m個詞的搭配度總和，如式(1)所示。

(1)

② 按式(1)計算得到同義詞庫中各詞的歸一化概率Pi，使搭配度越大的同義詞其歸一化概率越小，并按歸一化概率升序對同義詞庫各詞進行排序，如式(2)所示。

(2)

③ 根據各詞的歸一化概率，對排序后的同義詞庫各詞進行霍夫曼編碼，得到同義詞庫各詞的霍夫曼編碼，其中搭配度大的同義詞其碼長相對較長，搭配度小的同義詞其碼長相對較短。

為使水印系統的實現簡單易行，本文糾錯碼采用循環冗余校驗碼(CRC)[17]。碼長為N的(N,K)-CRC碼由兩部分構成：K位信息碼和R=N-K位校驗碼。在本算法中用K位信息碼表示同義詞位置的編碼，R位校驗碼表示同義詞可逆替換所需的監督信息。當水印嵌入后，R位校驗碼保存作為水印提取時的密鑰。

關于N、K大小的選擇，根據漢語特點，一個詞的同義詞總數最多可有幾十個。以哈爾濱工業大學的《同義詞詞林擴展版》為基礎，在不考慮句子語義的前提下對詞林中8 602個同義詞組進行統計測試，其中擁有超過16個同義詞的同義詞組有75個，所占比例為75/8 602=0.008 7。在實際應用中，當考慮句子語義后，通過閾值的合理設置，可以將這個比例降到為0。因此，可用4bit的二進制碼對同義詞編號進行編碼，K=4。為能夠糾正錯誤碼字，R最小取值為3，即用3bit表示其對應校驗碼信息，因此本文采用的糾錯碼為(7,4)-CRC。

表1給出本文(7,4)-CRC正確碼字的組成結構，定義同義詞編號1-8的同義詞詞標記位flag=0，同義詞編號9-16的同義詞詞標記位flag=1。信息碼對應同義詞編號1-16，一個校驗碼對應兩個信息碼。當碼字發生錯誤時，可根據原始校驗碼、詞標記位flag以及表1找到一個正確的信息碼，從而得到糾正后的正確碼字。

經過上述編碼，一個可替換同義詞在其同義詞庫中的位置就擁有兩種編碼： 霍夫曼編碼和(7,4)-CRC編碼。霍夫曼編碼功能實現水印的嵌入與提取，(7,4)-CRC編碼功能實現同義詞的可逆替換，兩種編碼獨立不相關。

表1 同義詞編號生成的(7,4)-CRC碼字組成結構表

3 水印嵌入和提取算法

3.1 水印的嵌入

可逆水印嵌入的具體流程如圖1所示，具體步驟如下。

圖1 文本水印嵌入

(1) 文本預處理

(2) 隊列去重

(3) 文本分組

圖2 相鄰可替換詞的左鄰分組文本

注意： 若第一個詞(假設為A′(i))無左鄰分組文本，則該詞的左鄰分組文本為空；若最后一個詞(假設為A′(i+3))有右鄰分組文本，則將CTi+3L′和CTi+4L′二者合并作為A′(i+3)的左鄰分組文本，即CTi+3L′={CTi+3L′CTi+4L′}。

(4) 隊列置亂

圖3 可替換同義詞及其相鄰分組文本的置亂

(5) 同義詞編碼

(6) 分組文本特征值計算

為生成水印信息，先對分組文本進行預處理。定位詞A″(i)的左鄰分組文本，統計分組文本的字數以及各字的筆畫數，按式(3)計算分組文本的特征值x0；

(3)

式(3)中，n代表分組文本的字數，Sm代表分組文本中最小筆畫數，SM代表分組文本中最大筆畫數，Si代表分組文本中某個字符的筆畫數，得到可替換同義詞的左鄰分組文本的特征值Lx0(i)。若n=0，即詞A″(i)的左鄰分組文本為空，則令x0=0.001。

(7) 水印信息的生成

① 令k=MaxLen,(Li)k表示二進制序列Li的前k比特；

② 讀取詞庫中霍夫曼編碼碼長為k的所有同義詞，遍歷搜索這些同義詞，獲取霍夫曼編碼為(Li)k的同義詞，若該同義詞不存在，則轉步驟③；反之，得到水印信息Wi=(Li)k，搜索算法停止；

③ 令k=k-1，重新執行步驟②。

(8) 水印的嵌入

重復執行步驟(5)～(8)，遍歷完原始文本。得到水印文本和密鑰KEY。

3.2 水印提取及同義詞的可逆替換

水印的提取為水印嵌入的逆過程。圖4給出一個可替換同義詞的水印提取及其左鄰分組文本的篡改檢測流程，圖5給出一個可替換同義詞的無損還原流程。具體步驟如下：

圖4 可替換同義詞的水印提取及其左右相鄰分組文本的篡改檢測

圖5 可替換同義詞的無損還原

(2) 水印的提取

(3) 篡改定位

對詞AW″(i)的左鄰分組文本，以Lx0(i)′為初值，生成與水印Wi′等長的二進制混沌序列Li′，得到定位信息LRi′=Li′；若Wi′≡LRi′，則該詞的左鄰分組文本內容未遭篡改。反之，若Wi′≠LRi′，則定位該同義詞的左鄰分組文本某處內容遭到篡改。

(4) 同義詞的可逆恢復

① 獲取詞AW″(i)在同義詞庫{AWBi″(j)}中的位置(wki)2以及詞標記位flagi′;；依次從密鑰KEY中提取3bit校驗碼(wvi)2和1bit詞標記位flagi′；將(wki)2和(wvi)2二者重構成(7,4)-CRC碼字Cwordi′；

② 根據表1，對碼字Cwordi′進行正確與否判別： 當且僅當碼字Cwordi′可在表1中找到，且flagi″和flagi′一致，則碼字正確；反之，碼字出錯；

③ 若碼字Cwordi′正確，則詞AW″(i)保持不變；若碼字Cwordi′出錯，需根據表1對碼字Cwordi′進行糾錯實現被替換詞的恢復；

④ 糾錯具體實現過程如下： 首先，根據詞AW″(i)的詞標記位flagi′和碼字Cwordi′的校驗碼(wvi)2，利用表1，找到對應的信息碼，得到糾錯碼字Cwordi′，實現對碼字Cwordi′糾錯處理；然后，讀取糾錯碼字Cwordi″的4bit信息碼(eki)2，搜索同義詞庫{AWBi″(j)}中位置eki對應的同義詞AWBi″(eki)，并用該詞替換水印同義詞AW″(i)，實現被替換詞的恢復。其流程如圖4所示。

重復執行步驟(2)到步驟(4)，遍歷完水印文本。得到水印信息{Wi′}和文本篡改檢測結果。

4 實驗結果和性能分析

為了驗證本算法的性能，在計算機(PentiumIVCPU2.8GHz、1GB內存)上進行了仿真，并與相關算法進行了比較。編程語言為MATLABV7.0，實驗文本內容取自網上新聞語料，文本為純文本格式文件。同義詞上下文搭配度算法使用的語料庫來自人民日報1998年和2002年部分語料，一共約385萬字，搭配度閾值thr=1。限于篇幅，下面僅給出部分實驗結果。另外，為了便于區分文本在水印嵌入前后詞語的變化，所以，在水印嵌入和提取等過程，采用對字體加粗、帶陰影、單下劃線、雙下劃線等方式進行標注。

4.1 可恢復性分析

圖6給出原始文本，圖中字體加粗帶陰影的詞匯代表可替換的同義詞。圖7給出嵌入水印后的水印文本及嵌入的水印，圖中字體加粗帶陰影和單下劃線的詞匯代表替換的同義詞。圖8給出提取水印后恢復的文本及提取的水印，圖中字體加粗帶陰影和雙下劃線的詞匯代表還原的同義詞。每個可替換同義詞嵌入的水印不等長，圖中水印信息間隔加陰影以示區分。

圖6 原始文本

圖7 水印文本

從圖7中嵌有水印的水印文本可以看出，水印的嵌入沒有引起文本格式外觀上的變化；采用搭配度方法選取同義詞，較好地避免了詞匯語境的歧義性，所嵌水印具有較好的不可見性。從圖8恢復的文本可以看出，本算法能夠無損的恢復原始文本。提取得到的水印W′與原始水印W一致。從以上比較分析可得，本算法在正確提取水印信息的同時，也無損地恢復了原始文本中被替換同義詞，且信息的隱蔽性能很好。另外，由于在水印嵌入之前，將可替換詞隊列進行了置亂處理，使得水印信息與文本中可替換詞非一一對應，提高算法的安全性。

4.2 魯棒性分析

(1) 常見格式攻擊

表2分別給出了對水印文本的文本再生攻擊、格式轉換、字體大小、顏色變化、刪除空格等一些常見文本格式攻擊后提取得到的水印信息。由于本算法水印的嵌入是發生在文本的內容中，故通過刪改這些屬性無法達到攻擊水印信息的目的。由于這些格式攻擊并沒有造成文本內容的改變，因此算法將這些攻擊視為無惡意攻擊，并不將其定位檢測出來。

(2) 句子、段落交換攻擊

圖9給出了水印文本(圖7)受到句子交換攻擊的攻擊文本，圖中帶單下劃線的句子代表互相交換的句子，圖10為圖9的恢復文本。圖11給出了水印文本(圖7)受到段落交換攻擊的攻擊文本，圖中帶雙下劃線的段落代表互相交換的段落，圖12為圖11的恢復文本。圖中帶細波浪線的內容代表定位成功的篡改分組文本區域，帶粗波浪線的內容代表定位失敗的篡改分組文本區域，以下類似標注。

表2 格式攻擊分析

圖9 句子交換攻擊文本

圖10 句子交換攻擊恢復文本

圖11 段落交換攻擊文本

圖12 段落交換攻擊恢復文本

由圖10和圖12可看出，句子、段交換攻擊不影響本算法對水印信息的正確提取和文本被替換同義詞的無損恢復，即本算法可很好地抵抗此類攻擊。由圖10和圖12亦可知，算法定位出可替換同義詞以外區域文本的篡改情況結果并不都是正確的，定位結果受限于算法的定位精度。由嵌入的水印可知，可替換同義詞一次嵌入的水印比特位最小為1bit，最大為4bit，因此，定位精度最小為1-1/21=50.00#，最大為1-1/24=93.75#。算法無法還原句子、段落的原始順序。

(3) 句子復制粘貼攻擊

圖13給出水印文本(圖7)受到句子復制粘貼攻擊的攻擊文本，圖中帶單下劃線的句子代表復制粘貼的句子，圖14為圖13的恢復文本。

圖13 句子復制粘貼攻擊文本

圖14 句子復制粘貼攻擊恢復文本

由圖14 可知，句子復制粘貼攻擊即使增加了可替換同義詞的詞數，但它并不會影響到本算法對水印信息的正確提取和文本原始被替換同義詞的無損恢復，即本算法可很好地抵抗此類攻擊。定位檢測結果如圖14所示。

(4) 句子內容增刪攻擊

圖15和圖17分別給出水印文本(圖7)受到不同句子內容增刪攻擊的攻擊文本，圖16和圖18分別為圖15和圖17的恢復文本。圖中帶單刪除線的內容表示刪除不包含可替換同義詞的內容，帶點式下劃線的內容表示增加不包含可替換同義詞的內容；帶雙刪除線的內容表示刪除包含可替換同義詞的內容，帶虛下劃線的內容表示增加包含可替換同義詞的內容。

圖15 句子詞匯增刪攻擊文本1

圖16 句子詞匯增刪攻擊恢復文本1

圖17 句子詞匯增刪攻擊文本2

圖18 句子詞匯增刪攻擊恢復文本2

由圖16可看出，當增刪的內容不涉及到可替換同義詞時，這時的攻擊不會影響本算法對水印信息的提取和文本原始被替換同義詞的無損恢復；當增刪的內容涉及到可替換同義詞時(圖18)，這時攻擊將影響到水印信息的提取和文本原始被替換同義詞的無損恢復，不能正確提取水印信息和還原被替換的同義詞。定位檢測結果如圖16和圖18所示。

(5) 同義詞替換攻擊

圖19給出水印文本(圖7)受到同義詞替換攻擊的攻擊文本，圖中帶雙下劃線的詞匯代表同義詞替換攻擊替換的同義詞。由于文獻12、文獻13和文獻14的每個可替換同義詞只能嵌入1bit水印，假設這三種算法嵌入的水印信息為101100010110。圖20、圖21、圖22及圖23分別為文獻12、文獻13、文獻14以及本算法對圖19的恢復文本和提取的水印。

圖19 同義詞替換攻擊文本

圖20 文獻[12]同義詞替換攻擊恢復文本

圖21 文獻[13]同義詞替換攻擊恢復文本

圖22 文獻[14]同義詞替換攻擊恢復文本

圖23 本文同義詞替換攻擊恢復文本

由圖20、圖21和圖22可知，水印文本受到同義詞替換攻擊時，文獻[12]、文獻[13]及文獻[14]無法恢復出原始同義詞。與此相反，從圖23可知，本算法基本恢復出了原始同義詞，且文中一旦有可替換同義詞被替換掉，算法肯定能夠判斷出文中內容遭過篡改。

通過以上仿真的實驗分析，實驗中與其他可逆算法進行了性能比較，如表3所示。

表3 算法性能比較

5 結論

本文從通信編碼的角度，探討一種同義詞替換和編碼技術相結合的可逆文本水印算法。借鑒霍夫曼和糾錯編碼的思想以及采用同義詞替換技術，實現水印的嵌入及可恢復提取。在提取水印時既不需要原始載體也不需要原始水印，只需密鑰就可實現水印的提取及原始文本的無損恢復， 增強了方案的實際可行性。實驗仿真表明，算法對格式攻擊、句子、段變換攻擊表現出了較強的魯棒性，且可定位文

本篡改區域；在水印文本未遭到攻擊時，能完全恢復出原始同義詞；當遭到小范圍同義詞替換、內容增刪等攻擊時，算法能恢復出原始同義詞；當遭到大面積同義詞替換、內容增刪等攻擊時，算法只能部分恢復出原始同義詞。當然，算法還是存在著一些不足，例如，恢復只是針對同義詞替換而不是文本任意內容，篡改定位精度還有待提高，以及同義詞替換引起語義歧義或語句不是很通順等問題，這些不足也將是今后研究的重點。

[1] Mercan Topkara，Cuneyt M，Taskiran. Natural language watermarking [C]//Proceedings of Security，Steganography，and Watermarking of Multimedia Contents VII，2005，2005： 441-452.

[2] Zunera Jalil，Anwar M Mirza. A review of digital watermarking techniques for text documents [C]//Proceedings of 2009 International Conference on Information and Multimedia Technology，ICIMT 2009，2009： 230-234.

[3] Zheng Xueling，Huang Liusheng，Chen Zhil. Hiding information by context-based synonym substitution[C]//Proceedings of 8th Internation- al Workshop on Digital Watermarking，IWDW 2009，2009： 162-169.

[4] 黃華，齊春，李俊，等. 文本數字水印[J]. 中文信息學報，2001, 15(5): 52-57．

[5] Coatriuex G，Guillou C L，Gauvin J M. Reversible watermarking for knowledge digest embedding and reliability control in medical images [J]. IEEE Transaction on Information Technology in Biomedicine，2009，13(2)： 158-165.

[6] 彭飛，雷瑜洲，孫星明. 2維CAD工程圖小波域可逆水印[J]. 中國圖象圖形學報，2011，16(7)： 1134-1139.

[7] 王俊祥，倪江群，潘金偉. 一種基于直方圖平移的高性能可逆水印算法[J]. 自動化學報，2012，38(1)： 88-96.

[8] Banani Patra，Jagdish C Patra. CRT-based fragile self-recovery watermarking scheme for image authentication and recovery [C]//Proceedings of 20th IEEE International Symposium on Intelligent Signal Processing and Communications Systems(ISPACS)，2012： 430-435.

[9] T jokorda Agung B.W，Adiwijaya. Medical image watermarking with tamper detection and recovery using reversible watermarking with LSB modification and Run Length Encoding (RLE) compression [C]//Proceedings of 2012 IEEE International Conference onCommunication，Networks and Satellite，COMNETSAT 2012，2012： 167-171.

[10] Luis Rosales-Roldan，Mariko Nakano-Miyatake. Watermarking-based tamper detection and recovery algorithms for official documents[C]//Proceeding of 8th International Conference on Electrical Engineering，Computing Science and Automatic Control，CCE 2011，2011.

[11] Makur Anamitra，Sridharan Govindarajan. Watermark based recovery of tampered documents[C]//Proceedings of ACM SIGKDD Workshop on Intelligence and Security Informatics，ISI-KDD 2012，2012.

[12] 姜傳賢，陳孝威. 魯棒可逆文本水印算法[J]. 計算機輔助設計與圖形學學報，2010，22(3)： 879-885.

[13] 劉志杰. 基于自然語言的文本可恢復水印研究[D].長沙： 湖南大學，2010.

[14] 費文斌. 可逆文本水印算法研究[D].杭州： 杭州電子科技大學，2013.

[15] 甘燦. 基于同義詞替換的自然語言文本信息隱藏技術研究[D]. 長沙： 湖南大學，2010.

[16] 張宇，劉挺，陳毅恒，等. 自然語言文本水印[J]. 中文信息學報，2005, 19(1): 56-62．

[17] 傅祖蕓. 信息論—基礎理論與應用[M].北京： 電子工業出版社，2007 ： 367-380.

[18] 向華，曹漢強，伍凱寧，等. 一種基于混沌調制的零水印算法[J]. 中國圖象圖形學報，2006，11(5)： 720-724.

A Reversible Text Watermarking Algorithm Based on Coding and Synonymy Substitution

LIN Xinjian1，TANG Xianghong1,2，WANG Jing1

(1. School of Communication Engineering, Hangzhou Dianzi University , Hangzhou, Zhejiang 310018,China;2. School of Information Engineering, Hangzhou Dianzi University, Hangzhou, Zhejiang 310018,China)

From the perspective of communication encoding, a reversible text watermarking algorithm based on coding and synonymy substitution is discussed. The algorithm employs interchangeable synonyms as signs to group the texts and generates watermarking by extracting group text feature. The algorithm uses the method of Huffman coding to encode synonyms and uses the method of error correction coding to encode the position of a synonym in the thesaurus into , then completes the watermark embedding combined with synonymy substitution. At the receiving end, using packet text feature and the Hoffman code to locate tampered watermark text and using error correcting codes to restore the original synonymy. Experimental results show that, the proposed algorithm can improve the robustness and imperceptibility of watermarking. In addition, it can locate the tampering and restore the original synonymy.

coding；synonymy substitution；reversible text watermarking； tampering identification

林新建(1988—),碩士,主要研究領域為文本數字水印。E-mail:lxj657983@126.com唐向宏(1962—),博士,教授,主要研究領域為擴頻通信、圖像壓縮與傳輸和數字水印。E-mail:tangxh@hdu.edu.cn王靜(1989—),碩士,主要研究領域為文本數字水印。E-mail:wang_jing001@163.com

1003-0077(2015)04-0151-08

2013-09-09 定稿日期： 2014-02-28

TP391

A