在一篇文档中出现频率较高的词,称为高频词。根据自然语言的特点,高频词往往与文档主题密切相关,因此文档高频词在文档自动分类处理和信息检索中具有重要意义。空格是英文文本天然的词分隔符,而中文文本的词与词之间并不存在分割符。如何将一段文字正确地分隔成字词的组合,一直以来都是中文信息处理技术研究的热点和难点。

高频词的获取,可以通过先分词和再统计来解决。中文分词方法大致分为两类:基于词典的方法和基于字标注的方法^{[ 1]}。基于词典的分词方法,往往需要借助于事先存在的分词词典,通过与词典进行匹配,再加上歧义消除处理来分词。基于词典的分词方法不足之处在于难以识别未在词典中登录的词,如人名、地名、机构名称和组合词等。基于字标注的分词方法根据字与字之间结合的紧密程度,对单个字的词位进行标注。最后,根据词位定义直接获得分词结果。此类方法主要包括互信息、隐马尔可夫模型(HMM)、条件随机场和最大熵模型(ME)等^{[ 2, 3, 4, 5]}。

高频词的抽取虽然可以通过分词来解决,但与分词有本质的区别。一篇文档的高频词一定是重复出现的词。因此以相同的字串形式重复出现,成为高频词的重要特征。反过来,这一特征可以帮助人们发现高频词。针对高

频词的抽取,金翔宇等^{[ 6]}提出了通过自增长算法获取中文文档中的汉字结合模式,并引入支持度、置信度等概念来筛选词条的无词典方法。韩客松等^{[ 7]}提出了使用Hash技术,依靠统计字的出现频率和字与字之间的结合程度等信息提取高频字串的方法。任禾等^{[ 8]}利用所有子字符串的相关频次信息计算每一个子字符串的信息熵来抽取高频词。

本文基于高频词以相同字串形式重复出现的特征,提出了通过构造文本的PAT数组和LCP数组来快速发现在一篇文本中多次重复出现的高频字串,进而从这些高频字串中抽取出高频词的算法。该算法将文本看作字符串的叠加,而不是字的组合。抽取过程不需要分词词典支持,数据结构模型更加简单,抽取过程只需要一次读取文本和一次字符串排序操作,执行效率更高。实验表明,该方法对高频词的抽取是可行的,且对新词、组合词的识别比较有效。

PAT数组主要用于对文本进行全文索引。PAT数组将待处理文本看作一个无限长的字符串,由任意位置开始直至文本结尾所形成的子字符串,称为文本的一个后缀^{[ 9]}。本文用记号sfx(i)来表示从位置i开始的文本后缀。如文本“传统经济与网络经济比较”,共有sfx(0)=“传统经济与网络经济比较”、sfx(1)=“统经济与网络经济比较”、…、sfx(9)=“比较”、sfx(10)=“较”等11个后缀,而PAT数组就是这11个后缀字典顺序的排列。

LCP(Longest Common Prefixes)数组对应于一个PAT数组,LCP数组记录了PAT数组中相邻两个后缀间的最长相同前缀长度^{[ 9]}。函数flcp(S₁,S₂)表示字符串S₁与S₂的相同的前缀长度。如字符串S₁=“网络经济”,S₂=“网络经营者”,则flcp(S₁,S₂)=3;而字符串S₃=“网络经济”, S₄=“传统经济”由于无相同前缀,则flcp(S₃,S₄)=0。文本“传统经济与网络经济比较”对应的PAT数组和LCP数组如图1所示:

图1

图1

图1 文本“传统经济与网络经济比较”的PAT数组和LCP数组 文本 0传 1统 2经 3济 4与 5网 6络 7经 8济 9比 10较 PAT数组 4 0 9 3 8 2 7 6 1 5 10 LCP数组 0 0 0 1 0 2 0 0 0 0 0

图1 文本“传统经济与网络经济比较”的PAT数组和LCP数组

PAT数组和LCP数组的创建过程的实质是字符串的排序过程。本文在实验程序中使用了文献[10]中所给出的Bentley-Sedgewick算法。算法思想源自于快速排序与基数排序,排序过程首先以所有字符串(文本后缀)的首字符为比较对象,对数组进行第一轮排序。排序后的数组分为三段,左边段字符串均小于中间段字符串,中间段内所有字符串的首字符相同,右边段所有字符串均大于中间段字符串。若各段的长度大于1,则对该段继续使用上述算法进行递归划分。每一次的划分可利用前一次划分的成果。如第一次划分后对中间相等段进行进一步划分时,比较可直接从第二个字符开始,无需再比较第一个字符。LCP数组的创建可与PAT数组的创建同时完成。以PAT数组的第i次三段划分为例,划分后的中间段内所有后缀的前i个字符相同,则与该段对应的LCP数组段内元素的值均更新为i。随着PAT数组排序过程的迭代进行,同时也完成了LCP数组元素值的计算^{[ 11]}。

在一篇文本中的不同位置多次重复出现的字符串可能有:词、短语、特定符号、词的组合和习惯用语等,文本的高频词也一定在其中。LCP数组中隐含了任意两个文本后缀之间的前匹配长度。如果在LCP数组中,存在连续的k个元素值大于等于m,则可以推断出有一个长度为m的字符串,在文本中总共出现了k+1次。因此,通过扫描LCP数组可以发现文本的重复字符串及其出现次数。以图1所示的文本“传统经济与网络经济比较”为例,通过扫描LCP数组,可以发现取值大于0的元素有:LCP[3]=1,LCP[5]=2。LCP[3]=1表明字符串“济”重复出现两次;LCP[5]=2表明字符串“经济”重复出现两次。本文所设计算法的目标就是要发现这样的重复串,进而从这些串中发现有效的高频词。

本文从人大报刊复印资料数据库中选取了50篇文本作为测试文本集,对上述算法所抽取出的前10位的高频词进行了人工的识别,人工识别可接受的词与抽取出的词的总数比为抽取的可接受率。实验还与中国科学院计算技术研究所汉语词法分析系统ICTCLAS^{[ 12]}的关键词分析结果作了对比。实验程序用C#语言编写,开发环境为Visual Studio 2005。算法使用了本文列出的4项优化策略,优化(4)的阈值t设定为0.25,抽取词的长度限定为最短2个字,最长不超过8个字。

实验抽取词汇的可接受率,及与ICTCLAS关键词分析对比的结果,如表1所示:

表1

表1

表1 可接受率及与ICTCLAS对比实验结果 文本数 前10位高频词人工判断 的可接受率 前10位高频词包含在ICTCLAS 前10位关键词中的比率 50 0.92 0.76

表1 可接受率及与ICTCLAS对比实验结果

本文算法与ICTCLAS关键词分析对比的部分实验结果,如表2所示:

表2

表2

表2 部分与ICTCLAS关键词分析对比数据 文章标题 ICTCLAS前10位 关键词 本文算法抽取的 前10位高频词 包含 比率 论列宁三个不同时期的全球化思想 世界、资本主义、列宁、经济、俄国、发展、全球化、国家、历史、时代 主义、资本、世界、资本主义、列宁、经济、发展、全球化、国家、社会 0.7 企业成本风险管理 成本、企业、费用、管理、产品成本、生产、信息、控制、风险、材料 成本、企业、产品、管理、费用、产品成本、信息、生产、控制、企业的 0.8 人体基因专利保护的伦理反思 基因、专利、人类、生命、利益、资源、提供、信息、价值、提供 基因、专利、基因专利、人类、生命、人的、利益、国家、发展、提供 0.6 供应链风险传导模式研究 风险、供应链、传导、企业、传递、模式、研究、节点、发出、可能 风险、供应链、传导、企业、供应链风险、风险传导、传递、模式、研究、传导模式 0.7 政治的语法—论斯密作为特殊德性的正义 正义、我们、斯密、情感、道德、社会、自己、政治、行为、政府 斯密、正义、我们、情感、道德、社会、自己、政治、行为、德性 0.9

表2 部分与ICTCLAS关键词分析对比数据

在实验的50篇文本中,算法在所抽取出的高频词人工判断的可接受率平均值达到了92%。所出现的无效词汇主要集中在“××的”、“可以”、“一个”等习惯用语上。对习惯用语这一类无效词汇,可以通过习惯用语词典的方法加以改进。在与ICTCLAS的前10位关键词对比中,平均的相同率达到了75%。实验结果发现算法在发现组合词上比ICTCLAS更具优势,能够发现在特殊语境下的组合词,如表2中的“基因专利”、“供应链风险”、“风险传导”、“传导模式”等,而这些组合词在其所对应文本中恰好能更加准确地表达文章的主题。

本文基于高频词以相同字串形式重复出现的特征,在PAT数组的基础上,利用文本后缀排序时所生成的最长相同前缀LCP数组,提出了中文高频词抽取算法。该算法的最大特点在于抽取过程不依赖于传统的分词词典,通过探测重复出现串,而不是统计字与字之间的结合程度来提取高频词,且算法能够发现在文本中重复出现的任意字的组合用法。实验结果表明算法对中文文本的高频词抽取,特别是对于新词和组合词的抽取是有效的,具有一定的实用价值。实验发现,干扰高频词抽取准确率的词主要是一些中文习惯用语,未来的工作是收集并研究习惯用语规律,进一步提高高频词抽取的可接受率。