面向互联网的有意义串的提取方法及装置

具体实施方式

为了使本发明的目的，技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明的一种面向互联网的有意义串的提取方法和系统进行进一步详细说明。

本发明将在互联网存在的海量网页中提取出有意义串。有意义串是具有独立语义，紧密耦合，具有广泛流通性的完整的语言单元。本发明提取的有意义串可以作为文本表示模型的特征表示，应用于互联网海量数据的聚类和分类中。

本发明将有意义串挖掘方法过程分为重复串发现，串内分析，串外分析，串间分析等四个阶段，整个过程如图1所示，包括以下步骤：

步骤S1，在重复串发现阶段，将网页语料预处理得到规则化的文本，记录文本中出现的重复串以及其出现的次数，过滤掉频次低于阈值的重复串和串长低于阈值的重复串。

步骤S2，在串内分析阶段，判断串的长度，如果该串的长度大于2，计算字符串的互信息，判断互信息是否达到设定的阈值，根据判断结果过滤掉没有达到阈值的字符串。如果该串是双字串，利用训练得到的双字串词性统计表和白名单，根据双字串分词后的结果对双字串进行过滤。

步骤S3，在串外分析阶段，计算字符串的熵值，判断熵值是否达到设定的阈值，根据判断结果过滤掉没有达到阈值的文本串。

步骤S4，在串间分析阶段，对所有字符串进行排序，计算排序后的相邻两串之间的重合率，并根据串和串之间的组成关系，把重合率大于阈值的邻串对划分为若干种类型，并分别对每种类型进行分析，过滤掉不满足要求的字符串，进而得到有意义串。

本发明主要使用了两个标准来衡量。首先，本发明在串内分析中，对长度大于2的串计算互信息，如果互信息值小于阈值，则删除该串。对于双字串，首先判断该串是否在双字串白名单里，如果在的话直接对该串进行串外分析。如果双字串不出现在白名单里，判断双字串分词后的词性组合是否在双字串词性统计表中，如果不在的话过滤该串，否则对该串进行串外分析。

其次，本发明引入了串间分析，以减少串之间的相异程度。计算排序后的相邻两串之间的重合率，根据串和串之间的组成关系把重合率大于阈值的邻串对划分成若干种类型，并分别对每种类型进行分析，过滤掉不满足要求的字符串。

下面详细说明步骤S1中，将网页语料处理得到规则化的文本，记录文本中出现的重复串以及其出现的次数，过滤掉频次低于阈值的重复串和串长低于阈值的重复串的过程。

本发明利用网络爬虫以增量方式采集互联网上的数据，并将下载到的网页抽取正文并格式化成纯文本文件。然后将文本转化成GB2312编码，根据GB2312编码规则将文本中的汉字，数字，英文转化成其对应的ASCII码值，将其他符号转化成空格的ASCII码，空格主要起到了分隔符的作用。采用ASCII码代替字符编码可以有效的避免所提取的串中含有半个汉字的问题，并能有效缩短提取重复串的时间。

目前比较成熟的提取重复串的方法有基于产生式文法的Sequitur算法，N元递增分步算法，以及后缀索引算法(包括后缀树和后缀数组)等等。后缀数组是一种全文索引结构，利用后缀数组计算语料中所有子串的集合频度和文档频度的算法的时间复杂度为O(NlogN)，空间复杂度为O(N)，N为文本的长度。本发明实例采用的后缀数组算法。后缀数组能在O(n)时间内建立。

在提取完重复串之后，要将重复串中的空格去掉，以空格为分隔符号将重复串拆成两个子重复串，直至所有重复串都不含有空格为止。去掉重复串中的空格的作用是保证提取的重复串不会跨标点、句子、段落，提高了重复串的语义完整性。

互信息是衡量重复串内部各组成部分之间的相关度。如果互信息比较高，则重复串与其单独左右部分子串相比更可能成为有意义串，否则删除该串。互信息是通过计算而得到。

计算互信息的公式如下：给定字符串S＝c₁c₂...c_n，其中c_i(1≤i≤n)为汉字、英文或数字，MI(S)为S串的互信息。

$\mathrm{MI}\left(S\right)=\frac{f\left(s\right)}{f\left(\mathrm{sl}\right)+f\left(\mathrm{sr}\right)-f\left(s\right)}$

其中f(sl)为去掉首字的S串的频次，f(sr)为去掉尾字的S串的频次，f(s)为S串的频次。

如图2所示，双字串词性统计表和双字串白名单是通过训练语料训练得到的，训练过程需要在人工的帮助下来训练数据。双字串进行分词的结果只有两种情况。第一种情况是对该双字串用分词程序只分出一个词性出来，即该串为一个双字词。观察满足这种词性的所有双字串是否有实际的语义，如果实义串的数目与满足该类所有串的数目的比值超过阈值的话，则将这种词性加入到双字串词性统计表中。第二种情况是该双字串用分词程序分成两个词性，即两个单字词，观察满足这种词性的所有双字串是否有实际的语义，如果实义串的数目与满足该类所有串的数目的比值超过阈值的话，则将其词性加入到双字串词性统计表中。

对于第二种情况，如果实义串的数目与该种词性组合的串的总数目的比值没有超过阈值的话，我们不将该类词性组合加入到双字串词性统计表中。不过满足这类词性组合的双字串中也会有部分串具有实际语义，为了避免去掉这些实义双字串造成的有意义串特征提取不完全，所以可以把这些实义双字串加入到双字串白名单里。双字串白名单可以事先过滤那些有实在意义但其分词后的词性组合却不满足双字串词性分析表的双字串。对双字串进行串内分析时候首先要用双字串白名单过滤双字串，如果双字串在白名单中，则直接对该串进行串外分析。如果不在白名单中，再对其进行串内分析步骤中后续的分析。

表1给出了双字串词性统计表的部分内容及其注释

双字串词         注释

性统计表  分词结果  第一个词性  第二个词性  双字串举例

内容

ng        1个词性   ng(名语素)  无          鞑虏

nr        1个词性   nr(人名)    无          布什

ns        1个词性   ns(地名)    无          中国

v         1个词性   v(动词)     无          监督

vn        1个词性   vn(名动词)  无          管理

mng    2个词性    m(数词)    ng(名语素)    二舅

ngng   2个词性    ng(名语素) ng(名语素)    木骨(地名)

nrnr   2个词性    nr(人名)   nr(人名)      汤唯

vn     2个词性    v(动词)    n(名词)       借钱

无论用分词程序将双字串分成一个词性还是两个词性，只要训练数据中该词性或者词性组合中大部分是完整的实义串，则将该词性或者词性组合加入到双字串词性统计表中。

对双字串进行的串内分析可以摒弃很多无意义的特征，提高特征的准确率。而且还能极大地减少特征数目。通过实验验证，加入双字串串内分析可以使有意义串的特征减少了89.1％。

下面详细描述步骤S3中，计算字符串的熵值，判断熵值是否达到设定的阈值，根据判断结果过滤掉没有达到阈值的文本串的过程。

熵值主要是反映字符串的独立性，熵值越大说明该串越能够在多种语言环境中使用。串外分析利用熵值来判别是否对字符串进行筛选。

计算熵值的公式为：EL代表串的熵值。令文本T的子串R共出现F次，其左邻接集合L＝{C₁，C₂……C_n}，C_i出现频次为f_i(1≤i≤n)，则R的左邻接熵如以下公式计算。

$\mathrm{EL}=-\underset{i=1}{\overset{n}{\Sigma }}\left(\frac{f_i}{F}\log \frac{f_i}{F}\right)$

同理可计算右邻接熵，左邻接熵和右邻接熵的算术平均值为串的熵值。

由于当串处在句子首部时，上文为空，无法计算左邻接熵，此f_i为该串处在句首的次数。同理当串处在句子尾部时，下文为空，无法计算右邻接熵，此时此时f_i为该串处在句尾的次数。

下面详细描述步骤S4中，对所有字符串进行排序，计算排序后的相邻两串之间的重合率，并根据串和串之间的组成关系，把重合率大于阈值的邻串对划分成若干种类型，并分别对每种类型进行分析，过滤掉不满足要求的字符串，进而得到有意义串的过程。

为了判断两个串的相似程度，本发明定义了重合率的概念。重合率能够度量两个串的重合程度的大小。当重合率大于阈值时，则两串相似。该阈值取值要大于0.5。重合率的计算公式如下：

设字符串a，字符串b的长度分别为length1，length2。两串的最长公共子序列的长度为s1，两串的最长重复子串的长度为s2，设两串的重合率记为C(a，b)，则重合率公式如下

$C(a,b)=\frac{1}{2}*(\frac{1}{2}(\frac{s1}{\mathrm{length}1}+\frac{s1}{\mathrm{length}2})+\frac{1}{2}(\frac{s2}{\mathrm{length}1}+\frac{s2}{\mathrm{length}2}))=\frac{s1+s2}{4}(\frac{1}{\mathrm{length}1}+\frac{1}{\mathrm{length}2})$如

图3所示，将所有字符串排序，计算排序后两两相邻串的重合率。根据相邻串的组合形式，只将那些重合率大于阈值的两两相邻串归入到以下5种类型中，A-AB型相邻串，A-AB-AC型相邻串，A-AB-ABC型相邻串，最长公共子串为1的相邻串及其他类型。如果相邻串的重合率大于阈值，则说明相邻的两串之间相似程度比较大。下面分别对各种类型的数据进行分析来筛选修剪字符串，以减少字符串的语义冗余和字符串的相似程度。

对于A-AB型数据，本发明引入频率比值来反映两个串语用环境丰富程度上的差异程度。我们利用频率比值来对A-AB型数据进行筛选和修剪。设A串的频次为f(A)，AB串的频次为f(AB)，则频率比值的公式如下：

计算A-AB型相邻串的频率比值，然后判断频率满足以下哪种情况。

S11)如果该频率比值大于大阈值，则说明A串出现的频次远远高于AB串出现的频次，AB串为小概率出现的串。一般来说，小概率出现的串在全文中的作用不太突出，内容可以忽略，而且A串在语义上能对AB串语义的丢失有一定的弥补，因此这种情况可以把AB串过滤掉。

S12)如果该频率比值小于小阈值，则说明A串后面紧接着B串的频次的概率远远大于A串后面不紧接着B串的概率，也就是说AB串有很大的概率作为一个整体出现，因此这种情况把A串过滤掉。

S13)如果该频率比值介于小阈值和大阈值之间，则说明A串后面接B串以及A串后面不接B串的概率差不多，A串和AB串都具有比较完整的语义，因此这种情况两串都保留。

对于A-AB-AC型数据，本发明通过A串，AB串，AC串的频次来对字符串进行筛选和修剪。设A串的频次为f(A)，AB串的频次为f(AB)，AC串的频次为f(AC)。对该类型数据的处理一共有以下四种情况。

S21)如果的值大于重合阈值，说明AB串加上AC串出现的总次数和A串出现的总次数差不多，这时用AB串和AC串在语义上可以很好的代替A串。因此这种情况下我们将A串过滤掉。

S22)如果的值小于重合阈值，并且AB串(或AC串)的频次小于最小阈值，即AB串(或AC串)出现的次数比较少。出现次数少的串大都是临时组合，AB串(或AC串)通常并不作为一个整体出现。因此这种情况下把AB或AC修剪成B或C。

S23)如果的值小于重合阈值，并且AB和AC的频次小于最小阈值，这种情况下则把AB和AC修剪成B和C。

S24)如果的值小于重合阈值，并且AB和AC的频次都大于最小阈值，即AB串和AC串都频繁出现，两串有很大的概率作为一个整体存在，这种情况下不修剪AB串和AC串。

对A-AB-AC型数据进行串间分析，既能够减少特征的数目又可以修剪部分冗余串成为语义更加完整的有意义串。将AB串修剪成B串，也就是说删除有意义串集合中的AB串，并在有意义串集合中增加B串。当然如果B串事先已经出现在有意义串集合中，此时就不用增加B串；否则向有意义串集合中添加B串，并将AB串的频次作为B串的频次。

对于A-AB-ABC型数据，设A串的频次为f(A)，AB串的频次为f(AB)，ABC串的频次为f(ABC)。本来发明通过主要根据f(AB)和f(ABC)四个参数来对该类所有字符串进行筛选和修剪。对于该类数据，根据以下规则处理A串和AB串，再根据相同规则处理AB串和ABC串，将两种处理结果结合起来就可得到对A-AB-ABC型数据的处理结果。

对于A-AB-ABC型数据中的A串和AB型的处理规则如下：

1)如果f(A)远远高于f(AB)串，这种情况将AB串过滤掉。

2)如果f(A)接近f(AB)，这种情况将A串过滤掉。

3)如果f(AB)小于最小阈值，这种情况把AB串修剪成B串。

4)如果f(AB)大于最小阈值，这种情况A串和AB串都保留。

对A-AB-ABC型数据处理的最终规则如下，规则的优先级顺序是从上到下，如果满足任一规则后则可退出，即该对相邻串处理完毕。“最终保留的串”是经过对A串，AB串，ABC串的修剪和筛选后最后形成的串。

S30)f(AB)远远大于f(A)，最终保留的串为A串。

S31)f(AB)接近f(A)，f(ABC)小于f(AB)，最终保留的串为ABC串。

S32)f(AB)接近f(A)，f(ABC)接近f(AB)，最终保留的串为AB串。

S33)f(AB)接近f(A)，f(ABC)小于最小阈值，最终保留的串为AB串和C串。

S34)f(AB)接近f(A)，f(ABC)大于最小阈值，最终保留的串为AB串。

S35)f(AB)小于最小阈值，最终保留的串为A串，B串和C串。

S36)f(AB)大于最小阈值，f(ABC)小于f(AB)，最终保留的串为A串和ABC串。

S37)f(AB)大于最小阈值，f(ABC)接近f(AB)，最终保留的串为A串和AB串。

S38)f(AB)大于最小阈值，f(ABC)小于最小阈值，最终保留的串为A，AB和C串。

S39)f(AB)大于最小阈值，f(ABC)大于最小阈值，最终保留的串为A，AB和ABC串。

对A-AB-ABC类型的数据进行串间分析，可以极大的减少特征串的数目，并且使特征串和特征串之间的相似程度有所减小，而保留的特征串在语义上完全可以概括原有的特征串。

对于相邻串的最长公共子串为1类型的数据来说，只有相邻串的重合率大于阈值才有可能将相邻串划分到该类。既然相邻串的重合率大于阈值，则两串的最长公共子序列必定大于2。通过实验数据观察，两串的语义上比较相似，如下表所示。对于这种类型的数据，可将两串合并成1个串，只保留长度较长的串，而删除掉长度较短的串。最后将两串频次的总和作为该长度较长的串的频次。

表2给出了最长公共子串为1的相邻串类型部分数据的处理结果

通过实验验证，满足该类型的数据通常情况下一个特征串是另一个特征串的缩写形式，两者在语义上比较相似。对该类型数据进行串间分析，可以增加特征的强度，减少语义漂移，使特征具有更好的代表性；而且也能够减少特征的数目，起到降维的作用。

以上过程提到的阈值都是经过不断调整阈值并观察实验效果训练得到。

经过这一系列步骤，还没有被过滤掉的特征串确定为有意义串。将这些有意义串和有意义串的频次输出，过程结束。

为了验证本发明的有效性，我们搭建了典型应用环境。实验采用AMD OPTERON 2G的曙光服务器，操作系统为2.6.16.19内核的Linux企业版。利用舆情系统收集到的来自新浪，中华网，网易，腾讯等六大论坛和各个新闻网页收集到的1万多网页，作为测试数据的原始网页的一部分。经过格式化文本最终的大小为12.3MB。本发明的有意义串的挖掘方法在这些新闻网页上提取有意义串的正确率可以达到85.3％。

与所属面向互联网的有意义串的提取方法相对应，本发明还提供了一种面向互联网的有意义串的提取系统，如图4所示，其包括：

重复串发现模块，用于将网页语料预处理得到规则化的文本，记录文本中出现的重复串以及其出现的次数，过滤掉频次低于阈值的重复串和串长低于阈值的重复串。

串内分析模块，用于对字符串进行串内分析，判断字符串的长度，如果该串不是双字串，则计算字符串的互信息，判断互信息是否达到设定的阈值，根据判断结果过滤掉没有达到阈值的文本串；如果该串是双字串，利用训练得到的双字串词性统计表和白名单，根据双字串分词后的结果对双字串进行过滤。

串外分析模块，用于对字符串进行串外分析，计算字符串的熵值，判断熵值是否达到设定的阈值，根据判断结果过滤掉没有达到阈值的字符串。

串间分析模块，用于对字符串进行串间分析，对所有字符串进行排序，计算排序后的相邻两串之间的重合率，并根据串和串之间的组成关系，把重合率大于阈值的邻串对划分为若干类型，并分别对每种类型进行分析，过滤掉不满足要求的字符串，进而得到有意义串。

本发明的面向互联网的有意义串的提取系统，采用与面向互联网的有意义串的提取方法相同的过程工作，因此，在本发明实施例中，不再对该系统进行重复描述。