改进的同义词替换算法
一种改进的基于同义词替换的中文文本信息隐藏方法
作者：甘灿，孙星明，刘玉玲，向凌云
（湖南大学 计算机与通信学院，湖南 长沙410082）
1 基于同义词替换的隐藏算法
基于同义词替换的方法是目前中文自然语言信息隐藏方法中使用最为广泛的方法。在同义词替换中，通过选择载体文本中在某一同义词库中出现的词，并根据一定的编码方式对这些词进行同义词替换，以此来嵌入隐藏信息。这里所谓的同义词，一般定义为“同一种语言中，在一些或全部的义项中具有相同或基本相同的意思的两个或多个词”。若设载体文本为C，隐秘信息为M，隐藏信息后的文本为S，同义词库为D，则有嵌入函数e()和提取函数d()，使得：
e(C,M,D)=S， d(S,D)=M，并且C和S在语义上保持不变。
嵌入函数定义如下：
1） 将隐秘信息M转化为二进制位串，并附加额外的长度信息和校验码等；
2） 对载体文本C进行自动分词；
3） 遍历C中的每一个词，判断是否在同义词库D中，若在，则根据该词所在词组词的个数以及当前所需嵌入的二进制位串，按一定的编码方式进行同义词替换；
4） 重复第3）步，直到完成隐秘信息的嵌入。如果遍历完所有的词还未完成，则嵌入失败。
提取函数定义如下：
1） 对文本S进行自动分词；
2） 遍历S中的每一个词，判断是否在同义词库D中，若在，则根据该词所在词组的位置以及相应的解码方式，得到嵌入的二进制位串；
3） 重复第2）步，根据长度信息和校验码恢复出隐秘信息M。
从上述算法的流程可以看出，现有的基于同义词替换的隐藏算法存在一个缺陷，由于很多同义词都只是部分的义项相同，从而可能会出现不等价的替换，导致替换后的文本出现语义不一致或语义混乱等，降低了算法的隐蔽性和抗检测性。
2 改进的同义词替换算法
为了方便描述，首先给出如下定义：
定义1 完全可替换词组：两个及其以上的所有词义完全相等的同义词称为一个完全可替换词组。
定义2 不完全可替换词组：两个及其以上的存在部分词义不相等的同义词称为一个不完全可替换词组。
定义3 歧义词组：两个及其以上的在同一词性时存在部分词义不相等的同义词称为一个歧义词组。
现有基于同义词替换的隐藏算法一般都采用对同义词进行直接替换的方法，但对于不完全可替换词组，则可能出现不等价替换，从而引起替换后的句子语义混乱。本文针对这点对算法进行改进，首先对同义词组进行分类，然后对歧义词组中的同义词，根据词的上下文语境判断是否替换。
3 同义词组的分类
首先以《同义词词林》为基础，从中提取出完全可替换和不完全可替换的词组，建立成一个同义词库。词林中存在很多生僻词，有的同义词组内词之间使用频率相差很大，这样会降低算法的隐蔽性。因此根据现代汉语词语的词频统计表，对同义词库进行整理，使每组同义词的词频相近。同时为使每组同义词不相交（否则会出现编解码错误），删除了重复出现的同义词，最后得到一个约15000词的同义词库。
为了抽取出同义词库中的歧义词组，我们利用《知网》对同义词词组进行分类。《知网》是一个以汉语和英语的词语所代表的概念为描述对象，以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库。在《知网》中，把若干与概念有关的义原组成的集合来解释概念，而这个义原集合称之为一个义项，一个词可以有多个义项。利用知网的义项对同义词词组中的词语进行标注，然后比较各个词之间的义项，从而对同义词词组进行分类。
以两个词的同义词词组为例，假设为{s1, s2}，它们的词性集分别为Ps1、Ps2，相应的义项集为Cs1 = {Ci,p | p € Ps1}、Cs2 = {Ci,p | p € Ps2}，则同义词词组可分为以下三类：
第一类：Cs1 = Cs2，即{s1, s2}为完全可替换词组；
第二类：Ps1 ≠ Ps2，但当词性p´ € Ps1 Π Ps2时，s1与s2的义项全部相等。虽然{s1, s2}为不完全可替换词组，但词性相同时，s1与s2完全可替换；
第三类：p´ € Ps1 Π Ps2，当词性p´为时，s1与s2只有部分义项相等。则{s1,s2}为歧义词组。
按照以上的分类规则对同义词库中的5600组同义词进行了分类，其中第一类约占35％，第二类占10％，第三类占55％。由此可见，完全相等的同义词只占一小部分，因此对大部分的属于歧义词组的同义词需要根据上下文语境判断是否可以替换。
4 评价模型
对于一个属于歧义词组的同义词w，其上下文语境是指句子中在其周围出现的词的集合。实际上，w的语义特征的确定只跟集合中的部分词相关，而与其它的词不相关。因此若抽取出相关的词，就可以缩小上下文的范围，降低问题的复杂度。由于词性特征之间有较确定的搭配关系，因此可以通过对句子进行句法分析得到句法树，再根据句法搭配关系从中得到与w相关的词，称为w的搭配词。本文通过使用依存句法分析来获取同义词的搭配词。
依存句法是由法国语言学家L.Tesniere最先提出。它将句子分析成一颗依存句法树，描述出各个词语之间的依存关系。也即指出了词语之间在句法上的搭配关系，这种搭配关系是和语义相关联的。例如句子“会议宣布了首批资深院士名单。”的依存句法树如图1所示：
图1 依存句法树
从图1可以看出，词“宣布”支配“会议”、“了”和“名单”，故可以将这些支配词作为“宣布”的搭配词。
假设句子S的词序列为W1…s1…Wn，s1属于歧义词组{s1,s2}， s1在句中的搭配词集为
，这里
。令P(s2 | w´i)是在已知搭配词w´i的条件下s2出现的概率，则
(1)
通过对实际的汉语语料进行统计，可以得到上式中的参数。如果N(s2, w´i)表示s2与w´i互为搭配词在训练语料中出现的次数，N(w´i)表示w´i在训练语料中出现的次数，根据最大似然估计原理，可以近似的认为：
(2)
令Score s2为s2与Wde中各个搭配词共现的概率之和，即：
(3)
则当的值越大，与在中可替换的可能性就越大。故可将作为能否替换句子中的的评价值，当它大于某一阈值时，则认为可以进行替换，否则不能。
5 算法流程
在对载体文本进行分词和词性标注之后，对文本中每一个同义词，首先判断能否进行同义词替换，然后才利用同义词替换嵌入隐藏信息。算法1描述了具体的判断步骤。
算法1 同义词替换判别算法
1）对载体文本中的每一个同义词，根据同义词库的标识，判断它属于哪一类同义词词组。若属于第一类则可以替换；若属于第二类则转步骤2）；若属于第三类则转步骤3）；
2）根据同义词库中标识的所在的词组词义等价时的词性集合，若这时的词性属于该集合，则可以替换，否则不能替换；
3）对所在的句子进行依存句法分析，抽取搭配词集；
4）根据公式(3)和训练语料中得到的参数，分别计算所在同义词组其它词的评价值；
5）若每个的值都大于阈值，则可以替换，否则不能替换。