全文检索单元词索引技术研究

全文检索单元词索引技术研究

!信息系统#ITA

●靖培栋　宋雯斐(北京师范大学管理学院　北京　100875)

全文检索单元词索引技术研究

摘　要:单汉字索引是中文全文检索索引技术中一个主要方法,此方法在索引的空间和检索的效率方面都存在不足。本文引入单元词索引,并分析试验数据,表明引入单元词索引后,索引的空间效率和检索的时间效率均有提高。

关键词:信息检索;全文检索/单元词索引;检索方法

Abstract:ThefulltextretrievalsystembasedonsingleChinesecharacterindexingisdeficientinindexingspaceandretrievalfeedback.Thispaperusesunittermindexingtoreduceindexingspaceandimproveretrievalfeedback.Thetestdataprovesittobeaneffectivemethod.

Keywords:informationretrieval;fulltextretrieval/unittermindexing

全文检索技术的出现,命。,如对标题、作者、、,计算机文,建立系统时对文献进行分类,并给出关键词或主题词,结果造成所描述的文献概念化,总不能反映出文献所有的内容,因而在查全率、查准率方面就有所欠缺;全文检索不仅可以实现以前信息检索的绝大部分功能,而且还能直接根据信息的内容进行检索,实现了支持多角度、多侧面综合地利用信息资源。

以词为单位建立索引需要对原始文献进行分词处理,这种标引技术的难点是分词,分词需要词典和分词规则的支持,这两项都是有待提高的技术难点。

单汉字标引法则是利用计算机自动标引,将文本正文中的每个汉字均作为标引词,不加选择地进行标引。单汉字标引技术一般采用倒排文件的索引形式。单汉字标引技术避开了语词切分的问题,增强了标引的客观性和一致性,也节省了索引建立的时间。

,因此检索时,都要经过二次、三次乃至,耗时较多,因而降低了系统检索的速度。④单汉字索引为原文中每个汉字建立倒排文件索引,需要耗费大量的存储空间,对于大型检索系统,这也是一个不可容忍的缺陷。

如何对上述问题进行优化处理,是目前基于单汉字索引全文检索系统的研究重点。我国学术界对此也已作过许多研究。

比如以“建立停用词表”来减少索引的空间,对原文中的无检索价值的虚字或是分辨率低的字不做索引,如对们不作索引以减轻索引的空间消耗[1]。这种方法缓解了单汉字索引带来的空间压力,却违背了全文检索索引全面性的初衷,可能造成漏检。

对索引的压缩,学者们还提出对索引的位置信息进行面向分组的编码压缩和面向位流的编码压缩。这两种方法都是对索引中的位置信息(即整数序列)进行压缩,用尽量少的字节数来表示这些位置,具体方法见参考文献

[2]。这样的索引压缩存储,用户再进行检索时,需要对

全文检索系统的核心技术是建立基于词或字的索引。“的”、“地”、“得”、“吗”等冗余字建立停用词表,对它

1　单汉字索引存在的不足之处及已有对策

单纯的单汉字标引技术的不足是:①它遮蔽了概念主题和词汇间的关系,检索时容易出现误检和漏检。比如检索“鲁迅”时,其他笔名及真名“周树人”、“周豫才”等就可能被漏检,查全率得不到保证。②由于单汉字索引系统并不理解词语的意义,不指定不同词间的相互参照关系,因而其检索结果的扩检、缩检都很难实现。③一般用户都是以词作为完整的概念词进行检索提问的,词一般都

读取的信息进行解码操作,解码得到最直接的索引信息后,才得到检索结果,这在一定程度上牺牲了检索速度,增加用户检索时还原索引所需的时间。

对于检索效率的改进问题,人们提出了“串检索”的概念,以检索词的第一个字为基础,采用前方一致的搜索单汉字索引,没有该字,则立即显示落选信息;有该字则根据该字的索引信息取出原文,采用字符串匹配形式确定该记录是否符合检索要求。“首字定位,全词匹配”的检索算法,在提高运行效率的同时也提高了算法的清晰度。

—118— 第29卷2006年第1期

全文检索单元词索引技术研究

ITA

当检索词首字的集合较大时,“全词匹配”所进行的实际上是顺序检索,并不能节省检索时间。

上述这些缺陷,或是节省了空间却影响检索效果、检索速度;或是提高了速度而以检索效果为代价。综合单字索引思想和后控词表带来了检索效果的提高。本文为全文检索系统引入新的单元词索引概念。

!信息系统#

其依据的文章都集中在中华人民共和国成立之初到改革开放之前的这段时间内,对解放前及改革开放后的文章未做统计,并且这三个时期中国的状况是完全不同的,所以全面性欠缺,但这并不妨碍本系统的试验性运行。

312　原文库及单元词索引可行性分析

本系统以《邓小平文选》作为全文数据库。录入《邓小平文选》第一卷共41篇文章,每篇文章分段入库,共

946个记录。经统计,全文库容量约20M,共167948个汉

2　引进单元词索引

这里的单元词概念源自传统手工标引中元词的概念,元词是直接从文献中抽取出来能表达文献主题的最小和最基本的词汇

[3]

字,并且文档中的字剔除重复汉字共2432个。假设平均每个字在m个记录中出现,根据字索引倒排档结构,可以计算出索引倒排档的空间大小:40M+2432×2(记录记录数的空间)+2432×m×2<45M,索引倒排档的膨胀系数小于01125。见表1。

,单元词索引的标引词就是这些词,然后根

据这些词汇(即元词)的组配来表达复杂概念。进行全文索引时,只记录单元词首字位置,而对单元词的其他单字不作索引,这样大大减少了倒排文件索引的空间;并且这些单元词是表达主题的最小词汇,因而不损害原文的标引全面性和标引深度。

单元词是最小和最基本的词汇,能表达一个完整的意思,,不具有检索意义。速度,比如一个由n,如果用单字索引进行检索,就得经过n-1次的集合乘积操作,而采用单元词索引可以把检索语句分解成若干个单元词、字的组合,可以大大减少集合乘积操作的次数,弥补字索引的查询速度不快的缺陷。

汉语的词是一个开放的集合,数量丰富接近无穷,因而想要收集到所有的词太过理想化,是不可能的。单元词表的选择还得依照词频统计词典来确定。

94640MB167948

去重后汉字个数2432(其中一级汉字2174,二级汉字258个)<45MB

1)空间分析。目前的索引倒排文件稍大于全文库正

文,这在全文数据量小的系统中是可以的,但对于海量的数据库系统,如果全文库规模是几百兆、甚至是G、T级别的,字索引倒排文件所需的系统空间就显得喧宾夺主了,需要对其进行压缩。

在本系统的全文数据库中,汉字的频率相对集中,频率500以上常用的近70个汉字,共占用了71364个汉字空间,占了需作索引的汉字的4215%,也就是说这些汉字的索引在字索引倒排文件中占了约4215%的空间。如果可以对这些汉字索引进行压缩,效果一定很明显。这就是引入单元词索引的结果。

频次500以上的汉字中许多都可以组合成单元词,并且这些单元词在《现代汉语频率词典》的报刊政论类词统计中都作为高频词出现。比如全文数据库中,“主”出现了

1199次,“义”出现了583次,而它们的组合单元词“主

3　系统试验

鉴于以上考虑,笔者开发了《邓小平文选》全文检索系统进行试验,在此系统中使用了单元词索引。

311　单元词表构造

本系统建立单元词表的目的有别于分词系统和计算机自动标引系统,它依赖于现有的词频统计词典,从中选取高频词纳入单元词表。同分词系统的词典构造一样,该选取什么样的词入库直接影响到单元词表功能效果。本系统采用《现代汉语频率词典》的报刊政论(包括经济、政治、哲学、法律、历史、地理等)类词,使用了出现频度最高的4000个字词,并去掉对相应字的索引。《现代汉语频率词典》中报刊政论类词统计来源于1951—1981年《人民日报》、《光明日报》、国家领导人的报告及法律、政治、历史、地理等方面34种语料,这与《邓小平文选》的主题基本一致,都是政论性的文章,因而措辞用语比较相似,具有较强的参考价值。但是,由于该词频词典出版年份较早,

义”是《现代汉语频率词典》的报刊政论类词统计中频次最高的词(除去单字)。还有类似的例子,比如“我们”、“人民”、“工作”、“问题”、“同志”、“群众”等高频单元词的字在全文数据库中都是频次在500以上的高频汉字。因此,单元词索引在压缩字索引倒排文件空间上具有非常乐观的效果。具体的统计分析在单元词索引部分完成。

2)效率分析。引入单元词索引还有一个原因是用户

检索时字索引的效率问题。单汉字索引系统的检索方案有

情报理论与实践 —119—

全文检索单元词索引技术研究

!信息系统#

两个,以一个有n个汉字的提问式为例,一种检索方案是从字索引倒排文件中找出这n个汉字的位置信息,然后进行n-1次的汉字索引集合的逻辑乘运算,找出符合提问式的全文记录。

按照用户的用词习惯,用户在构造检索串时多以词来表达。一般来说,某字在全文库中出现的频率都会大于它与其他字组成词出现的频率,这样间接减少了首字(首词)的索引集合,不管采用上面两种方案中的哪种,都提高了检索效率。

313　试验结果分析

ITA

势是不言而喻的。索引空间可节省约46770/167948≈28%,也就是说,添加了单元词索引的全文检索系统的索引空间约为全文库容量的72%,即索引空间膨胀率为-0128。相信如果单元词表进一步完善的话,效果会更明显。

2)效率分析。单元词索引的建立,不仅在索引的压

缩上贡献甚大,在用户检索上也能明显地提高系统反馈速度。单元词表中索引不为空的1208个单元词,共索引了

93132个汉字,而实际需要作为索引的位置只有46362个(每个单元词只有首字做了索引)。假设一个检索提问字符

串中有n(n≥2)个汉字,如果是字索引,那就要进行n

-1次的逻辑乘操作。下面考虑有单元词索引后的情况。

字索引的空间膨胀率一般大于0,我们建立的字索引倒排文件也稍大于全文数据库,而词索引空间膨胀率则一般在-015～0之间。空间膨胀率是索引文件大小减去全文数据大小后,与全文数据的比值,这个比值的大小关系到资源占用的多少和查询速度的快慢。

系统单元词表的收词情况前面有所提及,并且已经进行单元词索引的创建,2这n个汉字中某个字,不是单元词中的字的概率f是

(167948-93132)/167948≈4415%,而单元词的平均词长(AVGLength)是93132/(三音节或三音节以上

)。

,。可以根据检索串不同的出现概率,进行其平均检索效率的比较(不计字、词在文中出现的频次差异,既不考虑进行逻辑乘操作的两个索引在数量上的差异,也忽略一个字的单字索引和以此字为首的单元词索引在数量上的差异)。

n=2,单汉字索引需要进行1次逻辑乘操作,而有了

表名称

单元词数

单元词在文中出现的频率频率为0的单元词个数

实际被作单元词索引的数目

资源数

1405

46362(其中双音节45969,三音节)

197

120846770

46770×2B=93540B

单元词索引的检索分析见表3。

表3　n=2时的检索分析

序号

12

少作索引汉字个数

节省索引空间

组成形式

2个单字:××1个单元词:××

出现概率逻辑乘次数

0144501555

10

1)空间分析。现时市场上的全文检索系统的膨胀率在-012～110之间,但是由于全文检索系统的商家不公开其索引技术,因此索引的创建、索引文件的压缩方法我们也就无从知晓,但仍可以收集到一些数据。比如,著名的中文全文检索系统TRS全文检索服务器(TRSServer),在其产品说明书中指出,“内嵌智能汉语自动分词系统”,“支持按词索引、按字索引、按关键词索引、字词混合索引”,“高效的数据和索引压缩,实现了低空间膨胀率(-[4]012～110)”;汉王科技的汉王数字图书馆系统,在其解

n=3,单汉字索引需要进行2次逻辑乘操作,而有了单元词索引的检索分析见表4。

表4　n=3时的检索分析

序号

123

组成形式

3个单字:×××1单元词1字:×××1单元词1字:×××

出现概率

01445×01445

0155501445×01555

逻辑乘次数

211

n=4,单汉字索引需要进行3次逻辑乘操作,而有了单元词索引的检索分析见表5。

表5　n=4时的检索分析

序号

12345

决方案中描述到“汉王采用多种数据和索引压缩技术,使得空间膨胀率达到创纪录的010～013左右”,可以看出要使索引空间膨胀率达到负值(即索引空间膨胀比小于

1)有相当的难度;还有北京新星快威数码技术有限公司

[5]

组成形式

4个单字:××××1单元词2字:××××1单元词2字:××××1单元词2字:××××2单元词:××××

出现概率

01445×01445×01445

01555×0144501445×0155501445×01445×01555

01555×01555

逻辑乘次数

32221

的DIPS数字文献处理系统,它的数据库全文检索性能指标中有一项是“索引膨胀率低:索引空间膨胀率-011～

[6]013”。

从表2中可以看出建立了单元词索引后索引空间的优

—120— 第29卷2006年第1期

全文检索单元词索引技术研究

ITA

n=5,单汉字索引需要进行4次逻辑乘操作,而有了单元词索引的检索分析见表6。

表6　n=5时的检索分析

12345678

!信息系统#

少,从而节约了存取时间。

4　结束语

逻辑乘次数

43333222

引入了单元词索引的全文系统既节省了索引空间,也提高了系统的检索反馈速度,并且基本不影响全文检索系统的索引全面性。本文采用了《邓小平文选》作为全文库及词频统计词典中时政类词单元词表的取词依据,具有特殊性。但如果要构造其他类型文献的全文检索系统,并采用合适的词频统计词典作为单元词表的选词依据,也是可行的。□

参考文献

1　黎小林,吴骏盛.单汉字机助标引和检索.情报学报,1988,

7(1):29～33

2　余海燕,张仲义.组成形式

5个单字:×××××1单元词3字:×××××1单元词3字:×××××1单元词3字:×××××1单元词3字:×××××21:21:2单元词1字:×××××

出现概率

01445×01445×01445×0144501555×01445×0144501445×01555×0144501445×01445×0155501445×01445×01445×01555

0555055505550445055501445×01555×01555

虽然只计算了n取值为2、3、4、5的情况,但足以说明检索效率的提高。

上面对检索字符串的出现概率,只单纯地从字、单元词在原文中出现的概率来定义,用语习惯。事实上,,字或词中,的内容。,就应该大于目前的5515了,检索的效率可以有一个新的提高。

单元词索引对检索效率的贡献不只在于减少字、词间的逻辑乘操作,而且它可以减少对索引文件的存取。检索字符串经“分割”后,使得组成检索字符串的元素个数大大减少,系统需要从索引中读取字、词的位置信息次数减　　(上接第124页)

出来,其实这是一个信息的再组织和加工过程。通过社会书签可以很方便地查看和管理有用的网页,可通过摘录网页形式与别人分享。书签还可以摘录一些网页内容,将内容标题和网页地址发布到网摘网站的首页上,让其他浏览者也可以看到这些信息,可以看到其他网友推荐的网页。网页评述是对保存的网页添加评论的,而网页简介或摘要则是保存网页原文中的一部分内容。为方便阅读,一般都有内容分类,有的还有热门网摘排行榜栏目,可通过关键词搜索方式检索到需要的内容。网摘的价值在于网站管理员或者其他用户将其觉得最有价值的内容推荐给广大网民,从而节省网民在海量信息中挑选自己感兴趣内容的时间。网摘的意义还在于分享与发现,它实质上是个人兴趣在互联网中的传播过程。网摘将互联网资源搜集、过滤、整理后,向特定用户群提供服务,在海量信息遴选过程中选取有价值的内容,并归类组织管理,从而实现了网络信息的增值利用[9]。□

.,,):　14～19

3..:北京大学出版社,

全文检索服务器TRSServer./products/trsir2ckm/trsserver/index.jsp,2003205

5　汉王数字图书馆解决方案./hw/tech

03.htm,2003205

6　DIPS数字文献处理系统功能特性.2quick.

/ziye/7.htm,2003205

作者简介:靖培栋,男,1964年生,博士,教授。

宋雯斐,女,1979年生,硕士生。

收稿日期:2005-07-27

参考文献

1　刘斌.Bookmark———智能化网络信息服务系统.高技术通讯,

1999(6):38～42

2　文心.博大家之长,采草根之智./

146/2005201226/28598.html,20052062083　,2005206208

4　/,20052062085　,20052062086　/,2005206208

7　孟宪福.网上Bookmark服务系统及其基于Web挖掘的推荐引

擎.小型微型计算机系统,2001,22(12):1485～1488

8　TonyH,HannayT.SocialBookmarkingTools(I):GeneralOverview.

D2LibMagazine,2005,11(4)

9　王翌.网摘:分享互联网.计算机世界,2005203228

作者简介:黄晓斌,男,副教授,博士。主要研究方向:

数字图书馆技术、网络信息资源开发与利用,发表论文100多篇,出版著作(含参加编写)

8部。

收稿日期:2005-07-07

情报理论与实践 —121—

本文来源：https://www.bwwdw.com/article/0sm4.html