一种改进的维吾尔语句子相似度计算方法

卡哈尔江·阿比的热西提，吐尔根·依布拉音，姚天昉，艾山·吾买尔，艾山·毛力尼亚孜

(1. 上海交通大学 计算机科学与工程系，上海 200240； 2. 新疆大学 信息科学与工程学院,新疆 乌鲁木齐 830046)

1 引言

计算句子相似度在基于实例的机器翻译(Example Based Machine Translation，EBMT)中起到重要的作用。自从基于实例的翻译方法提出以来[1]，句子相似度计算已经成为该方法的一个研究重点。维吾尔语-汉语基于实例的机器翻译中维吾尔语句子的相似度计算也是一个难点。维吾尔语属于阿尔泰语系突厥语族西匈语支，在结构特点上，属于黏着语。它是通过在词干上附加各种构词和构形词缀而改变词汇意义和语法意义的一种语言。这种特点对于维吾尔语句子相似度计算带来了一定的困难。文献[2]提出了一种计算维吾尔语句子相似度算法，先基于词形特征选出粗选相似句子，然后进一步精选并计算相似度。该方法虽然考虑了维吾尔语单词词频特征对不同的单词给予不同的权值，但没有考虑维吾尔语的黏着性，即没有进行词干提取，并且对较长的句子或组成词频低的句子相似度计算的偏较差大，这反而降低了系统的翻译质量。

我们的学校

你们的功课

有时动词可用交互—集合态形式，也可以用基本态形式。如：

您的孩子们来了。

有时作定语的所有格附加成分要省略。如：

从以上的例子等号两边的短语或句子的形式不一样，但意义、用法完全相同。鉴于以上维吾尔语的独特现象，计算维吾尔语相似度时先对单词进行词干提取是必要的。

本文对文献[2]的粗选算法进行了修改，将倒排索引文件中单词的频率，即词干频率，也存到链表中，当粗选时仅考虑出现频率较低的单词，这样可以去掉频率很高的单词，因为这些高频单词影响粗选句子的多样性，降低EBMT系统的效率且对文献[2]提出的精选算法进行改进，将维吾尔语的黏着性特点考虑进去，将维吾尔语进行词干提取，并在计算相似度方面采取了词形、词序、单词间的夹角和句长结合的方法，且进行简单的结构相似性分析，实验结果表明该方法比较接近人工评分的句子相似度。

2 EBMT系统的句子相似度计算模块

2.1 倒排索引的建立

维吾尔语句子相似度计算模块作为维汉 EBMT 系统的重要部分，将对齐维吾尔语和汉语句子分别存到两个文件，并对维吾尔语句子文件建立倒排索引。倒排索引的格式为：

词干词干频率句子编号...

将倒排索引存到另一个文件作为维吾尔语实例库的索引。词干频率的计算方法和文献[2]的计算词频方法相同。用文献[4]方法对维吾尔单词进行词干提取。

2.2 对输入维吾尔语句子进行粗选

为EBMT系统提供相似的、多样的句子集，当粗选句子时仅考虑已词干提取好的输入句子单词、单词的字符串长度和单词在实例库中出现频率。即出现频率大于阈值(1.5)的单词不参加粗选，并在粗选集中输入句子单词，且其字符串最长的句子排在最前面,系统默认粗选100个句子。

2.3 几种相似度计算方法

已选好的100个句子进行了相似度计算，先根据句子编号，读取相应的句子，并对句子进行词干提取[4]和词性标注[5]。

2.3.1 词形相似度

用Words(A)表示输入句子A的单词集合,用Words(A)i表示该集合的第i个元素，Len(W)表示W的字符串长度，Match(A，B)表示输入句和实例句中相似单元集合，即相似单词。输入句子A和实例句子B的词形相似度SimWord(A,B)。由以下的公式来表示：

2.3.2 词序相似度

仅计算词形相似度，不能正确地判定句子的相似度。例如：

输入句子：

实例句子：

上述句子中SimOverlap(A,B)=SimOverlap(A,C)。

所以需要考虑每个单词的顺序。在计算词序相似度时要不仅考虑句子的有序度，而且考虑句子的无序度。PositionA表示Match(A，B)的相似单元在句A中的位置，PositionB表示句子B中顺序排列的相似单元对应句A相似单元的位置。用Entropy(A，B)表示PositionA中相似单元的排列顺序的相邻关系在PositionB被打乱的程度。再用Order(A，B)表示PositionB中相邻相似单元有序程度。句子A，B的词序相似度SimOrder(A,B)由下述公式表示：

(2)

λ的经验值为0.5。

2.3.4 句长相似度

在进行句子相似度计算时，实例句和输入句的长度相差较大时，相似度较低，因句长差引起的相似度降低的公式如下：

(3)

2.3.5 夹角

有些句子中可能词形、词序相似度和句长相似度都相同，但句子的相似度不一样。比如：

输入句子：

实例句子：

上述句子中不仅SimOrder(A,B)=SimOrder(A,C)，而且SimOrder(A,B)=SimOrder(A,C)和SimLenDiffe(A,B)=SimLenDiffe(A,C)。实际上实例句子C和 输入句子A的相似度远远大于实例句子C与输入句子A。所以需要再添加相似度夹角的计算。相似度夹角反映输入句中相邻的相似单元在实例句中被分隔的程度。用AngleNum(A，B)表示相似单元夹角的个数，AngleSize(A，B)表示所有夹角中间隔匹配单元相似单元的夹角值[6]，则计算公式为：

(4)

λ的经验值为0.5。

2.3.6 基于词的相似度

计算基于词的相似度总公式为：

该公式中的α1,α2,α3,α4可以通过遗传算法确定。本文根据观察，分别取值为0.6,0.2,0.1,0.1。

2.3.7 简单的句子结构相似度

为了代码和计算方式的重用，本文对结构相似度同样使用了以上公式(5)，只将单词替换为该单词的词性标注。

2.3.8 最终句子相似度

对结构相似度同样适用以上的公式，只将单词替换为该单词的词性标注。

根据经验，θ1的取值为0.7，θ2的取值为0.3。

3 实验

到目前为止还没有评价维吾尔语句子相似度的标准数据。为了评价该论文提出的句子相似度方法，我们构造了20个句对，并要求22位参与者分别对每一个句对相似度进行打分。句子是从我们的标准语料库中随机选择的。

3.1 实验过程

我们的测试人员母语为维吾尔语，并且从小学到初中或高中在母语学校上学的22位硕士生、博士生。

3.2 实验结果

通过用同样的语料库，对三种方法分别进行比较，方法A为文献中的方法，方法B为仅通过公式(6)计算句子相似度，方法C为通过公式(7)计算句子相似度。图1为通过三种方法计算以上的20个句对的相似度、计算值和评分人员的相似度值均值的皮尔逊相关系数r。从图中可以看出，方法C比方法A和B更好地接近人工的评分值。

表1 20个句对中的一部分

图1 皮尔逊相关系数

4 总结和展望

通过对维吾尔语进行词干提取可以提高句子相似度计算的准确度，更好地接近人工的评分标准。并且对维吾尔语进行简单的结构相似度计算可以进一步提高准确度和进一步接近人工的评分标准。但本文采取的方法还存在不足，如果计算简单的结构相似度时可以对不同的词性赋予不同的权值，可以进一步地体现出不同词性对句子相似度的不同贡献。扩大测试集的规模设计能够更好地构造测试集和改进测试方法，努力构造维吾尔语句子相似度计算的标准参考测试集。

[1] NAGAO M. A framework of a mechanical translation between Japanese and English by analogy principle [C]//A.Elithorn et al eds. Artificial and Human Intelligence. North-Holland: NATO Publication, 1984: 173-180.

[2] 田生伟, 吐尔根·依布拉音, 禹龙, 等. 一种维吾尔语句子相似度算法的研究 [J]. 计算机工程与应用, 2009, 45(26): 144-146.

[3] 易坤琇, 高士杰. 维吾尔语语法 [M]. 北京: 中央民族大学出版社, 1998: 25-27.

[4] WUMAIER A, YIBULAYIN T, KADEER Z, et al. Conditional random fields combined FSM stemming method for Uyghur [C]//ICCSIT 2009，2009.

[5] 买合木提·买买提, 吐尔根·依布拉音. 基于N-gram的维吾尔语词性标注研究[C]//第二届全国少数民族青年自然语言处理学术研讨会论文集，2008.

[6] 龙昊, 张斌. 双语知识库中相似实例的多策略提取机制的研究 [D]. 沈阳: 东北大学, 2006.