基于句法依存分析的文本水印算法

吳戈，文大化

（1.長春理工大學 電子信息工程學院，長春 130022；2.中國科學院 長春光學精密機械與物理研究所，長春 130033）

目前，數字水印被普遍認為是抵抗各種多媒體產品盜版及解決相關版權糾紛的“最后一道防線”。因此從水印技術角度來看，它的應用前景之廣泛和經濟價值之大受到了整個業界的矚目。進入21世紀，人們對網絡逐漸從認識過渡到熟悉，網絡即給人們合法使用提供了方便，同時也使盜版也變得更加輕易，因此數字作品的管理、保護不僅成為業界迫切需要解決的問題，而且對非法使用數字作品的維權也成為司法界執行版權糾紛的要求。

電子文檔就是以數據方式存于計算機中的文件，目前，即使視頻和音頻數字作品依托互聯網快速發展，但文本數據依然是互聯網上使用最多和傳播最廣的一種信息模式。因此如何保護電子文本版權，維護原創作者的權益，以及充分利用文本數據作載體進行隱蔽通信，對信息安全具有重要意義和實用價值。

1 文本水印

文本水印作為一種保護文本數據信息的技術，它的目的是保護在文本媒體中隱藏的信息不被非法使用者侵犯并可利用水印檢測技術恢復和保留在數據中，從而實現文本所有權和跟蹤對作品的侵權行為。目前已有的大部分文本信息隱藏方法集中于兩個方面：一種是采用基于文本數據格式的方式，通過改變文本的排版特征嵌入隱秘信息。這種方法由于對媒體本身改動過于明顯，很容易受到重新排版的影響，同時也很容易受到敵手的攻擊，甚至隱秘信息被識別。另一種是基于自然語言算法的信息隱藏，其方法按照水印嵌入粒度可分為詞匯層、句子層和篇章層。本文從句子層角度出發進行探討的。

不論想在哪種載體（文本、圖像、視頻、音頻等數字載體）中嵌入水印，都需要利用原有載體中存在的冗余現象。對于文本而言，由于其句法結構存在冗余，同時，由于語言在長期發展過程中形成的同一意思可用不同句式表達的特點，所以可以通過句法分析來尋找水印的嵌入點。

2 依存句法分析水印算法

2.1 算法思想

依存句法分析［1］有一個重要特點：絕大多數句子以動詞為核心詞，少量句子以形容詞為核心詞；同時由于很多句中都存在主謂關系（SBV），即存在依賴于核心詞的名詞、代詞，圖1為依存句法分析示例。根據上述特點并結合與句子中核心詞有關的詞匯用法，考慮到副詞則是既有結構意義又有語用意義的詞，所以可以考慮利用其結構意義設計水印算法。

圖1 依存句法分析示例Fig.1 Example of dependency parsing

對于依存于核心詞的主謂關系（SBV），要通過遍歷找到構成主謂關系（SBV）的兩個詞中間是否還含有其他句法關系。如果除了狀中結構（ADV）外，不再含有其他關系，則可以考慮刪除狀中結構（ADV）來嵌入水印信息；否則結構過于復雜，計算時間過長，不予考慮。如果原來主謂關系（SBV）的兩個詞中間沒有其他句法關系，則可通過增加能構成狀中結構（ADV）的詞來嵌入水印信息。

由于核心詞主要為動詞和形容詞，依存于核心詞的構成主謂關系（SBV）的另一個詞主要是名詞和代詞；而依存于核心詞構成狀中結構（ADV）的主要是副詞，整個算法的關鍵就在于對副詞的刪減和增加上，所以要對副詞進行分類討論。

2.2 水印嵌入規則

針對副詞的水印嵌入原則，提出以下句子結構特點：

（1）相對程度副詞中的較高級、比較級、較低級中的各個詞可以增刪而基本不影響語義，而相對程度副詞中的最高級和絕對程度副詞都不能增刪而只能替換。

（2）程度副詞中的較高級、比較級、較低級中的各個詞可以增刪而基本不影響語義，而相對程度副詞中的最高級和絕對程度副詞都不能增刪去而只能替換。

（3）范圍副詞的句子中，如果是全部總括型，可以刪去；如果是部分總括型，不能刪去可替換。在含統計性范圍副詞的句子中，如果是全部統計，可以刪去；如果是部分統計型，不能刪去可替換。如果是含有限定性范圍副詞或外加性范圍副詞，可以刪去；

（4）基于語氣副詞特點提出對于表示或然語氣“也許、或許”等詞可以刪去；表示必然語氣“一定、必然、必定”等詞可以刪去；表示料定語氣“果然、果真”等詞可以刪去；表示必要語氣“必須、一定、務必”等詞以及表示僥幸語氣“幸虧、幸而、幸好”等詞不能刪去。

（5）對于不適合進行刪去處理的副詞，建立副詞同義詞詞典，采用替換的方法嵌入水印。

2.3 算法流程

圖2 基于句子分析的水印嵌入算法流程Fig.2 Flow chart of watermarking embedding algorithm

2.4 水印的嵌入和提取

水印嵌入的具體步驟如下：

Input：文本T，密鑰K1，密鑰K2，用戶信息。

Output：含水印文本T’。

（1）使用擁有者和用戶信息產生二進制水印序列W1，用密鑰K1對W1進行混沌調制，得待嵌入水印信號W。

（2）.利用分詞系統對T進行分詞，找到所有的句號、問號、驚嘆號。建立句子集合

（3）.對每個句子進行句法分析。找到每個句子的核心詞（HED），對核心詞前的句法結構進行分類，把含有SBV+ADV關系的句子合成一個子集S1，把其中構成ADV結構的副詞合并成一個子集C’。

（4）計算S1的句子數目N，N=num（S1）

（6）利用密鑰K2，把S1映射到與水印信息長度相同句子集合S2中。

（8）output T’

水印提取基本上是水印嵌入的逆過程，這里不再詳盡敘述。

3 實驗結果

本文選用了北大CCL語料庫中的句子，截止2009年7月其規模已經達到4.77億字。這里僅選取其現代漢語中的部分免費語料進行實驗，選取的語料共10684個分句。對10684個句子利用哈工大的LTP平臺進行分析，其中主要副詞及可進行替換的情況統計如表1。

從表1中的數據可以得出水印嵌入容量為9.75%，高于文獻［3］的算法。與文獻［4］進行魯棒性比較的結果如表2，從表中可以看出在實現比較容易的情況下，本文的方法在魯棒性方面不弱于已經獲得廣泛認同的基于TMR樹的方法。

表1 實驗文本中副詞格變換的統計Tab.1 statistics of adverbs exchanging in texts

表2 與其他算法魯棒性比較Tab.2 robustness comparison with other algorithms

4 結論

本文提出一種基于中文文本的句子層分析的信息隱藏方法，其特點是利用文本中大量存在的SBV?ADV結構，而對ADV結構中的副詞進行合理的替換和增刪通常對文本含義的表達不會產生較大的影響，這樣就可以實現將信息嵌入到文本中的目的。實驗結果表明本算法具有較好的魯棒性和較大的水印容量。

［1］姜傳賢，陳孝威.基于文本重要內容的魯棒水印算法［J］.自動化學報，2010，9（9）：1250-1256.

［2］孫星明，殷建平，陳火旺，等.漢字的數學表達式研究［J］.計算機研究與發展，2002，9（6）：707-711.

［3］Gupta G，Pieprzyk J，Wang H X.An attack-localizing watermarking scheme for natural language documents［A］.Proceedings of the ACM Symposium on Information，Computer and Communications Security［C］.Taipei，2006：157-165.

［4］Atallah M J,Raskin V，Crogan.Metal Natural language watermarking：Design，Analysis and Proof-of-Concept Implementation［A］.Proc of the 4th Information Hiding Workshop［C］.Pittsburgh，2001：193-208.