基于指代冗余的矩阵编码文本水印算法*

吴玉环，曾国荪

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