改进的BM25F评分算法在文献检索系统中的应用

改进的BM25F评分算法在文献检索系统中的应用目录1系统总体架构及数据准备·································································11.1系统总体架构·························································································11.2数据准备·······························································································22搜索引擎的搭建过程·······································································42.1索引的建立····························································································42.2中文分词器的比较与选取··········································································52.3评分算法的设计与实现·············································································62.3.1BM25算法....................................................................................................................62.3.2BM25F算法..................................................................................................................62.3.3算法的编码实现...........................................................................................................83项目特色·····················································································123.1考虑查询关键词之间的距离·····································································123.2数据库表设计的优化··············································································133.3定时增量索引·······················································································144系统实现·····················································································164.1开发环境·····························································································164.2搜索结果展开及分析··············································································165总结···························································································20摘要本文主要就改进的BM25F评分算法在论文检索中的实现与应用过程进行了介绍。首先是数据集的建立过程，为了配合BM25F评分算法在结构化文档中的优势，检索对象设定为学术论文，基于万方数据库提供的文献资源通过爬虫建立了检索数据集；然后是搜索引擎搭建过程，索引使用的是倒排索引，在实现了BM25F算法之后，结合实际检索效果，从以下三个方面对系统进行了优化。（1）对BM25F进行改进，将文档中查询关键字的紧邻距离作为影响评分的一个因素加入至BM25F评分算法中。（2）优化了数据库设计，分别添加了各个域的长度字段，为各个区域长度的计算提供了便利，一定程度上提高了检索效率。（3）实现了定时增量索引，在很大程度上节省了索引创建时的开销，同时保证了数据查询的实时性，以及系统数据的可扩展性。关键词：爬虫；BM25；BM25F；紧邻距离；增量索引；《信息检索》项目报告11系统总体架构及数据准备我们改进了BM25F算法，把它用在了论文检索中，BM25F算法比较适用划分了区域的文档，如论文中的区域有标题，摘要，作者等区域，用这个算法来进行论文的检索就相当的合适。1.1系统总体架构图1-1系统架构图以上是我们这个系统的总体架构图，大致分成两块，第一块就是数据准备，即从网上把我们需要的数据用爬虫爬下来，从爬下来的html源代码解析提取出我们想要的字段，然后存储在数据库中。第二块就是当我们有了这些原始数据后，可用它来建立索引、字典等操作，然后再在这个基础上构建我们的搜索引擎，用我们改进的BM25F算法来对检索出来的论文进行排序，再把最终的结果返回给用户。我们在数据库的设计上做一些小优化，以更好地适应我们的算法，它可以在很大程序上减少计算的开销。除此之外，我们在原始的BM25F算法上也做了一些优化，详见后面的章节。《信息检索》项目报告21.2数据准备我们项目中的论文数据爬取自万方，下面是一篇论文示例：图1-2论文实例在这个页面中，划分了很多字段（或者说区域），有标题、摘要、作者、关键字等。我们主要爬取了标题、摘要、关键字、作者、作者单位这几个字段。下面是一个爬取过程的示意图：图1-3爬虫过程示意图《信息检索》项目报告3最后存储在数据库中的结果如下图所示：图1-4数据库表设计示意图从上图中可以看到，我们不仅保存了爬取到的这些字段的完整信息，还保存了去除停用词后的分词结果，以及一些比较重要的字段的长度，这极大的减小了后续进行BM25F分值计算时的计算开销。《信息检索》项目报告42搜索引擎的搭建过程2.1索引的建立我们检索系统中所用到的是倒排索引，下面给出倒排索引的相关概念，倒排索引（InvertedIndex），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。倒排索引有两种不同的反向索引形式：一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。现代搜索引擎的索引都是基于倒排索引。相比“签名文件”、“后缀树”等索引结构，“倒排索引”是实现单词到文档映射关系的最佳实现方式和最有效的索引结构。存储在MySQL数据库中的每一条记录都被表示成一个文档，我们为每一个文档建立索引。倒排索引的具体建立步骤分为两步，首先使用中文分词器对需要建立索引的文档进行分词，然后构建倒排索引表，我们还做了一个小小的处理，使得一些原来会被分词器当成两个词而分开的词，现在当成一个整体而不会被分开，例如机器学习，如果不做处理，会被分为机器、学习，这样就不符合我们期望的结果。下图是一个倒排索引表的示意图：表2-1索引文件示意表KeyWordsDocumentID[Frequency]PositionsFields机器学习1[2],2[1]2,5,2Abstract⁞⁞⁞⁞在上图所示的倒排索引表中，索引的词是机器学习，它出现的区域是摘要，它在文档1的摘要中的出现了2次，位置分别是2和5，在文档2的摘要中出现1次，出现的位置是2。这里所说的位置，都是以分词后的单词为距离来计算的，也就是说以分词后的单词为最小的单位。《信息检索》项目报告52.2中文分词器的比较与选取当前比较常用的中文分词器主要有PaodingAnalyzer、ImdictChineseAnalyzer、MMSeg4jAnalyzer以及IKAnalyzer四种，首先分别简单介绍一下这四种中文分词器。PaodingAnalyzer中文翻译为“庖丁解牛”，引入隐喻，采用完全的面向对象设计，构思先进。ImdictChineseAnalyzer是ImdictChineseAnalyzer智能词典的智能中文分词模块，算法基于隐马尔科夫模型(HiddenMarkovModel,HMM)，是中国科学院计算技术研究所的ictclas中文分词程序的重新实现（基于Java）。MMSeg4jAnalyzer用Chih-HaoTsai的MMSeg算法实现的中文分词器，并实现lucene的analyzer和solr的TokenizerFactory以方便在Lucene和Solr中使用。IKAnalyzer是一个开源的，基于java语言开发的轻量级的中文分词工具包。从2006年12月推出1.0版开始，IKAnalyzer已经推出了4个大版本。接下来将分别从用户自定义词库、效率以及算法和代码复杂度三个方面对4种分词器进行比较。（1）用户自定义词库：PaodingAnalyzer：支持不限制个数的用户自定义词库，纯文本格式，一行一词，使用后台线程检测词库的更新，自动编译更新过的词库到二进制版本，并加载。ImdictChineseAnalyzer：暂时不支持用户自定义词库，但原版ICTCLAS支持用户自定义stopwords。MMSeg4jAnalyzer：自带sogou词库，支持名为wordsxxx.dic，utf8文本格式的用户自定义词库，一行一词。不支持自动检测。IKAnalyzer：支持API级的用户词库加载，和配置级的词库文件指定，无BOM的UTF-8编码，，不支持自动检测。（2）速度以下数据来源于个分词器官方介绍。PaodingAnalyzer：在PIII1G内存个人机器上，1秒可准确分词100万汉字。ImdictChineseAnalyzer：483.64(字节/秒)，259517(汉字/秒)。MMSeg4jAnalyzer：complex1200kb/s左右，simple1900kb/s左右。IKAnalyzer：具有50万字/秒的高速处理能力（3）算法和代码复杂度PaodingAnalyzer：svnsrc目录一共1.3M，6个properties文件，48个java文件，6895行。使用不同的Knife切不同类型的流，不算很复杂。ImdictChineseAnalyzer：词库6.7M（这个词库是必须的），src目录152k，20个java文件，2399行。使用ICTCLASHHMM隐马尔科夫模型，“利用大量语料库的训练来统计汉语词汇的词频和跳转概率，从而根据这些统计结果对整个汉语句子计算最似然的切分”MMSeg4jAnalyzer：svnsrc目录一共132k，23个java文件，2089行。MMSeg算法，有点复杂。IKAnalyzer：svnsrc目录一共6.6M(词典文件也在里面)，22个java文件，4217行。