基于指代冗余的矩陣編碼文本水印算法*

吳玉環，曾國蓀

(1.同濟大學計算機科學與技術系，上海 201804;2.嵌入式系統與服務計算教育部重點實驗室，上海 201804)

0 引言

隨著網絡普及與發展，越來越多的文學、影視音樂等作品通過網絡出版的形式提供給消費者，然而網絡的開放性和共享性導致盜版技術和成本要求比較低，盜鏈、轉發等侵權現象嚴重，版權保護困難，其嚴重損害了作者和正版授權者的合法權益。當數字作品遭到非法分發或者盜用后，如何追蹤取證在后續版權保護中尤為重要。

為了解決數字產品版權保護問題，業內提出了許多方法，比如ID授權許可、在線認證以及EDRM識別鑒權等。除此之外，軟件水印、圖像水印、文本水印等水印技術也應用到數字版權保護中。目前針對音視頻版權保護的水印技術研究較多，也比較成熟，但針對文本保護的水印算法較為有限，主要有基于文本圖像、格式、字符結構、語義以及文本統計特征等方法。如李翔、丁文霞［1］提出的基于小波變換的文本不可見水印算法，該算法通過對文本圖像進行一級小波變換，通過隨機選擇換后的對角細節子圖中系數模值較大的點嵌入水印，該算法具有良好的魯棒性，但是由于載體對象是文本圖像，不能抵抗OCR掃描或是重錄入攻擊;鐘征燕、郭燕慧、徐國愛［2］提出了基于PDF文檔結構的數字水印算法，其利用PDF文檔行末標識符不會在文檔中顯示的特性嵌入水印，具有較好的隱蔽性，但該算法同樣不能抵抗重錄入攻擊;李慶誠、張振華和張金［3］提出了基于漢字結構的自然型文本水印算法，該算法通過漢字字形的拆分組合嵌入水印信息，具有較好的隱蔽性;林建濱、何路［4］提出了一種抗攻擊的基于中文同義詞替換的文本水印算法，該算法選擇詞匯相似度低義項相似度高的同義詞進行替換，有效地降低了機器消歧正確率，提高了基于同義詞替換的水印魯棒性;張宇、劉挺［5］提出的基于句法分析和語義的水印嵌入方法，在不改變文本原意的前提下，利用二次余數理論將水印信息插入到原始文本中，在適度的攻擊下不會破壞水印信息，但由于自然語言理解技術的有限，語義分析準確度不夠，會造成變換后文本上下文不連貫、不符合語境等情況;程玉柱、孫星明［6］提出的基于混沌映射的文本零水印算法，王曉龍、嚴承華［7］提出的基于漢字使用頻率的文本零水印算法以及舒娟娟、劉玉玲［8］提出的基于詞性頻率的中文文本零水印算法均利用文本統計特征構造水印信息，這些算法對文檔信息不作任何修改，構造的水印能夠有效地抵制針對文本文檔的復制、剪切、格式調整等編輯操作，具有較強的魯棒性和透明性，但由于零水印算法需要將水印信息注冊到第三方，與傳統的版權保護方法沒有實質區別。以上的文本水印算法多利用文本外在特征如格式、字符結構、同義詞(句)等，很少利用文本內容上的內在關聯性，本文通過分析文本中實體間的指代關系即下文所說的指代冗余，利用矩陣編碼嵌入水印，減少對載體文本的修改，并且克服了基于文本格式、同義詞替換等水印算法不能抵抗格式變換、重錄入、同義詞替換攻擊等對水印的破壞以及基于句型變換水印算法造成原文本可讀性的降低的問題，為文本水印算法研究提供新的思路。

1 文本和水印概念

本文的研究對象是文本文件。通常意義的文本由格式和內容兩部分組成，本文針對純文本即只包含文字內容無格式信息的文本開展研究。為了描述清楚，下面給出文本及文本水印的相關概念。

文本是由一定格式和文字內容信息構成的電子文件，如常見的TXT、Word、PDF等文件。純文本只包含文字內容而不包含格式信息，并且文字內容具有完整的句子結構和語義段落的自然語言，如一篇文章、一本小說等。純文本分為詞語、句子、段落3個層次結構。詞語是最基本的語義單位，其通過一定的語法規則構成句子，句子通過形式和內容上的聯系構成段落。句子是本文分析的主要對象，為了簡化分析，我們只考慮句子中主語和賓語兩種成分，對于復合句將其拆分成單句，并對其省略的成分進行補齊處理。因此，句子可記為:seni=gi(wsi，woi)，其中 wsi，woi∈W，gi∈G，wsi和 woi分別表示文本中第i個句子seni的主語和賓語，W是詞語集合，G是語法集合。

1.1 文本冗余

純文本主要有編碼冗余和內容冗余。編碼冗余與文本采用的編碼方式有關，修改編碼會對文本產生破壞，造成文本不可讀，因此很難直接利用編碼冗余;內容冗余是由于同義詞、同義句或是上下文關聯而產生的冗余，目前利用同義詞和句型變換的水印算法［4－5］會造成文本內容連貫性的變化，降低文本可讀性。通常文本內容都有指代［9］，包括回指和共指。回指是指當前的指示語與上文出現的詞、短語或句子存在語義關聯性，而共指則是指不同詞語指向真實世界中的同一參照體。指代是文本句子間一種關聯關系的描述，因此可認為指代是一種語言冗余。

下面給出本文用到的一些概念。

定義1 實體:是指文本出現的特定事實信息，如人物、組織機構、地理位置等，記作oi。文本中所有實體構成集合O={o1，o2…on}，下標表示實體在文本中首次出現的次序。

定義2 實體狀態:文本中通常用名詞、代詞、或省略描述實體，這3種描述形式稱為實體狀態，所有狀態構成實體狀態集，記為S={s1，s2，s3}，其中s1表示名詞描述形式，s2表示代詞描述形式，s3表示省略。

定義3 指代冗余狀態:如果當前實體狀態可以轉換成其它兩種狀態而不影響內容連貫性，則稱該實體狀態為指代冗余狀態，對于句子seni中實體ok的sj狀態是指代冗余狀態，則將其記作e=(seni，ok，sj)。

定義4 指代冗余狀態序列:文本中所有指代冗余狀態按先后次序構成的序列，稱為文本指代冗余狀態序列，記作 E=(e1，e2，…ei…，em)，下標 i表示指代冗余狀態在文本中出現的次序。

定義5 實體狀態編碼:是指對實體狀態集S中的狀態進行的二進制編碼。

定義6 指代冗余編碼序列:是指根據狀態編碼，將指代冗余狀態序列E中所有ei用其狀態編碼替換得到的編碼序列，記作Eb=(a1，a2…an)，其中ai∈{0，1}。

1.2 文本水印

定義7 文本水印:是版權所有者直接嵌入到文本或是修改文本特定區域，同時不影響原文本使用且不易感知和再次修改的標志信息。通過這些隱藏在文本中的信息，可以達到確認內容創建者、購買者或者判斷文本是否被篡改等目的。

與圖像、音頻水印載體冗余大、修改變換影響小相比，文本水印載體不具有這些優點，其有自身的特點:①編碼冗余小、變化敏感，少量的修改都會導致錯誤，使文本不再具有可讀性;②內容冗余分析困難，由于自然語言處理技術的有限性，很難對文本內容進行深入的分析，提取標記文本冗余成分較為困難;③內容變換操作復雜，通常的同義詞替換、句式變換，都很難保證上下文之間的銜接和風格一致。因此簡單的通過修改文本內容嵌入水印十分困難。

1.3 文本水印評價指標

水印評價指標用來評判水印算法的優劣水平，通常嵌入水印時希望水印算法能夠較少地修改載體同時提供較大的水印嵌入容量，并且希望嵌入的水印具有良好的抗攻擊能力，所以本文將文本利用率、文本修改率和水印魯棒性作為水印算法的評價指標。假設文本信息量為It，可用來編碼水印的信息量為I，為了嵌入信息量為Iw的水印w而需要修改文本的信息量為Ic，設文本遭受篡改信息量為Ia的攻擊時，其提取的水印信息為wa，則:

定義8 文本利用率:是指文本中可用來進行水印嵌入操作的信息的比例，記作η=。

定義11 相似度系數是指提取的水印與嵌入的水印之間的相似程度。在數字水印中通常使用NC系數衡量，記為:

定義12 水印魯棒性:是指當文本遭到攻擊篡改后，仍能提取水印的能力。利用提取水印與原水印的相似度和文本篡改率之間關系，來評價水印魯棒性。

2 文本指代冗余分析

目前已有較多的文本指代分析算法［10－12］，但嚴格的指代分析較為復雜，為了簡化分析，本文只考慮同個段落中的單句以及結構明顯的復合句的主語和賓語對應的實體構成的指代，通過指代冗余分析得到指代冗余編碼序列作為水印嵌入的直接載體。

2.1 實體狀態轉換條件和操作

為了確定指代冗余狀態，這里給出指代冗余狀態所需要滿足的條件和相互轉換的操作。如果文本中某個實體狀態滿足以下所有狀態轉換條件，即當前狀態可以轉換成任意其它狀態，則該實體狀態是指代冗余狀態，如圖1所示。

圖1 實體狀態轉移Fig.1 Entity state transition diagram

條件cond12:s1狀態不是第一次出現，即當前指代的實體在這之前出現過;

操作op12:用s2對應表述替換s1對應表述。

條件cond13:當前實體充當所在句成分與前面句子對應成分指代同一實體;

操作op13:s3對應表述替換s1對應表述。

條件cond21:無;

操作op21:考慮到語言習慣，可以用與s1不同的名詞進行替換，保證指代的實體一致即可。

條件cond23:當前實體狀態所在句子是獨立句式，與前一句相應成分對應同一實體;

操作op23:修改實體狀態描述，將其作為一分句與前面句子組合，改寫成復合句。條件cond31:s3出現在復合句的某一分句中;操作op31:用其指代對象的s1狀態的形式進行描述，并將該復合句拆寫成獨立句式。

條件cond32:無;

操作op32:s2對應表述替換s3對應表述。

2.2 指代冗余狀態序列提取

通過上節的討論可知，指代冗余狀態序列是嵌入水印的基礎，其提取的一般過程如下:①分析提取文本句子的主語、賓語成分，寫成seni=gi(wsi，woi)的形式;②根據實體定義從seni=gi(wsi，woi)中，提取實體并構建實體集合O={o1，o2…on};③將句子成分補齊，并將主語和賓語標注成對應的指代實體，記作seni=gi(os，ot);④分析句子主語和賓語的實體狀態，根據實體狀態轉換條件將指代冗余狀態寫成e=(seni，ok，sj)的形式;⑤將文本中所有指代冗余狀態按在文本中出現先后順序構成文本指代冗余狀態序列E=(e1，e2…，em)，從E中按照一定規則選擇其中一部ei構成新的序列Es，記為Es=φ(E)，為了描述方便，稱φ為子序列構造函數。

2.3 指代冗余矩陣

根據2.2節的分析結果，將Es中出現最少的狀態編碼為0，其余兩種狀態分別編碼為11和10，然后對Es中所有指代冗余狀態ei用狀態編碼替換，得到指代冗余編碼序列記作 Eb=(a1，a2…an)，其中ai∈{0，1}。在給定k時對序列 Eb每2k－1 bit進行分組，最后一組不足舍去，設總共可分t組，每組作為行向量，構成文本指代冗余矩陣如下:

其中稱M是文本的指代冗余矩陣構造函數。

3 基于指代冗余的水印嵌入算法

在對文本進行水印嵌入時，我們使用矩陣編碼［13］嵌入文本水印，該編碼方法是利用2k－1 bit信息對k bit原始信息進行編碼，而最多只需要修改1 bit，以降低載體利用率來減少對載體的修改。實際應用中，通過選取合適的k值，在載體利用率和載體修改率之間達到一個平衡。如果直接使用矩陣編碼會導致水印覆蓋的問題，即攻擊者可以構造另外一個水印，通過相同的方法嵌入后完全覆蓋原來的水印，導致原水印的徹底破壞。為了抵抗水印覆蓋問題，我們選擇指代冗余狀態子序列構造指代冗余矩陣，這樣可以有效提高水印的魯棒性。

3.1 算法主要思想

我們通過對文本句子的主語和賓語進行指代冗余分析，得到文本的指代冗余狀態序列，利用該序列和狀態編碼，構造指代冗余矩陣作為嵌入水印的直接載體，通過矩陣編碼計算指代冗余矩陣中需要修改的元素位置，修改后對應到指代冗余狀態序列中，找到載體文本的對應位置，再根據實體狀態編碼和狀態轉移操作修改載體文本，最后得到含有水印的文本，完成水印嵌入。

3.2 水印信息的編碼和計算

假設水印信息為w，其可以是包含版權信息的文字、圖片或是音頻，將其對應的二進制信息每k bit為一組，作為行向量構成水印矩陣W，不足的用0補齊，記作:

在對指代冗余矩陣使用矩陣編碼嵌入水印信息時，需要確定指代冗余矩陣的修改位置，涉及的矩陣

運算定義如下:

式中，B是用于矩陣編碼的已知矩陣，構成其第i行的行 向 量 (bi，1，bi，2，… bi，k)滿 足·bi，j=i ，bi，j∈{0，1};矩陣 C 的元素由式(3)確定:

這里·和⊕分別是“與”和“異或”運算。

3.3 指代冗余水印嵌入算法

前面給出了指代冗余水印算法涉及到的操作和運算，下面給出水印嵌入算法的主要步驟:①首先對文本進行指代冗余分析得到文本指代冗余矩陣MT;②根據水印矩陣W和文本指代冗余矩陣MT，利用矩陣編碼進行修改位計算:L=f(C，W)=f(MT⊕B，W);③根據L對MT相應位置進行修改得到MTw;④利用狀態編碼將MTw寫成指代冗余狀態序列Ew=(ew1，ew2…，ewm)，根據指代冗余狀態的轉換操作修改原文本相應實體狀態，完成水印嵌入。

設文本為T，水印信息為w，子序列構造函數為φ，矩陣編碼的參數為k，水印嵌入算法的偽代碼描述如下:

算法1:指代冗余水印嵌入算法

輸入:文本T，水印w，子序列構造函數為φ，矩陣編碼的參數為k。

輸出:嵌有水印w的文本Tw。

值得說明的是提取水印是嵌入水印過程類似，首先分析得到嵌入水印后的文本指代冗余矩陣MTw，水印可直接計算為W=MTw⊕B，這里不再贅述。

4 應用和案例分析

前面給出了水印算法的主要過程，下面以2014年01月15日《人民日報》上的文章“人生‘坐票’，屬于不懈追求者”為例，說明該算法的性能和效果。

該文本正文總共705個字符(不含標點和空格)，通過對文本分析，得到33個指代冗余狀態，對其編碼如表1所示。

表1 指代冗余統計和編碼Table 1 Coreference redundancy statistics and coding

(1)文本利用率和修改率

分別取k=2、3和4，計算文本利用率和修改率，如圖2所示。

圖2 文本利用率和修改率Fig.2 Text availability and modification rate

基于漢字結構的自然型文本水印算法［3］文本利用率和修改率約為13%，基于同義詞替換和句型變換的水印算法［4－5］的文本利用率和修改率約為2.5%。當文本滿足嵌入水印容量需求時，相同嵌入率情況下本文算法修改率更低，具有更好的優勢。

(2)魯棒性評估

通常的掃描攻擊、重錄入攻擊、格式變換以及同義詞替換不會改變主語及賓語的實體狀態，因此不會影響水印信息;對于刪除、句式變換會改變實體狀態序列，會導致文本水印的破壞，但是這類破壞會較大影響文本的可讀性，通常情況較少使用。這里實驗采取的是隨機選擇若干句子改變其句式或者添加無關語句的多次重復實驗，得到文本篡改率ηa與相似度系數的關系，如圖3所示。

圖3 相似度系數NC與文本篡改率ηa關系Fig.3 Similarity NC and tampering rate ηa

在較低篡改率情況下，該算法對句子變換或是添加具有較好的魯棒性;隨著篡改率不斷增大，提取的水印與原水印相似度逐漸趨于穩定。為了進一步提高水印魯棒性，實際應用中可以采取對文本分塊、分區等形式嵌入或者選擇文本關鍵語句構造指代冗余矩陣，進一步增強水印抗破壞能力。

5 結語

本文通過分析文本內在聯系，即文本中句子主語及賓語對應的實體關系，利用指代冗余狀態在一定條件下可以相互變換來嵌入水印信息，減少了由于文本內容變換產生的文本上下文不連貫、不符合語境等情況，具有較低的文本修改率和較好的魯棒性，為文本水印算法提供了新的思路。目前只考慮了句子主語和賓語對應實體構成的指代冗余狀態，在以后研究中可以擴展至整個句子所有的實體指代冗余狀態，以提高文本利用率。

［1］李翔，丁文霞.基于小波變換的文本不可見水印算法［J］.通信技術，2012，45(04):31－33.LI X，DING W.Text Invisible Watermarking based on Wavelet Transform ［J］.Communications Technology，2012，45(4):31－33.

［2］鐘征燕，郭燕慧，徐國愛.基于PDF文檔結構的數字水印算法［J］.計算機應用，2012，32(10):2776－2778.ZHONG Zheng－yan，GUO Yan－hui，XU Guo－ai.Digital Watermarking Algorithm based on Structure of PDF Document［J］.Journal of Computer Applications，2012，32(10):2776－2778.

［3］李慶誠，張振華，張金.基于漢字結構的自然型文本水印算法［J］.計算機應用研究，2009，26(04):LI Qing－cheng，ZHANG Zhen－hua，ZHANG Jin.Natural Text Watermarking Algorithm based on Chinese Characters Structure［J］.Application Research of Computers，2009，26(4):

［4］林建濱，何路.一種抗攻擊的中文同義詞替換文本水印算法［J］.西北大學學報:自然科學版，2010，40(03):433－436.LIN Jian－bin，HE Lu.An Anti－Attack Watermarking based on Synonym Substitution Algorithm for Chinese Text［J］.Journal of Northwest University:Natural Science E-dition，2010，40(3):433－436.

［5］張宇，劉挺.自然語言文本水印［J］.中文信息學報，2005，19(01):56－62.ZHANG Yu，LIU Ting.Natural Language Watermarking［J］.Journal of Chinese Information Processing.2010，40(3):433－436.

［6］程玉柱，孫星明.一種新的基于混沌映射的文本零水印算法［J］.計算機應用，2005，25(12):2753－2758.CHENG Yu－zhu，SUN Xing－ming.Text Zero－Watermarking Algorithm based on Chaotic Mapping［J］.Computer Applications，2005，25(12):2753－2758.

［7］王曉龍，嚴承華.基于漢字使用頻率的文本零水印算法［J］.計算機應用，2009，29(09):2366－2368.WANG Xiao－long，YAN Cheng－hua.Text Zero－Watermark based on Use Frequency of Chinese Characters［J］.Journal of Computer Applications，2009，29(9):2366－2368.

［8］舒娟娟，劉玉玲.基于詞性頻率的中文文本零水印算法［J］.計算機應用，2012，31(A02):103－105.SHU Juan－juan，LIU Yu－ling.Chinese Text Zero－Watermark based on Frequency of Part－of－speech［J］.Journal of Computer Applications，2012，31(A02):103－105.

［9］Van Deemter K，Kibble R.On coreferring:Coreference in MUC and Related Annotation Schemes［J］.Computational linguistics，2000，26(04):629－637.

［10］張威，周昌樂.漢語語篇理解中元指代消解初步［J］.軟件學報，2002，13(04):732－738.ZHANG Wei，ZHOU Chang－le.Study on Meta－Anaphoric Resolution in Chinese Discourse Understanding［J］.Journal of Software，2002，13(4):732－738.

［11］董國志，朱玉全，程顯毅.中文人稱代詞指代消解的研究［J］.計算機應用研究，2011，28(05):1774－1779.DONG G Z，ZHU Y Q，CHENG X Y.Research on Personal Pronoun Anaphora Resolution in Chinese［J］.Application Research of Computers，2011，28(5):1774－1779.

［12］熊皓，劉群，呂雅娟.聯合語義角色標注和指代消解［J］.中文信息學報，2013，27(06):58－68.XIONG Hao，LIU Qun，LV Ya－juan.Joint Semantic Role Labeling and Coreference Resolution［J］.Journal of Chinese Information Processing，2013，27(6):58－68.

［13］CRANDALL R.SomeNotes on Steganography［EB/OL］.Posted on Steganography Mailing List，1988(2010－02－15)［2014－01－16］.http://os.inf.tudresden.de/～ westfeld/crandall.pdf.