论文部分内容阅读
摘要:该文从传统的基于FAQ库自动答疑系统的知识库存储及检索方式的不足出发,提出了知识库文档预处理及建立倒排索引结构的方法。对倒排索引文档进行重组及性能进行优化,初始化了文档的权重,提高了文档内容的检索速度。
关键词:知识库;倒排索引;答疑系统;权重
中图法分类号:TP301.6文献标识码:A文章编号:1009-3044(2009)35-10100-02
Research of Text Index in Automatic Question-Answering System
NING Ke-wei
(Xinjiang Normal University Institute of Educational Science, Urumqi 830054, China)
Abstract: From the disadvantages of the traditional knowledge saving and seaching ways based on FAQ database,this paper provide the methods about the pretreatment of knowledge database documents and the structural establishment of inverted index. Reorganizing files of inverted index and optimizing their capabilities,and initializing the weight of document,then enhance searching speed of the contents of documents.
Key words: knowledge database; inverted index; question answering system; weight
在一般基于FQA库自动答疑系统中,其问题库对应的答案基本来源WEB或者通过关系数据库存储在本地硬盘中.在系统运行过程中,用户经常问的问题、正确率高的答案被保存在FQA库做为答案直接返回给用户,另外在针某门学科答疑系统中管理员有时也把与某学科相关的资料做常识知识存储起来形成知识库提高答案的准确率。这样知识库中就存在上千万条数据,如果是单纯的数据库查询,如此大数据量对查询效率的影响不会太大,但是在答疑系统中,在检索时要进行问句的相似度计算,如果知识库每个问句都要和待查问句进行计算,那么查询时间就是非常可观的。如此巨大的知识库文本如何存储,并且如何在几秒内返回搜索结果确实是一项挑战。基于以上分析,答疑系统中的知识库不能简单是数据库中几张表,而是一个复杂的数据结构,本文根据自动答疑系统的检索特性提出一个良好的数据存储结构——索引,并对现有答疑系统的索引进行重组和优化,大大提高了系统的检索效率。
1 知识库的索引
对知识库文本建立索引方式常用的有3种,分别是倒排,后缀数组和签名文件。倒排索引被当前主流搜索引擎所广泛使用,它对关键词的检索非常有效。在倒排索引中,无论多大数量的文本数据库,总能够规范出一个关键词表,所有关键词的数量不会随文本内容的增长而线性增长。据统计对于1GB的文本信息,倒排文档的关键词表的大小在5MB左右[4]。由于倒排文档的组成特点,使得许多数学检索模型(如布尔模型,集合运算等)能够方便地用于信息检索中。因此本文采用倒排索引结构。
2 知识库索引的优化
2.1 索引文件的合并
对答疑系统的巨型知识库建立索引时若将信息存储一个索引文件中会超过操作系统限制单个文件最大容量上限。鉴于这种情况,本文在建立索引时一般将索引文件分若干文件。如果索引文件的个数无限增加,必然带来一些磁盘I/O的负担,当检索系统检索一个关键词时,其相关的文档分布大量不同的索引文件,要获得相关文档内容则需要打开每一个索引文件,并将其加载。如果此时的索引文件有成千上万个,那么对于系统的资源消耗是致命的。因此需要对索引文件数量进行一个控制,将小的索引文件合并成一个或几个大的索引的文件,以此来提高检索效率。进行索引文件合并时其原理是将所有小文件全部读入内存,在内存中进行整合,然后将内存中的数据全部写到一个新的大文件,大文件生成后将原来小文件删除。其合并过程如图1所示。
2.2 提高文件扫描性能
在建立索引的时候,系统需要频繁地访问文件,就不停地执行“文件打开”“文件读取”,“文件关闭”这就需要考虑到提升I/O性能。通常我们用系统开发语言所提供的标准文件操作函数对索引文件进行操作,其实操作系统本身也提供这些文件操作的函数如pen(),read(),write()。例如一个文件通过C函数的fopen()打开,其数据传输的路径与被open()这个系统调用函数打开是不一样的,当使用fopen()打开文件时,数据首先从用户数据空间移动到函数缓冲区间,然后随着数据在函数库中的移入移出,才移动底层的系统中,如果使用系统调用函数open(),文件操作可以饶过函数缓冲区间,数据直接从用户数据空间转移到系统底层。索引系统请求的文件大小由读或者写的系统调用决定。当请求的数据能被直接I/O(Direct I/O)操作则数据从用户数据空间直接移动设备,就可以节省管理大量的缓存带来的系统开销,否则系统调用函数能基于系统的修正的边界来创建数据缓冲区来实现I/O操作。文献[2]提出了一种使用操作系统的系统调用函数替代程序开发语言所提供的标准文件操作函数的方法,并且证明这种方法确实有很好的性能。
2.3 索引文件的压缩
当知识库文档数量很大时,索引库的容量会变得很大,占用的空间有时会超过源文档的占用空间。采用一定的压缩策略可以节约存储空间,另外检索系统执行检索需要读取一定的索引数据,采用压缩技术可以减少读取数据所需的I/O时间,从而提高检索速度。根据上节所提到倒排文档结构特点,在IX文件中的词汇表及文本号向量,IF文件中的索引词的位置信息占两个文件体积比重较大,有必对其进行压缩。本文着重从以下几个方面进行倒排文档压缩。
2.3.1 索引词的压缩
在IX文件中词汇已按照字典升序排列的,词之间前缀出现了大量的冗余。所以本文采用两种压缩方法,前方压缩,后方压缩。其作法是将词汇表调入升序队列,每个关键词后的词逐一与前一词进行比较,前方一致部分不再重复存贮,只在该词前面标上与前一词的重复的字符数。采用前方压缩处理后(如表1所示)。
为了更有效地对数据进行压缩,可同时采用前方压缩和后压缩(Rear-read Compression),后方压缩的原理跟前方压缩是一样的,只是字之间比较方向是相反,这里就不赘述。通常索引词表规模越大,压缩的效果越好,其存储空间可压缩66%左右[3]。
2.3.2 文本号向量的压缩
本文通过添加文本号向量策略来提高获取文档集合的速度,IX中需要存储大规模的文本号向量数据,其在IX中占了大量空间。从时间效率来看,由于缩小文本查找范围的速度与索引数和文本号向量的长度成正比,所以通过压缩文本号向量提高查找数速度。根据文本向量特性,通过“多阶段压缩法”[1]来压缩稀疏的文本号向量,其作法是将长度为N的文本号向量初始设定级别为1称为1级文本号向量,把1级的文本号向量按给定的一个分隔单位D位进行分割,级别数据从原来级别上加1,分割的向量为块向量,把前一级别的d个块压缩为由d个bit组成的1个块。其中前一级别的各个块内的bit值如果都是0,压缩bit的值为0,在块内有1压缩bit的值为1。对于前一级别的所有块一直重复操作。直分解到Int(Logd(n-1))级为止。例如:把N=64的文本号向量压缩成N=4的过程,其中分割单位=4,Int(Log4(64-1))=3,通过以上压缩过程能大大缩小IX的体积,保证倒排索引的检索速度。
2.3.3 索引词的位置信息的压缩
索引词的位置信息在IF(倒排文件)占较大的比重。对文档的扫描处理是顺序进行的,字符出现的位置必然是按升序排列的。根据这一特点,可以对位置序列进行压缩,首先采取差值编码的思想,减小数值的范围。例如:关键词A出现在某文档的位置为22,65,120,180,经过差值编码转换为22,43,55,60后数值降低了很多。但每个数字仍然用4个字节来是极大的浪费。对变换后的数列采用“均匀变长编码”方式将差值进一步采用短的长度表示,减少数字占用的存储空间。其方法是设计一种整数变长编码,将双字的低字节的最低2位作为数值字节长度标志位。除了2位作为标志位,字节其它位都用来保存数据。比如数值120,用二进制表示为11110000,压缩编码后的二进制表示为 00000011 11000001,可以看出大部分的增量数值只需1-2个字节表示,而无需再用4字节,节省了大量空间。
3 结束语
通常的FAQ的知识库存储是采用数据库来存放,知识库的大小直接影响了结果的好坏。一般一个专业的FAQ都有上百万的记录,如此大数据量对查询效率的影响不会太大,但是在答疑系统中,在检索时要进行问句的相似度计算,如果知识库每个问句都要和待查问句进行计算,那么查询时间就是非常可观的。如此巨大的知识库文本如何存储,并且如何在几秒内返回搜索结果确实是一项挑战。本文根据自动答疑系统的检索特性提出一个良好的数据存储结构——索引,并对现有答疑系统的索引进行重组和优化,大大提高了系统的检索效率。
参考文献:
[1] 张帆.信息存储与检索[M].北京:高等教育出版社,2007.
[2] 周宁.情报数据库系统[M].武汉:武汉大学出版社,1988.
[3] 张辉丽.计算机邻域中文自动问答系统的研究[D].天津:天津大学,2006.
[4] 赵金海.基于Web的自动答疑技术研究及系统实现[D].重庆:重庆大学,2007.
[5] 赵会杰.中文全文检索系统中索引的研究[D].北京:北京交通大学,2006.
[6] Newman H.Application Performance and I/O[Z].2001.
关键词:知识库;倒排索引;答疑系统;权重
中图法分类号:TP301.6文献标识码:A文章编号:1009-3044(2009)35-10100-02
Research of Text Index in Automatic Question-Answering System
NING Ke-wei
(Xinjiang Normal University Institute of Educational Science, Urumqi 830054, China)
Abstract: From the disadvantages of the traditional knowledge saving and seaching ways based on FAQ database,this paper provide the methods about the pretreatment of knowledge database documents and the structural establishment of inverted index. Reorganizing files of inverted index and optimizing their capabilities,and initializing the weight of document,then enhance searching speed of the contents of documents.
Key words: knowledge database; inverted index; question answering system; weight
在一般基于FQA库自动答疑系统中,其问题库对应的答案基本来源WEB或者通过关系数据库存储在本地硬盘中.在系统运行过程中,用户经常问的问题、正确率高的答案被保存在FQA库做为答案直接返回给用户,另外在针某门学科答疑系统中管理员有时也把与某学科相关的资料做常识知识存储起来形成知识库提高答案的准确率。这样知识库中就存在上千万条数据,如果是单纯的数据库查询,如此大数据量对查询效率的影响不会太大,但是在答疑系统中,在检索时要进行问句的相似度计算,如果知识库每个问句都要和待查问句进行计算,那么查询时间就是非常可观的。如此巨大的知识库文本如何存储,并且如何在几秒内返回搜索结果确实是一项挑战。基于以上分析,答疑系统中的知识库不能简单是数据库中几张表,而是一个复杂的数据结构,本文根据自动答疑系统的检索特性提出一个良好的数据存储结构——索引,并对现有答疑系统的索引进行重组和优化,大大提高了系统的检索效率。
1 知识库的索引
对知识库文本建立索引方式常用的有3种,分别是倒排,后缀数组和签名文件。倒排索引被当前主流搜索引擎所广泛使用,它对关键词的检索非常有效。在倒排索引中,无论多大数量的文本数据库,总能够规范出一个关键词表,所有关键词的数量不会随文本内容的增长而线性增长。据统计对于1GB的文本信息,倒排文档的关键词表的大小在5MB左右[4]。由于倒排文档的组成特点,使得许多数学检索模型(如布尔模型,集合运算等)能够方便地用于信息检索中。因此本文采用倒排索引结构。
2 知识库索引的优化
2.1 索引文件的合并
对答疑系统的巨型知识库建立索引时若将信息存储一个索引文件中会超过操作系统限制单个文件最大容量上限。鉴于这种情况,本文在建立索引时一般将索引文件分若干文件。如果索引文件的个数无限增加,必然带来一些磁盘I/O的负担,当检索系统检索一个关键词时,其相关的文档分布大量不同的索引文件,要获得相关文档内容则需要打开每一个索引文件,并将其加载。如果此时的索引文件有成千上万个,那么对于系统的资源消耗是致命的。因此需要对索引文件数量进行一个控制,将小的索引文件合并成一个或几个大的索引的文件,以此来提高检索效率。进行索引文件合并时其原理是将所有小文件全部读入内存,在内存中进行整合,然后将内存中的数据全部写到一个新的大文件,大文件生成后将原来小文件删除。其合并过程如图1所示。
2.2 提高文件扫描性能
在建立索引的时候,系统需要频繁地访问文件,就不停地执行“文件打开”“文件读取”,“文件关闭”这就需要考虑到提升I/O性能。通常我们用系统开发语言所提供的标准文件操作函数对索引文件进行操作,其实操作系统本身也提供这些文件操作的函数如pen(),read(),write()。例如一个文件通过C函数的fopen()打开,其数据传输的路径与被open()这个系统调用函数打开是不一样的,当使用fopen()打开文件时,数据首先从用户数据空间移动到函数缓冲区间,然后随着数据在函数库中的移入移出,才移动底层的系统中,如果使用系统调用函数open(),文件操作可以饶过函数缓冲区间,数据直接从用户数据空间转移到系统底层。索引系统请求的文件大小由读或者写的系统调用决定。当请求的数据能被直接I/O(Direct I/O)操作则数据从用户数据空间直接移动设备,就可以节省管理大量的缓存带来的系统开销,否则系统调用函数能基于系统的修正的边界来创建数据缓冲区来实现I/O操作。文献[2]提出了一种使用操作系统的系统调用函数替代程序开发语言所提供的标准文件操作函数的方法,并且证明这种方法确实有很好的性能。
2.3 索引文件的压缩
当知识库文档数量很大时,索引库的容量会变得很大,占用的空间有时会超过源文档的占用空间。采用一定的压缩策略可以节约存储空间,另外检索系统执行检索需要读取一定的索引数据,采用压缩技术可以减少读取数据所需的I/O时间,从而提高检索速度。根据上节所提到倒排文档结构特点,在IX文件中的词汇表及文本号向量,IF文件中的索引词的位置信息占两个文件体积比重较大,有必对其进行压缩。本文着重从以下几个方面进行倒排文档压缩。
2.3.1 索引词的压缩
在IX文件中词汇已按照字典升序排列的,词之间前缀出现了大量的冗余。所以本文采用两种压缩方法,前方压缩,后方压缩。其作法是将词汇表调入升序队列,每个关键词后的词逐一与前一词进行比较,前方一致部分不再重复存贮,只在该词前面标上与前一词的重复的字符数。采用前方压缩处理后(如表1所示)。
为了更有效地对数据进行压缩,可同时采用前方压缩和后压缩(Rear-read Compression),后方压缩的原理跟前方压缩是一样的,只是字之间比较方向是相反,这里就不赘述。通常索引词表规模越大,压缩的效果越好,其存储空间可压缩66%左右[3]。
2.3.2 文本号向量的压缩
本文通过添加文本号向量策略来提高获取文档集合的速度,IX中需要存储大规模的文本号向量数据,其在IX中占了大量空间。从时间效率来看,由于缩小文本查找范围的速度与索引数和文本号向量的长度成正比,所以通过压缩文本号向量提高查找数速度。根据文本向量特性,通过“多阶段压缩法”[1]来压缩稀疏的文本号向量,其作法是将长度为N的文本号向量初始设定级别为1称为1级文本号向量,把1级的文本号向量按给定的一个分隔单位D位进行分割,级别数据从原来级别上加1,分割的向量为块向量,把前一级别的d个块压缩为由d个bit组成的1个块。其中前一级别的各个块内的bit值如果都是0,压缩bit的值为0,在块内有1压缩bit的值为1。对于前一级别的所有块一直重复操作。直分解到Int(Logd(n-1))级为止。例如:把N=64的文本号向量压缩成N=4的过程,其中分割单位=4,Int(Log4(64-1))=3,通过以上压缩过程能大大缩小IX的体积,保证倒排索引的检索速度。
2.3.3 索引词的位置信息的压缩
索引词的位置信息在IF(倒排文件)占较大的比重。对文档的扫描处理是顺序进行的,字符出现的位置必然是按升序排列的。根据这一特点,可以对位置序列进行压缩,首先采取差值编码的思想,减小数值的范围。例如:关键词A出现在某文档的位置为22,65,120,180,经过差值编码转换为22,43,55,60后数值降低了很多。但每个数字仍然用4个字节来是极大的浪费。对变换后的数列采用“均匀变长编码”方式将差值进一步采用短的长度表示,减少数字占用的存储空间。其方法是设计一种整数变长编码,将双字的低字节的最低2位作为数值字节长度标志位。除了2位作为标志位,字节其它位都用来保存数据。比如数值120,用二进制表示为11110000,压缩编码后的二进制表示为 00000011 11000001,可以看出大部分的增量数值只需1-2个字节表示,而无需再用4字节,节省了大量空间。
3 结束语
通常的FAQ的知识库存储是采用数据库来存放,知识库的大小直接影响了结果的好坏。一般一个专业的FAQ都有上百万的记录,如此大数据量对查询效率的影响不会太大,但是在答疑系统中,在检索时要进行问句的相似度计算,如果知识库每个问句都要和待查问句进行计算,那么查询时间就是非常可观的。如此巨大的知识库文本如何存储,并且如何在几秒内返回搜索结果确实是一项挑战。本文根据自动答疑系统的检索特性提出一个良好的数据存储结构——索引,并对现有答疑系统的索引进行重组和优化,大大提高了系统的检索效率。
参考文献:
[1] 张帆.信息存储与检索[M].北京:高等教育出版社,2007.
[2] 周宁.情报数据库系统[M].武汉:武汉大学出版社,1988.
[3] 张辉丽.计算机邻域中文自动问答系统的研究[D].天津:天津大学,2006.
[4] 赵金海.基于Web的自动答疑技术研究及系统实现[D].重庆:重庆大学,2007.
[5] 赵会杰.中文全文检索系统中索引的研究[D].北京:北京交通大学,2006.
[6] Newman H.Application Performance and I/O[Z].2001.