文本切分是自然语言处理中的第一步, 也是关键的一步。采取何种方法及切分难易程度, 在不同语言环境下有所不同, 但最终目的是一样的, 即从文本中获取能表达具体、完整语义的语言单元的集合。这些语言单元在很多情况下是突破词语概念界限的语义串^[1-2], 是文本中上下文任意多个连续字符(字或词)的稳定组合, 是结构稳定不可分割且语义完整的语言单元(如固定搭配、习语、对偶词等具有词汇意义和语法意义的模式串^[3-4]、词组或短语^[5]、复合词或领域术语^[6]以及命名实体等)。

在文本中, 句子可以表达完整、连贯、易于理解的语义, 而语义串蕴含句子的关键信息。因此, 用语义串表示文本, 可以有效地刻画文本主题^[7], 构造泛化能力更强、更紧凑的文本模型^[8-9], 从而可以提高相关算法性能及文本处理效率。因此, 如何识别语义串边界并完整获取, 已成为文本挖掘领域中的关键问题^[10-11]。

中文信息处理领域中, 分词是研究历史最悠久的问题, 经过多年的研究, 中文分词已出现多种较成熟的技术和实用分词工具。但是, “文本海啸”的到来, 对中文自动分词研究提出一系列新的课题, 尤其是新词边界的正确识别及分词系统对开放环境的适应性及健壮性的需求日益突出。

作为文本中上下文任意多个连续字符(字或词)的稳定组合, 语义串是语义及结构完整的语言单元, 其内部结合紧密, 不可分割。因此, 以相邻汉字之间的结合程度作为切分依据, 或将它作为补充手段来消除歧义, 在中文分词和新词识别方法中已起到很好的作用。孙茂松等^[12]从大规模生语料中获取汉字二元信息, 用互信息及t-测试差的线性叠加值来衡量相邻汉字之间的结合能力, 并设计了一种无词表及无指导学习的自动分词算法。王思力等^[13]用双字耦合度和t-测试差的线性叠加值来消除分词中的交叉歧义, 但他们是从熟语料中获取二元模型。费洪晓等^[14]分别用N-gram、互信息及t-测试3种统计量来判断双字构成词的可能性。王芳等^[15]用互信息定量估计相邻两个基本词间的结合可信度, 提出一种基于可信度的中文完整词自动识别方法。何赛克等^[16]将字串邻接变化数(accessor variety)引入基于条件随机场的中文分词系统, 提高了分词系统性能。基于词典的分词方法mmseg中, 蒋建洪等^[17]用互信息来度量并过滤非邻接词, 使分词系统性能得到提高。

基于上述研究, 本文提出一种基于词间关联度度量的维吾尔文本自动切分方法。所提方法接近于孙茂松等^[12]和王思力等^[13]的研究, 但又有区别。首先, 他们都是用两种基本统计量的线性融合作为组合统计量, 度量相邻汉字之间的结合紧密度, 目的是提高现有中文分词系统的精度。本文引入邻接对熵(dual adjacent entropy), 并将t-测试差(difference of t-test)、互信息(mutual information)及邻接对熵的线性融合作为一个组合统计量dmd, 用以度量相邻维吾尔文单词之间的结合紧密程度。本文目的是从已分好词的单词序列(以空格隔开的词序列)中识别出最终的切分边界, 从而获取文本中结构及语义完整的语言单元。除此之外, 本文还将维吾尔文不同词性之间的结合规律作为一种规则, 融入词间位置判断中, 以便提高语义串识别精度。

1 维吾尔文分词及存在的问题

维吾尔文是突厥语族中的一个成员, 又属于阿尔泰语系, 是一种拼音文字, 具有黏着语特性。从表面上看, 维吾尔文词在文本中以空格与上下文隔开, 因此, 一直认为维吾尔文中不需要分词。在各种文本处理中也都以空格作为自然分隔符进行分词(简称空格分词), 以词为特征表征文本。

例1  去北京的火车从哪个车站出发？

例1由6个词组成, 经过词干复原处理后再进行空格分词, 对应的中文也经ICTCLAS分词(省略了功能词), 得到的词序列(维吾尔文书写顺序为从右到左)如图 1所示。

从分词结果上看, 空格分词对以上句子是有效的, 切分出来的词都能作为基本的语义单元运用。但对于以下几个新闻标题, 这种分词结果几乎是错误的。

例2  科学家研制出禽流感病毒。

例3  首批全国政协委员抵达北京。

例4  奥巴马连任面临就业问题挑战。

例2~4采用空格分词的结果见图 1。

根据一个词语的最小语义完整性, 例2应该被分为5个词语(带下划虚线的串), 但是空格分词把句子分成8个词。然而, 二词串②, ④和⑤都是常用实词, 是两个单词的稳定组合, 不可分割。例3中的二词串①, ③, ⑥和例4中二词串③, ④, ⑥也都是结构稳定、语义完整的常用实词, 不能以空格分开提取。

维吾尔文中能表达一个最基本的、具体而完整语义的语言单元, 在很多情况下不仅仅是一个以空格隔开的单词, 而是它与上下文若干个词的稳定组合。维吾尔文中能表达一个完整语义或者说在实际语料中能充当一个实词的串, 可分为以下两类。

定义1  单词语义串是一个维吾尔文单词, 即一个无空格字母串, 语义完整且独立运用, 可用空格分词切分得到。比如, 例1中以空格分割的都是单词语义串。

定义2  多词语义串是若干个维吾尔文单词的稳定组合, 并且满足如下条件: 1)语义完整, 在真实语料中充当一个实词, 不能以空格分开; 2)结构稳定, 在大规模语料中具有较高的流通度, 是独立运用的语言单元。

随着维吾尔文文本挖掘相关领域研究工作的不断深入及更广范围的开展, 空格分词方法开始暴露出其潜在的缺陷和局限性, 主要表现如下。

1)在维吾尔文Web搜索中, 由于空格分词没有考虑切分单元的语义完整性和结构完整性, 因此获取的单词难以在文本标引中发挥关键词的作用^[18]。另外, 空格分词还会导致组合歧义及交叉歧义的产生, 并出现低查准率^[19-20]。

2)中、英文文本聚类和分类中, 常用词特征来表征文本, 聚类和分类效果也比较满意。同样以词特征表征文本并用性能最好的学习算法, 维吾尔文文本聚类和分类效果却远不及中文和英文^[21]。这是因为, 文本中表示关键信息的语义串被空格分词拆分为与其语义完全不符的若干个字母串, 因此不仅不能提取更具有表征能力的文本特征, 反而提高了特征空间的维度, 甚至导致大量冗余、不相关(噪音)甚至类间交叉特征的出现。冗余特征的存在会降低学习算法的效率, 不相关特征(噪音特征)的存在会损害学习算法的性能^[22], 类间交叉特征的存在会极大地降低聚类和分类准确率^[23]。

除搜索、聚类和分类外, 空格分词在机器翻译、主题词提取、维吾尔人名(名在前姓在后, 以空格隔开)、地名、机构名等命名实体识别以及新词识别等文本处理过程中也会成为一个瓶颈。

2 词间关联度度量

本文的主要思路是, 从第一个单词开始扫描待处理文本中的词序列, 并用一个统计量S去观察相邻单词间的结合程度。如果S > T(T为阈值), 则保留它们之间“连”的状态, 否则插入一个分隔符(维吾尔文单词之间以空格隔开, 因此本文以字符“|”作为分隔符)将它们分开, 这时它们之间是“断”的状态。例如, 一个有n个单词的文本的词序列为W₁ W₂ W₃...W_i-1 W_i...W_n-1 W_n, 则基于统计量S的词间连、断判断如图 2所示。最后以分隔符“|”进行切分, 就得到文本中的所有语义串。其中, 统计量S是从大规模生语料中学习计算得出。

本文所用语料都来自网络和正式出版物, 包括从互联网收集的人工分类文本(共20类)、新疆日报2008年3和4月份全部内容、出版物8本(有关文学、社会、法制、经济等)。在实验和算法验证中, 我们将大语料分为3个语料库, 每个语料库都包含以上大语料中一定比例的内容。1)生语料库URC (Uyghur Raw Corpus), 共含维吾尔文单词及标点9443290个, 未经标注; 2)开发集USC₁(Uyghur Segmented Corpus), 共含维吾尔文单词及标点15708个, 经人工标注; 3)测试集USC₂, 共含维吾尔文单词及标点154411个, 经人工标注(以上语料均由新疆大学智能信息处理重点实验室提供)。实验中, 除对文本语料进行词干提取处理外, 无任何特殊处理和人工干预, 算法所需要的所有统计信息直接从生语料中获得。

在实验和算法验证中, 我们用单词间的“连”和“断”的判断准确率α来调整阈值T和其他参数, 直到算法给出最好的性能。准确率α的定义为

$ \alpha = \frac{{{\rm{PosCoun}}{{\rm{t}}_连}({W_{i-1}}, {W_i}) + {\rm{PosCoun}}{{\rm{t}}_断}({W_{i-1}}, {W_i})}}{{{\rm{PosCount}}({W_{i-1}}, {W_i})}}, $

(1)

其中, W_i-1和W_i是文本中相邻的词对, PosCount_连(W_i-1, W_i)表示正确判断为“连”的词间位置数, PosCount_断(W_i-1, W_i)表示正确判断为“断”的词间位置数, PosCount (W_i-1, W_i)表示被处理文本中所有的词间位置数。

2.1 基本统计量:互信息(mi)

在一个维吾尔文文本以空格隔开的有序词序列中, A和B是相邻的词对, 则根据互信息原理, 单词A和B之间的互信息可定义为

$ {\rm{mi}}(A, B) = {\log _2}\frac{{P(A, B)}}{{P(A)P(B)}}, $

(2)

其中, P(A, B)为词对A和B在大规模语料库中出现的概率, P(A)为单词A出现的概率, P(B)为单词B出现的概率。假定它们在语料库中出词频分别为count (A), count (B)和count (A, B), n是语料库中的词频总数, 则有

$ \left\{ \begin{array}{l} P(A, B) = \frac{{{\rm{count}}(A, B)}}{n}, \\ P(A) = \frac{{{\rm{count}}(A)}}{n}, \\ P(B) = \frac{{{\rm{count}}(B)}}{n} \end{array} \right. $

(3)

互信息mi (A, B)反映相邻词对A和B之间的关联程度。mi (A, B)越大, 表明A和B之间的关联程度越紧密, 如果mi (A, B)大于给定的一个阈值T_mi, 则可以认为A和B之间是不可分割的。

我们以生语料库URC训练维吾尔文单词Bigram模型, 并以USC₁为对象考察互信息关于单词间连、断的分布情况。互信息变化范围在-6.75~21.01之间, 当阈值T_mi取4.0时(根据URC统计得到的mi均值为3.63), α值最高可达75.26%。例如, 对于例5中各位置的判别基本上是正确的(如图 3(a), “|”为分隔符)。

例5  这种软件可以监测硬盘状态。

从式(2)可以看出, 互信息反应的是相邻词对A和B之间的静态结合能力, 而不考虑它们的上下文, 因此仅仅参考互信息这个基本统计量, 也会出现错误的连、断判断。比如, 对于例6和7的词间位置判断准确率较低(图 3(b)和(c))。

例6  首批全国政协委员抵达北京。

例7  奥巴马连任面临就业挑战。

2.2 基本统计量: t-测试差(dts)

Church等^[24]首次引入t-测试来度量一个英文单词A与其上下文单词x和y的结合紧密程度。根据定义, 维吾尔文单词序列x A y的t-测试值计算公式如下:

${t_{x, \;y}}(A) = \frac{{p(y|A) - p(A|x)}}{{\sqrt {{\sigma ^2}(p(y|A) + {\sigma ^2}(A|x))} }}, $

(4)

其中p(y|A)和p(A|x)分别为相邻词对(A y)和(x A)的Bi-gram概率, σ²(P(y|A))和σ2(P(A|x))分别是二者的方差。由式(4)可以看出, 如果t_{x, y}(A) > 0, 则A与后继y结合的强度大于与前趋x结合的强度, 此时A应与x断而与y连; 如果t_{x, y}(A) < 0, 则A与前趋x结合的强度大于与后继y结合的强度, 此时A应与y断而与x连; 如果t_{x, y}(A)=0, 则A与其前趋和后继的结合强度相等, 无法判断A与x和y的连断关系。

t-测试是基于字的统计量, 而不是基于字间位置。为了能够在中文分词中直接计算相邻字间连断概率, 孙茂松等^[12]提出t-测试差的概念。根据定义, 对于维吾尔文单词序列x A B y, 相邻单词A和B之间的t-测试差值计算公式如下:

$ {\rm{dts}}(A, B) = {t_{x, B}}(A)-{t_{A, y}}(B)。 $

(5)

当dts (A, B) > T_dts(T_dts为阈值)时, 相邻词对A与B之间的位置更倾向于判断为连, 否则判断为断。我们仍以USC₁为对象, 考察t-测试差关于单词间连、断的分布情况。t-测试差变化范围在-264.14~108.41之间, 当阈值T_dts取0.0时, α值可达最高为78.14%。与mi相比, 切分准确率较高, 但对于例5~7, 各位置的判断与mi有所不同(图 4)。

2.3 基本统计量:邻接对熵(dae)

语义串作为频繁使用的语言单元, 在真实文本中具有一定的流通度, 能够应用于多种不同的上下文环境。因此, 我们可以根据相邻两个单词上下文语言环境的复杂程度来衡量词对的结构稳定性。

对于维吾尔文有序单词序列x A B y(x和y是任何一个维吾尔文单词), 词对A和B在文本中每次出现的左邻接元素x和右邻接元素y构成一个邻接对 < x, y > , 那么A和B的所有邻接对组成邻接对集S_dae={ < x_i, y_i > }。m为集合中所有邻接对个数, c为集合邻接对种类数(不重复邻接对个数), n_i为每个邻接对 < x_i, y_i > 的频次, 则A和B的邻接对集合的信息熵(邻接对熵)的计算公式如下:

$ {\rm{dae}}(A, B) =-\sum\limits_{i = 1}^c {\frac{{{n_i}}}{m}} \log \left( {\frac{{{n_i}}}{m}} \right){\rm{。}} $

(6)

由式(6)可知, dae (A, B)取值越大, 词对A和B的语言环境变化越灵活多样, 其内部结合越紧密; dae (A, B)取值越小, A和B的独立性越弱, 很可能是一种偶然性组合。因此, 当dae (A, B) > T_dae(T_dae为阈值)时, A和B的单词间位置更倾向于判断为“连”, 反之判断为“断”。

例如, 三词语义串(A B C)在语料库中共出现5次, 其语言环境分别为x A B C y, y A B C x, z A B C x, w A B C y, v A B C x, 那么相邻词对A和B的邻接对集合S_dae={ < x, c > , < y, c > , < z, c > , < w, c > , < v, c > }, 此时m=5, c=5, 因此A和B的邻接对熵为

$ \begin{array}{l} {\rm{dae}}(A, B) =-\frac{1}{5}\log \frac{1}{5}-\frac{1}{5}\log \frac{1}{5}-\frac{1}{5}\log \frac{1}{5} - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{5}\log \frac{1}{5} - \frac{1}{5}\log \frac{1}{5} = 0.699\;{\rm{。}} \end{array} $

我们仍以USC₁为对象, 考察邻接对熵关于单词间“连”、“断”的分布情况。dae变化范围在0.06~1.37之间, 当阈值T_dae取0.60时, α值可达最高为73.23%。

与mi和dts相比, dae的分词准确率稍低, 但它对新词词间位置的连、断判断更准确。例如, 对于一个新出现的语义串A B, 因为A和B是两个独立语言单位, 在真实文本中会频繁使用, 他们结合构成的特定新词A B的词频远远小于A和B的词频, 会出现count (A)和count (B)极大而count (A B)极小的情况。在这种情况下, mi和dts几乎都会做出错误的判断, 但dae中词频不是决定性因素, 而是更多地考虑两个词上下文语言环境的变化多样性, 因此能够做出正确的判断。

例如, 新词“قۇش زۇكام”(禽流感)在生语料库URC中共出现17次, 单词“قۇش”(禽)出现2378次, 单词“زۇكام”(流感)出现4927次。因此(قۇش, زۇكام()的互信息值为3.78, dts取值不均匀(-3.17~-0.48), 如果以mi或dts来判断词间位置的连断, 是要断开的。但邻接对熵取值为0.96, 用dae判别词间位置是连接的。例如, 对于例8中“قۇش زۇكام”的词间位置判断, mi和dts都是错误的, 只有dae的判断是正确的(图 5)。

例8  科学家研制出禽流感病毒。

不论互信息、t-测试差或邻接对商, 都是将词在语言环境中某一方面的信息特征作为计算依据, 因此必然存在一定的局限性。中文分词中已有成功的案例, 将基本统计量加以组合从而各取所长。我们分别用互信息、t-测试差和邻接对熵对USC₁进行实验, 发现将它们结合互补有较大的可行性。

2.4 组合统计量:dmd

我们单独用基本统计量对USC₁进行词间位置判断, 其中t-测试差的α值最高(78.14%), 其次为互信息(75.26%), 最后是邻接对熵(73.23%)。因此, 我们以dts为主, 将3个基本统计量进行线性叠加, 融合成一个组合统计量dmd, 并完全根据dmd来判断词间位置。由于以上基本统计量取值范围相差较大, t-测试差变化范围为-264.14~108.41, 互信息变化范围为-6.75~21.01, 邻接对熵变化范围为0.0~3.97, 因此, 线性迭加前先进行归一化处理, 如式(7)~(9)所示。

$ {\rm{dt}}{{\rm{s}}^*}(A, B) = \frac{{{\rm{dts}}(A, B)-{\mu _{{\rm{dts}}}}}}{{{\sigma _{{\rm{dts}}}}}}, $

(7)

$ {\rm{m}}{{\rm{i}}^*}(A, B) = \frac{{{\rm{mi}}(A, B)-{\mu _{{\rm{mi}}}}}}{{{\sigma _{{\rm{mi}}}}}}, $

(8)

$ {\rm{da}}{{\rm{e}}^*}(A, B) = \frac{{{\rm{dae}}(A, B)-{\mu _{{\rm{dae}}}}}}{{{\sigma _{{\rm{dae}}}}}}, $

(9)

其中μ_dts, μ_mi和μ_dae分别是dts, mi和dae的均值, 实验值依次为-6.51, 3.63和0.52。σ_dts, σ_mi和σ_dae分别是dts, mi和dae的均方差, 实验值依次为24.29, 3.54和0.31。通过下式将它们叠加:

$ {\rm{dmd}}(A, B) = {\rm{dt}}{{\rm{s}}^*}(A, B) + \lambda \times {\rm{m}}{{\rm{i}}^*}(A, B) + \gamma \times {\rm{da}}{{\rm{e}}^*}(A, B), $

(10)

其中, λ和γ的值经实验测定, 发现当λ=0.35, γ=0.30时的分词效果最好。dmd在USC₁上的变化范围为-11.5~6.9, 当阈值T_dmd取为0时, α值最高(84.31%), 比单独使用t-测试差、互信息或邻接对熵分别提高6.17%, 9.05%和11.08%。

2.5 基于规则的词间关联度度量

以组合统计量dmd判断词间位置的准确率达到84.31%, 但是与理想的准确率还存在一定的距离。我们从维吾尔文本身的语言特性中寻找有助于词间位置判断的信息, 发现以下特性。

特性1  维吾尔文中的助词(ئىكهن、ئىدى等)、连词(ياكى、بىراق等)、副词(ئاران、بهك等)、量词(ئاران、بهك等)、代词(سهن、مهن等)以及感叹词(اھ、ئاھ等)等功能词, 在文本中始终不与其他单词结合成为语义串。本文将这些词称为“独立词”(in-dependent word, IW)。

特性2  维吾尔文单词间的结合主要是在名词(N)、形容词(ADJ)和动词(V)之间发生, 并构成语义串。当形容词与名词或与动词结合时, 形容词总是作为前驱, 而不会出现在后继位置。因此, N+ADJ或V+ADJ关系的相邻单词不可能结合构成一个语义串。

根据特性1和特性2, 我们归纳出用于词间关联识别的单词结合规则(word association rule, WAR), 并定义如下。

定义3  单词结合规则(WAR):对于文本中的相邻词对“A B”, 如A∈{IW}或B∈{IW}或B∈{ADJ}, 则判断A与B不能结合成为关联模式, 要断开。

因此, 我们建立两个辅助词表:独立词表和形容词表, 并用单词结合规则判断词间位置。这样, 既减少了词间位置的dmd计算量, 又明显提高了准确率。

3 基于词间关联度度量的切分算法

确定组合统计量dmd和单词结合规则后, 基于词间位置判断的维吾尔文语义串识别及切分整体流程如图 6所示。

对于训练语料, 将所有的标点符号都替换为分隔符“|”, 并进行词干提取处理, 然后计算语料库中所有词对的dmd值, 构建双词结合度(dmd)词典。对于待处理文本, 进行同样的预处理(标点符号的替换以及词干提取), 然后依次提取词间位置(词对), 按以下步骤判断词间的相邻性。

1)对于当前词对“A B”, 如A∈{IW}或B∈{IW}或B∈{ADJ}, 则判断A与B断开, 并插入分隔符“|”来消除A与B间的相邻性, 否则转步骤2。

2)从双词结合度词典中读取词对“A B”的dmd值, 如dmd (A, B) > T_dmd, 则判断A与B连接并保留相邻性, 否则插入分隔符“|”, 消除A与B间的相邻性, 转步骤3。

3)如“A B”是最后一个词对, 则转步骤4, 否则提取下一个词对并转步骤1。

4)结束当前文本词间位置的判断。

对当前文本中所有词间位置判断结束后, 以分隔符“|”进行切分, 得到文本中所有语义串。算法流程如图 7所示。

4 实验与分析

我们基于生语料库URC得到维吾尔文单词(词干)统计模型, 并构建双词结合度词典, 以USC₁为对象, 用不同统计量判断词间位置的准确率并调整阈值, 确定式(10)中的λ和γ来检验组合统计量dmd的有效性以及验证语义串提取算法在开放环境下的健壮性。因此, 我们分别在开发集和测试集上进行词间位置判断实验, 分析dts, mi和dae组合前和组合后词间位置正确判断情况。

以分界符“|”替换为所有标点符号后, 开发集USC₁和测试集USC₂共含的维吾尔文单词及需要判断的词间位置如表 1所示。

使用不同策略情况下的开发集和测试集实验结果如表 2和3所示。

从测试结果看出, 算法在测试集中的性能没有下降, 表明本文提出的组合统计量dmd及各类参数的确定是有效的, 尤其是引入语言特性的单词结合规则后, 词间位置判断准确率有明显提高。

我们发现, 词干切分工具的局限性、维吾尔文中难以避免的拼写错误、词间位置的不规范性以及名词术语的不规范缩写等因素在一定程度上影响词间位置判断准确率。关于词干切分算法的局限性, 除算法本身的缺陷外, 拼写错误也是一个主要的因素, 现有的方法和工具还不能对批量文本进行全自动检错和纠错。对于词间位置和名词术语书写规范化, 还没有相关的研究报道。不管是算法上的缺陷, 还是原始文本的不规范性, 都会影响词间判断准确率。因此, 对语料库进行训练或对待处理文本进行处理前, 应尽量排除以上负面因素的影响, 在较规范的文本语料上可以获得更高的切分准确率。这也是我们将来工作的研究重点。

5 结语

以空格作为自然分隔符的维吾尔文传统分词方法, 会把多词结构的语义串拆分成与其本义完全不符的若干个片段, 表现出非常明显的不足和局限性, 在维吾尔文文本挖掘领域研究中已成为一大瓶颈。本文提出一种基于词间关联度度量的维吾尔文本自动切分方法, 利用单词关联规则和统计结合的方法度量相邻单词之间的关联紧密程度, 从而识别出语义串的边界, 达到以语义及结构完整的词串为单位进行文本切分的目的, 实现了相应的自动切分算法。在大规模测试语料上进行的切分实验表明, 该算法表现出较高的准确率和健壮性。本文提出的方法还能应用到哈萨克文、柯尔克孜文等其他语言文本自动切分中。