一种面向有意义串挖掘的重复串提取方法及装置

摘要

本发明提供的是一种面向有意义串挖掘的重复串提取方法及装置。方法包括下列步骤：步骤A：语料预处理；步骤B：重复串提取；步骤C：重复串修剪。装置由语料预处理模块、重复串发现模块和重复串修剪模块连接组成。本发明提取的重复串可经过进一步深度分析以得到有意义串，可以广泛应用于网络舆情管理、互联网智能信息处理等应用领域。

说明书

技术领域

本发明涉及利用计算机技术辅助网络信息智能分析或舆情管理方法及装置。

背景技术

随着互联网技术的迅猛发展，网络在传达社情民意方面的优势逐步显现出来。继传统的报纸、广播、电视之后，互联网已经确立了自己第四媒体的主导地位，并在表达民众心声、反映社会舆论方面发挥极其重要的作用。网络舆情是通过互联网传播的公众对现实生活中某些问题所持的有较强影响力、倾向性的观点和言论，是网民关注的热点，是民众讨论的焦点，集中反映一个时期网络舆论的中心。互联网已经成为中国社会各阶层利益表达、情感宣泄、思想碰撞的重要舆论渠道。在这样的背景下，如何从互联网网页文本中挖掘出有用信息就显得非常重要。有意义串是具有独立语义，紧密耦合，具有广泛流通性的完整的语言单元。有意义串实际上就是以短语为特征，以有意义串作为特征表示在文本聚类和分类上取得了良好的效果。提取有意义串首先需要提取重复串，在重复串的基础上对重复串进行深度分析便可以得到有意义串。

目前国内在重复串的预处理研究方面取得了一些研究成果.文献[1][2][3]在语料预处理中去除了停用词以及数字标点等非单词符号，目的是减少无用特征项对提取重复串的干扰。文献[1][2]在文档之间用特定的边界符号分隔，该边界符号不会出现在任何原始文档中，这样可以避免出现重复串跨文档的情况，因为跨越文档边界的字符串是没有意义的。文献[1][3]将每个单词被转换成一个ID，这样每个英语单词或中文汉字都可以被作为一个单元处理，可以避免提取的重复串中会出现半个汉字的情况并可以缩短重复串提取的时间。文献[1]处理的数据为许多文档的集合，在语料预处理中将每个字符编号，然后记录每个下标对应字符所属的文档编号，在提取重复串时很容易判断出每个重复串究竟出现在哪几篇文档中。

本发明申请涉及到的相关的公开文件包括：

[1]黄玉兰，龚才春，许洪波，程学旗.基于局部性原理的有意义串提取方法.第四届全国信息检索与内容安全学术会议.2008-11-01；

[2]龚才春.短文本语言计算的关键技术研究.中国科学院研究生院(计算技术研究所)博士论文.2008-04-01；

[3]龚才春，贺敏，张华平，许洪波，程学旗.大规模语料的频繁模式快速发现算法.通信学报.2007-12-25；

[4]胡吉祥，许洪波，刘悦，程学旗.重复串特征提取算法及其在文本聚类中的应用.计算机工程.2007-01-20；

[5]胡吉祥，许洪波，刘悦，王斌，程学旗.基于重复串的短文本聚类研究.全国第八届计算语言学联合学术会议(JSCL-2005).2005-08-01；

[6]黄旭，朱艳琴，罗喜召.重复串特征提取算法在不良信息检测中的应用.第三届全国信息检索与内容安全学术会议.2007-11-01；

[7]张华平，贺敏.一种面向互联网的有意义串的挖掘方法和系统.200710120755.5.2008-03-26；

[8]邹纲，刘群.一种中文新词语的检测方法及其检测系统.200410000651.7.2005-07-20。

通过对上述文献的总结和分析，发现目前的重复串提取方法中在预处理阶段存在以下缺点：1)停用词处理不当：在语料预处理阶段中去除停用词会破坏语料的整体结构，导致提取的重复串不准确以及提取重复串上下文时也不准确；2)对重复串的长度没有限制：如果提取的重复串长度过长，会导致提取的特征过于冗余和稠密，语义过于分散；3)重复串的边界界定不清：某些提取的重复串可能会跨越完整的语义单元，跨越标点符号以及句子，造成提取的重复串是由不同语义单元的内容拼凑而成，该种重复串的组成具有偶然性，无确切语义，没有实际价值。

发明内容

本发明的目的在于提供一种能够从海量语料中准确高效的提取重复串，为进一步进行有意义串深度挖掘提供技术支持的一种面向有意义串挖掘的重复串提取方法。本发明的目的还在于提供一种面向有意义串挖掘的重复串提取装置。

本发明的目的是这样实现的：

本发明的面向有意义串挖掘的重复串提取方法包括下列步骤：

步骤A：语料预处理；

步骤B：重复串提取；

步骤C：重复串修剪；

所述步骤A包括些下列步骤：

步骤A1，将网页中的数据去除标签后格式化成文本形式，将文本中的特殊符号用分隔符号代替，采用空格作为分隔符，然后将文本中出现的所有符号都转化成对应的ID表示；

所述步骤B包括些下列步骤：

步骤B1，从文本中提取重复串，记录重复串以及其出现的次数，过滤掉频次低于阈值和长度小于阈值的重复串；

所述步骤C包括些下列步骤：

步骤C1，对于长度大于阈值的重复串，利用对该串进行分词后的词性类别将该串分割成若干子串；对于含有空格的重复串，以空格为分隔符号把该串分割成若干子串；同时对重复串进行去停用词处理等其他修剪工作。

所述步骤A 1包括些下列步骤：

步骤A11，去除网页标签，提取网页中的正文；

步骤A12，将网页编码转化成GB2312格式编码；

步骤A13，根据GB2312的编码格式保留文本中出现的汉字、英文、数字符号，将其他符号用空格符代替。

步骤A14，去掉文本中首尾出现的空格；若文本中连续出现空格，则只保留一个空格；

步骤A15，将文本中的汉字、英文、数字、空格符号分别转化成对应的ID值，ID值为其ASCII码的整数值。

所述步骤B1包括些下列步骤：

步骤B11，提取该文本的重复串，记录文本中出现的重复串和重复串的次数，删除频次低于阈值和长度小于阈值的重复串；

步骤B12，将重复串的ID组合形式转换成相对应的字符组合形式。

所述步骤C1包括下列步骤：

步骤C11，删除重复串中含有的停用词，如果删除后重复串的长度过短，则删除该重复串；

步骤C12，去掉重复串首尾空格，并过滤掉长度小于阈值的重复串；

步骤C13，去除粘性字符；

步骤C14，以空格为分隔符号，把含有空格的重复串分割成若干子串，如果子串已经在重复串集合中出现过，则删除该子串；否则统计该子串出现的频次，并将该子串加入到重复串集合中；

步骤C15，如果重复串的长度小于阈值，则转入步骤C18；否则转入步骤16；

步骤C16，对长度大于阈值的重复串进行分词，并对分词后的词性结果进行扫描，如果前一个词的词性是名词词性，后一个词的词性是非名词词性，则把此重复串拆分成两个子串，其中把该名词、包括该名词本身之前的串当做一个子串，把该名词、不包括该名词之后的串当做另一个子串；

步骤C17，以分词后词性结果中的特殊词性为分隔符号对步骤C15分割出的子串再次进行分割；

步骤C18，删除不包含汉字的重复串，并对重复串进行去重工作。

本发明还提供了一种面向有意义串挖掘的重复串提取装置包括：

语料预处理模块、重复串发现模块和重复串修剪模块连接组成，

语料预处理模块，将网页中的数据格式化成文本，把文本中的特殊符号用空格代替，然后将文本中出现的所有符号都转化成对应的ID表示；

重复串发现模块，从文本流中提取重复串，记录重复串以及其出现的次数，过滤掉频次低于阈值和长度小于阈值的重复串；

重复串修剪模块，对长度大于阈值的重复串，利用对该串进行分词后的词性类别将该串分割成若干子串。对于含有空格的重复串，以空格为分隔符号把其分割成若干子串；同时对重复串进行去停用词等其他修剪工作，进一步对重复串进行筛选和修剪；在进行长串分析和空格分析后，删除不包含汉字的重复串对重复串去停用词以及对重复串去重等相关工作。

所述重复串发现算法可以使N元递增分步算法，以及后缀索引算法(包括后缀树算法，后缀数组算法)等。本发明采用后缀数组算法来发现重复串。

本发明的有益效果是：本发明的面向有意义串挖掘的重复串提取方法和系统，从互联网中下载网页，然后经过语料预处理，重复串发现，重复串修剪三个阶段达到挖掘出互联网中的重复串的目的，在重复串发现的基础上能够继续挖掘出有意义串并为舆情监管系统服务。本发明没有在语料预处理阶段去除停用词而在重复串修剪阶段去除停用词的目的是因为去掉停用词后提取的重复串可能会不准确，而且在对重复串进行深度挖掘出有意义串的过程中需要保存该重复串的上下文，去掉停用词可能会破坏重复串的上下文。语料预处理和重复串修剪阶段中的空格分析可以很好的限制所提取的串的有效范围，能够使重复串不跨越完整的语义单元，不跨越标点，句子，段落，提高了重复串的准确性。重复串修剪阶段的长串分析能够有效地减少重复串的长度，避免了长串在语义上过于冗余拖沓。

本发明提取的重复串可经过进一步深度分析以得到有意义串，可以广泛应用于网络舆情管理、互联网智能信息处理等应用领域。

附图说明

图1本发明面向有意义串挖掘的重复串提取方法过程示意图；

图2本发明面向有意义串挖掘的重复串提取过程流程图；

图3本发表面向有意义串挖掘的重复串提取装置示意图。

具体实施方式

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

本发明将从互联网中存在的大量网页语料中挖掘出重复串。重复串是文本中重复出现的语言单元。重复串的粒度比分词分出的词的粒度要大，重复串会可能会是某个词，也可能是某些词的组合。

本发明提出的重复串挖掘方法过程分为语料预处理，重复串发现，重复串修剪等三个阶段，整个过程如图1所示，包括以下步骤：

步骤S1，将网页中的数据格式化成文本，并把文本中的特殊符号用分隔符号代替，将文本中出现的全部符号转化成该符号对应的ID表示。

步骤S2，对步骤S1形成的文本集合提取重复串，记录重复串内容及其出现的频次，删除频次低于阈值和长度小于阈值的重复串。

步骤S3，对长度大于阈值的重复串，利用对该串进行分词后的词性类别将其分割成若干子串。对于含有空格的重复串，以空格为分隔符号将其分割成若干子串。同时进行重复串去停用词等处理，进一步实现对重复串的筛选和修剪。

本发明主要使用了两个标准来衡量。首先，本发明在语料预处理阶段中在文本语料中加入分隔符号(即空格)，在提取完重复串之后如果发现提取的重复串中包含空格的话，则以空格为分隔符把该重复串拆分成若干子串。

其次，本发明还要判断一个串是否是长串，如果是长串的话，对该长串进行分词处理。然后根据分词结果中名词词性出现的位置对该长串进行一次分割，将该长串拆分成若干子串。最后根据分词结果中特殊词性出现位置对上次分割后的结果进行二次分割，继续拆分子串。

下面详细说明步骤S1中，将网页中的数据格式化成文本，并把文本中的特殊符号用分隔符号代替，将文本中出现的全部符号转化成符号对应的ID表示的过程。

将从互联网中下载的网页去除网页标签，并提取网页中的正文。将所有网页文档合并成一个伪文档，网页文档之间用一个空格分隔。伪文档不是一篇具体网页内容形成的文档，而是所有网页内容合并在一起形成的文档。将合并后的伪文档中的编码格式转化成GB2312格式，逐字扫描该伪文档，只保留汉字，空格，英文和数字等符号，把其余符号(包括标点符号，美元符号等)都用空格代替。最后再将伪文档中所有符号转化成对应的ID表示，即相应的ASCII码值的整数值。

把除汉字、英文、数字之外的符号用空格代替，目的是在重复串的修剪阶段会以空格为分隔符号对该重复串进行拆分，以保证提取的重复串不会跨越完整语义单元以及跨越标点符号、句子、文本，提高了重复串的语义完整性，减少了无关的重复串的输出。

把文本中的汉字、数字、空格、字母转化成对应的ID，目的是利用ID表示能够大大缩短重复串提取的时间，并且能够有效避免提取的重复串中会出现半个汉字的情况。

通过实验验证，选择在语料预处理方面保留数字和英文，这样能保证包含英文和数字的重复串的信息能够提取完整。例如文档中含有“AC米兰”这个重复串，如果去掉英文字母的话，则只能提取出“米兰”这个重复串，此时无法判断出“米兰”这个重复串究竟说的是一个城市还是在说一个足球俱乐部。

通过实验验证，在预处理阶段去停用词，会破坏文本中的结构，导致提取某些重复串提取错误。重复串可以进一步深度分析得到有意义串，计算有意义串时需要计算重复串的上下文，在预处理阶段去停用词还可能造成提取重复串上下文数据不准确，所以需要将停用词处理放在串的修剪阶段。这里说的停用词主要是汉字停用词，不包括标点符号，字母，数字等其他符号。例如某个文档中有两个句子“张三果然来自中国东北”和“张三可能来自中国东北”，其中“果然”和“可能”是停用词。在去掉停用词后提取的重复串为“张三来自中国东北”，实际上“张三”和“来自中国东北”这两个串并没有直接连在一起。计算重复串上下文时也可能计算不准确，例如“来自中国东北”的上文本应该是“果然”和“可能”，但是去停用词后提取的上文却是“张三”。

下面详细描述步骤S2中，对文本流提取重复串，记录重复串及其出现的频次，删除频次低于阈值和长度小于阈值的重复串。

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

此时提取的重复串实际上不是字符的组合，而是ID的组合。为了在直观上便于观察重复串，我们要将重复串的ID表示形式还原为重复串的字符表示形式。

下面详细说明步骤S3中，对于长度大于阈值的重复串，利用对该串进行分词后的词性类别将该串分割成若干子串；对于含有空格的重复串，以空格为分隔符号把其分割成若干子串；同时会对重复串进行去停用词等其他修剪工作的过程。

为了保证重复串内部各成分之间紧密耦合，使得重复串不会出现跨越完整语义单元，跨标点、跨句子、跨段落，跨文档等情况，本发明在文本中加入分隔符号，并对分隔符号进行处理。通过空格分析，如图2所示，可以提高重复串的准确率，增强重复串的内部凝固度，减少重复串的语义冗余。

例如：对于提取的重复串“日本作为战败国是不能拥有军队的只能有所谓的自卫队”，将该重复串以空格为分隔符号，把该重复串分割成四个重复串“日本作为战败国”“是不能拥有军队的”“只能有所谓的”“自卫队”。如果分割后新生成的子串没有出现在已有的重复串集合中，则把该串加到重复串集合中。

为了避免重复串的长度过长导致重复串的语义分散，本发明对长度较长的重复串先进行分词处理，再根据分词后的词性类别对长度较长的重复串进行分割。这里使用的分词程序为中科院的分词程序ICTCLAS。长串分析主要有两步。

步骤L1：首先对该长串进行分词，然后对分词后的词性进行扫描，如果前一个词的词性是名词词性(名词词性包括n名词，Ng名词性语素，nr人名，ns地名，nt机构团体名词，nz专有名词等)，后一个词的词性是非名词词性，则把该长串拆分成两个子串，其中把该名词(包括该名词本身)之前的串当做一个子串，把该名词(不包括该名词)之后的串当做另一个子串。步骤L1可以使名词词组作为一个整体被提取出来，而不会被分开。

例如：对于提取的重复串为“两国人民的根本利益”

该串的长度大于阈值，属于长串。首先对其进行分词，分词结果为：

两/m  国/n  人民/n  的/u  根本/a  利益/n

由于“人民”的词性是名词词性，“的”的词性是非名词词性，则将“人民”之前的部分(包括“人民”)当做一个重复串，将“人民”之后的部分当做另一个重复串。长串分析第一步分解出两个重复串是“两国人民”和“的根本利益”。

步骤L2：对第一步分割出的若干子串根据某些特殊词性为分隔符进行第二次扫描和串的分割。这些特殊词性包括o拟声词，u助词，x非语素字，c连词，e叹词，y语气词，p介词等。这些词本身没有实在意义，只是起到对实词的修饰和补充作用，可以起到分隔重复串的作用。

例如：对于第一步分解出的重复串″的根本利益″，由于“的”的词性属于特殊词性中的一种，所以对该串“的根本利益”进行再次分割，分割后的子串结果为“根本利益”。

通过长串分析，“两国人民的根本利益”这个重复串最终分解成“两国人民”和“根本利益”两个重复串。

为了进一步修剪和筛选重复串，还要对重复串做去停用词分析，去无汉字串分析，去重分析。这里说的停用词主要是双字以上的停用词，例如对于重复串“不管美军”，由于“不管”这个重复串在停用词表里，在去停用词后，这个重复串被修剪为“美军”。去停用词工作能够有效避免由无实义特征所引起的重复串语义冗余和语义偏移问题。

停用词表可以采用基于统计学和语言学的方法选取生成。由于其不是本发明的发明点，因此在本发明中不再一一详细描述。

较佳的还会进行去黏性字符分析，例如“的花朵”中的“的”字就属于黏性字符，黏性字符本身没有实际的语言意义，黏性字符并不对重复串的语义造成影响，应该考虑去掉黏性字符。

经过这一系列步骤，还没有被过滤掉的重复串确定为最终的重复串。将这些重复串和重复串的频次输出，过程结束。

为了验证本发明的有效性，我们搭建了典型应用环境。实验采用AMDOPTERON 2G的曙光服务器，操作系统为2.6.16.19内核的Linux企业版。利用舆情系统收集到的来自新浪，中华网，网易，腾讯等六大论坛和各个新闻网页收集到的1万多网页，作为测试数据的原始网页的一部分。经过格式化文本最终的大小为12.3MB。经观察，用本发明方法提取的重复串特征数量与直接进行重复串提取相比较而言两者数量相差在1％左右。本发明提取的重复串既能保证提取的重复串在维持原有语义的基础上长度不会过长，又能保证提取的重复串严格控制在句子以及完整的语义单元内部。

与所述面向有意义串挖掘的重复串提取方法相对应，本发明还提供一种面向有意义串挖掘的重复串提取系统，如图3所示，其包括：

语料预处理模块，将网页中的数据格式化成文本，并把文本中的特殊符号用分隔符号代替，将文本中出现的全部符号转化成对应的ID表示。

重复串发现模块，对文本流提取重复串，记录重复串以及其出现的次数，过滤掉频次低于阈值和长度小于阈值的重复串。

重复串修剪模块，对长度大于阈值的重复串，利用对该串进行分词后的词性类别将该串分割成若干子串。对于含有空格的重复串，以空格为分隔符号把其分割成若干子串。同时对重复串进行去停用词等其他工作，进一步对重复串进行筛选和修剪。

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

以上对本发明的具体实施例进行了描述和说明，这些实施例应被认为其只是实例性的，并不用于对本发明进行限制，本发明应根据所附的权利要求进行解释。