高性能检索子系统

高性能检索子系统主要内容检索系统基本技术倒排文件性能模型混合索引技术倒排文件缓存机制本章小结第2页,共89页，2024年2月25日，星期天主要内容检索系统基本技术倒排文件性能模型混合索引技术倒排文件缓存机制本章小结第3页,共89页，2024年2月25日，星期天检索系统基本技术系统设计与结构索引创建检索过程第4页,共89页，2024年2月25日，星期天检索系统基本技术系统设计与结构索引创建检索过程第5页,共89页，2024年2月25日，星期天检索系统基本技术

-系统设计与结构搜索引擎检索系统设计遵循的指标检索效率—用户查询的响应时间用户的需求是“随心所欲的”响应迟缓的系统只能意味着较少的用户检索效果—用户的满意度搜索引擎的检索技术相对于最新的信息检索研究成果是落后的提高检索效果面临的问题用户普遍使用短查询、不作优化相关度计算第6页,共89页，2024年2月25日，星期天检索系统基本技术

-系统设计与结构用户查询请求检索代理布尔查询元数据全局属性语义约束SEServicePointIndexingServicePoint天网检索系统集成框架结构第7页,共89页，2024年2月25日，星期天检索系统基本技术

-系统设计与结构天网检索系统的设计原则系统效率和可扩展性通过集成的框架结构，能够有效地把各种有利于改善检索效果的技术集成起来天网系统框架文档表示用户信息需求的类型识别不同检索排序方式得到的结果的融合第8页,共89页，2024年2月25日，星期天检索系统基本技术

-系统设计与结构天网系统的实现基于信息检索技术排序算法和模型的选择模型布尔模型向量空间模型检索系统的相关性排序由多种因素综合决定查询词的邻接关系运算结果查询词出现的位置，包括Title、AnchorText相似度权值与其他的权值，如全局属性的PageRank值第9页,共89页，2024年2月25日，星期天检索系统基本技术

-系统设计与结构索引的实现技术采用倒排文件索引索引文件的组织结构链表有利于提高更新效率，但会降低检索效率索引项数据连续存放有利于提高检索效率，但不利于更新索引文件的压缩第10页,共89页，2024年2月25日，星期天检索系统基本技术

-系统设计与结构检索系统采用分布式系统结构WWW1WWWnindex1index2indexNdoc1doc2docMWeb查询服务节点索引服务节点文档服务节点Internet检索服务系统共使用20台PC（PIII733/1GB）一台为WWW查询服务器，其余19台为索引服务器，文档服务节点和WWW查询服务器使用同一机器第11页,共89页，2024年2月25日，星期天检索系统基本技术系统设计与结构索引创建检索过程第12页,共89页，2024年2月25日，星期天检索系统基本技术-索引创建索引词选择索引词的选择是检索系统实现的一个重要环节中文文本必须通过自动分词程序的处理基于词典的分词方法基于统计语言模型的分词方法英文文本统一转换为小写，但不作词根词形变换第13页,共89页，2024年2月25日，星期天检索系统基本技术-索引创建网页预处理编码转换GBK、GB2312、GB18030……简繁转换简繁并不是一一对应的发（發、髮），台（臺、檯、颱）大量网页不符合HTML规范、网页中存在大量无用的信息（广告、导航条）第14页,共89页，2024年2月25日，星期天检索系统基本技术-索引创建索引创建算法页面分析按HTML语法规则分析网页标签结构提取索引词记录每个索引词的TF（词频）DF（文档频率）值通过散列表转换为索引词编码，保存得到的词典文件保存页面分析的结果到临时文件第15页,共89页，2024年2月25日，星期天检索系统基本技术-索引创建生成临时倒排文件根据计算的TF和DF值，可以估算出倒排文件中相应数据项的长度，预申请整个文档集合倒排所需要的内存空间重新读取页面分析保存结果的临时文件，在内存中执行倒排，把结果保存到临时倒排文件中对生成的多个临时倒排文件，执行多路归并、压缩编码，输出得到最终的倒排文件第16页,共89页，2024年2月25日，星期天检索系统基本技术系统设计与结构索引创建检索过程第17页,共89页，2024年2月25日，星期天检索系统基本技术-检索过程索引压缩优点减小倒排项数据长度减少内存和I/O带宽的使用缺点对压缩数据解码，增加了CPU时间消耗方法字节对齐索引压缩变长索引压缩第18页,共89页，2024年2月25日，星期天检索系统基本技术-检索过程字节对齐索引压缩用少量最左边的比特位（bit）表示整数实际占用的字节数优点容易编码和解码位操作少，占用CPU时间少缺点压缩效率低每个整数至少占用一个字节的空间第19页,共89页，2024年2月25日，星期天检索系统基本技术-检索过程整数大小需要字节0=<x<64164=<x<16,384216,384=<x<4,194,30434,194,304=<x<1,073,741,8244可变长字节表示的整数第20页,共89页，2024年2月25日，星期天检索系统基本技术-检索过程变长索引压缩一元编码整数x编码成x-1个比特位，后跟一个0表示结束104111071111110210511110811111110311061111109111111110第21页,共89页，2024年2月25日，星期天检索系统基本技术-检索过程γ编码将整数x分成两个部分1+[logx]和x-2[logx]1+[logx]用一元编码实现x-2[logx]用[logx]比特位的二进制编码表示整数一元编码γ编码10021010031101014111011000511110110016111110110107111111011011811111110111000091111111101110001第22页,共89页，2024年2月25日，星期天检索系统基本技术-检索过程δ编码将整数x分成两个部分1+[logx]和x-2[logx]1+[logx]用γ编码实现x-2[logx]用[logx]比特位的二进制编码表示当整数小于15时，δ编码比γ编码编码长，大于15时，δ编码优于γ编码整数一元编码γ编码δ编码10002101001000311010110014111011000101005111101100110101611111011010101107111111011011101118111111101110000110000009111111110111000111000001第23页,共89页，2024年2月25日，星期天检索系统基本技术-检索过程随机访问的索引组织对索引项建立二级索引，使得可以随机访问倒排项数据块数据块的大小小数据块访问频繁系统调用寻道时间消耗较大大数据块访问读入冗余数据数据传输时间消耗较大天网使用32K为最小块单位第24页,共89页，2024年2月25日，星期天检索系统基本技术-检索过程重要索引词单独索引可以产生小的倒排索引文件，保存在内存中查询在小索引文件中获得足够的返回结果，则查询结束当查询得到的结果不足时，去访问磁盘上的整个倒排文件重要索引词包括AnchorText、Title，文摘中的词第25页,共89页，2024年2月25日，星期天主要内容检索系统基本技术倒排文件性能模型混合索引技术倒排文件缓存机制本章小结第26页,共89页，2024年2月25日，星期天倒排文件性能模型大规模信息检索系统的主要指标效果：即质量，指检索返回结果集合的准确性和完整性（准确率、召回率，第十章中介绍）效率：即性能查询响应时间（responsetime）从用户想系统提交查询到他开始看到结果的时间间隔查询吞吐率（throughput）系统在单位时间（秒）里可以服务的最大用户查询数量第27页,共89页，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一种性能模型结合计算机性能指标的考虑第28页,共89页，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一种性能模型结合计算机性能指标的考虑第29页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念倒排文件（InvertedFile）是描述一个词项集合（terms）元素和一个文档集合（docs）元素对应关系的数据结构词项：可以是英文的单词，也可以是中文的字或者词terms={t1,t2,t3,……tM}docs={d1,d2,d3,……dN}M：词项集合的大小N：文档集合的大小第30页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念M词项总数记录表（PostingLists）不同词项组成的索引Vocbulary每个词项出现过的文档集合第31页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念几个相关的变量sj=|PL(tj)|词项tj

所涉及的文档的个数DF(tj)=sj/N词项tj

的文档频率IDF(tj)=-lgDF(tj)‏倒置文档频率，值越小表示出现频率越高第32页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念fi,j第j个词项tj

在第i个文档di

中出现的次数

系统所有文档包含词项的总量（包括重复）

词项tj

在所有文档中出现的频度ITF(tj)=-lgTF(tj)‏倒置词频，越小表示出现频率越高第33页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念M词项总数N文档总数sjp(i)：倒排表长度分布q1q2……qk同时到达的查询r：响应时间B系统最大输出带宽S：实现吞吐率第34页,共89页，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一种性能模型结合计算机性能指标的考虑第35页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型性能模型就是要给出N、M、p(i)、d、B、r和k的一种关系N：文档总数M：词项集合的大小p(i)：倒排表长度分布d：文档平均数据量B：系统最大输出带宽r：响应时间K：同时到达的查询的数量第36页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型对p(i)和B的说明p(i)是倒排表长度的统计分布函数M*p(i)的长度表示i的记录表的个数，i∈[0,N]倒排表的平均长度为第37页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型B是系统最大输出带宽，是支持倒排文件运行的下层系统的瓶颈带宽磁盘的I/O带宽网络带宽根据同时到达的查询量k，得到一个数据量D，看能否有：针对查询q1,q2,q3,……qk的假设它们都属于集合terms它们在terms上随机、独立分布对于磁盘I/O带宽和网络带宽不作区别第38页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型倒排文件性能的基本模型考察k个查询导致的输出数据量D每个查询可能落到M个词项中的任何一个k个查询可能涉及M的任何1,2,……k项，对应不同的数据量计算涉及i项的概率fm,k(i)，i=1,2,3,……k第39页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型D=一个倒排表的平均数据量*k个并发查询平均涉及的倒排表个数第40页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型考虑全文索引与非全文索引非全文索引：只考虑哪些文档含有特定的词项全文索引：还要考虑该词在相关文档中出现的位置信息全文索引的情况下，每个倒排表的数据量正比于文档号和频率位置信息占用的长度第41页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型TN（所有文档中词的集合）远远大于N系统中每个词项倒排表的长度主要由词频率TF和数据规模TN决定的平均情况下非全文索引全文索引C表示了为记录一个词项在文档中一次出现位置信息所需的数据量第42页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型倒排表的长度影响操作执行的时间索引网页量增加时，高频词项的倒排表将急剧膨胀，占用大量I/O带宽、内存空间、CPU时间，降低系统效率理想情况：所有词项频率尽可能低，而且大小相近，使得所有倒排表同步增长。词项的频率分布和语言相关第43页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型频率英语单词（E）汉语字符（H）0.1%1032520.07%1483480.05%2204750.02%6328670.01%128512150.007%178014000.005%238116090.002%547422100.001%67132676英汉词频统计排序对照第44页,共89页，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一种性能模型英语单词和汉语字符的ITF分布第45页,共89页，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一种性能模型结合计算机性能指标的考虑第46页,共89页，2024年2月25日，星期天倒排文件性能模型

-结合计算机性能指标的考虑决定系统性能的关键I/O的性能磁盘I/O网络I/ODiskModelSize(GB)‏AverageaccessTime(msec)‏RPMRandomIOPSInternalTransferRate(MB/s)‏InterfaceIBMUltrastar36ZX365.41000011915~29Ultra160QuantumAtlasV36.76.310000107.517~29Ultra160SeagateCheetahX1518.43.915000169.538~47FC-ALSeagateCheetah7373.45.61000011626~40Ultra160第47页,共89页，2024年2月25日，星期天倒排文件性能模型

-结合计算机性能指标的考虑提高磁盘I/O性能的方法Ultra160SCSI，最高带宽可达150MBps当前单个磁盘的平均数据传输率在20~50MBps之间解决办法RAID：冗余磁盘阵列技术第48页,共89页，2024年2月25日，星期天倒排文件性能模型

-结合计算机性能指标的考虑系统吞吐量与倒排表索引的数据量假设将每个倒排表读入内存只需一次I/O，所花费的时间为Tlatency：磁盘访问平均延迟时间（s）IObandwith：I/O可用带宽（Bps）TN：所有文档包含的词项总量TF：频率第49页,共89页，2024年2月25日，星期天倒排文件性能模型

-结合计算机性能指标的考虑每次读取倒排表的时间乘Lq*m不大于1秒当I/O系统性能（Tlatency、IObandwith）和TF确定下来后，可以看到TN和m之间成反比关系假设IOPS=100，Lq=5，则系统平均每秒处理查询的上限是m=IOPS/Lq=20如果磁盘的可用带宽为20MBps，则每个查询的I/O小于1MB第50页,共89页，2024年2月25日，星期天倒排文件性能模型

-结合计算机性能指标的考虑根据上式，可得出如下结论对汉字字符：TN=<400MB（TF=0.05%，Lq=5）对英文字符：TN=<4GB（TF=0.005%，Lq=5）第51页,共89页，2024年2月25日，星期天主要内容检索系统基本技术倒排文件性能模型混合索引技术倒排文件缓存机制本章小结第52页,共89页，2024年2月25日，星期天混合索引技术混合索引原理混合索引实现第53页,共89页，2024年2月25日，星期天混合索引技术混合索引原理混合索引实现第54页,共89页，2024年2月25日，星期天混合索引技术-混合索引原理索引技术面临的问题通过自动分词来选择索引词分词单位是指具有确定语义或语法功能的基本单位目前，中文自动分词的成熟技术都是基于分词词典的机械型分词方法网上大量的常用词、新出现词、专业词汇，词典中没有收录分词词典的分词单位一般很短，导致常用的短语也会被分词程序且分开第55页,共89页，2024年2月25日，星期天混合索引技术-混合索引原理混合索引技术用统计的方法对索引文档中的未登录词进行识别，把识别出的新词（词典中未收录的字串）放入一个扩展词典有效扩大词典的规模统计的方法存在相当的错误率天网中，扩展词典的规模控制在50万词左右第56页,共89页，2024年2月25日，星期天混合索引技术-混合索引原理索引创建过程中首先是基于基本分词词典的常规分词对基本分词结果使用基于扩展词典的分词两次的分词结果都被选择作为索引词例如：基本词典中有“国家”、“图书馆”两个基本词条，无“国家图书馆”系统通过未登录词识别，把“国家图书馆”加入扩展词典文档中出现“……国家图书馆……”字串，第一遍分词得到“国家”、“图书馆”两个基本词条，第二遍得到“国家图书馆”最终索引词包括“国家”、“图书馆”、“/2国家图书馆”三个单位。“/”表示转义符，后面数字表示扩展词包含的基本分词词条个数第57页,共89页，2024年2月25日，星期天混合索引技术-混合索引原理对用户输入的查询串的处理首先是基于基本分词词典的常规分词对基本分词结果使用基于扩展词典的分词例如用户输入查询“国家图书馆”经过两遍分词，得到“国家”、“图书馆”、“/2国家图书馆”三个单位前两个基本词条被第三个扩展词条覆盖，查询执行时只需直接读取索引词“/2国家图书馆”对应的倒排项数据，即可完成查询第58页,共89页，2024年2月25日，星期天混合索引技术-混合索引原理混合索引vs.短语索引混合索引使用统一的倒排索引词典，没有额外的二级索引词典访问开销混合索引不限制扩展词条为两个基本词条长，可以索引更长的短语，更加灵活混合索引vs.词索引+Bi-gram混合索引使用了未登录词识别技术，可以有效控制倒排索引词典规模，避免了Bi-gram词典膨胀的问题第59页,共89页，2024年2月25日，星期天混合索引技术混合索引原理混合索引实现第60页,共89页，2024年2月25日，星期天混合索引技术-混合索引实现未登录词的识别提取n元组使用基本词典，将文本进行部分分词，从部分分词结果中提取n元组单字，只有连续出现的单字才能生成n元组形成新词的n元组必须包含一个单字噪声剔除删除那些包含低构词能力字的n元组第61页,共89页，2024年2月25日，星期天混合索引技术-混合索引实现剔除n元重叠把那些在n取不同值情况下重复被提取的n元组剔除最后剩下的n元组按出现频次降序排列，为识别结果第62页,共89页，2024年2月25日，星期天混合索引技术-混合索引实现扩展词典组织与分词输入基本分次结果序列，找到序列中在扩展词典里的所有最长匹配词条基本词典和扩展词典中的词典均按照整数编码进行存放市……大学……NULL生NULL北京NULL第63页,共89页，2024年2月25日，星期天混合索引技术-混合索引实现扩展词典匹配查找算法输入：基本分次结果词条序列（t1,t2,……ti）输出：最长匹配扩展词条init_scoreboard();初始化匹配任务表while（ti!=EOF）{code=get_code(ti);从编码三列表中取得ti的编码foreachtaskinscoreboard{ret=search_token(code);测匹配任务追加一个词，是否结束？if(ret==NULL){clear_taskadd_hit;得到一个匹配}elseupdate_task;根据检测结果更新匹配任务状态}check_hit；检测匹配结果，输出}第64页,共89页，2024年2月25日，星期天主要内容检索系统基本技术倒排文件性能模型混合索引技术倒排文件缓存机制本章小结第65页,共89页，2024年2月25日，星期天倒排文件缓存机制搜索引擎检索系统中通常被研究的缓存对象查询结果用户查询具有很强的局部性，因此对查询结果进行缓存是可行的布尔操作的中间结果把布尔查询的中间结果作为缓存对象，并利用查询结果间的语义关系加速后续查询的执行倒排文件用户查询经过查询器执行，转换为对倒排文件数据的访问序列，这些数据也可以作为缓存的对象第66页,共89页，2024年2月25日，星期天倒排文件缓存机制倒排文件缓存负载特性缓存策略的选择第67页,共89页，2024年2月25日，星期天倒排文件缓存机制倒排文件缓存负载特性缓存策略的选择第68页,共89页，2024年2月25日，星期天倒排文件缓存机制

-倒排文件缓存体系结构倒排文件倒排文件缓存查询执行器查询结果缓存用户查询结果查询服务器索引服务节点第69页,共89页，2024年2月25日，星期天倒排文件缓存机制

-倒排文件缓存用户提交的查询中包含查询词的个数通常很少，词间的位置临近关系对结果排序十分重要天网使用带位置数据的全文倒排索引，对多个词的用户查询计算临近权值查询执行器访问倒排文件的数据分为两类查询词对应的倒排表中的文档编号和文档内权值数据文档数据查询词对应的出现在每篇文档中的位置数据位置数据第70页,共89页，2024年2月25日，星期天倒排文件缓存机制

-倒排文件缓存执行过程各个查询词按倒置文档频率降序处理读取文档数据，执行文档集合的布尔运算，得到一个小的结果集合使用文档内权值数据计算每个结果文档对查询的相关性读取对应的位置数据，对结果集合进行邻近权值排序第71页,共89页，2024年2月25日，星期天倒排文件缓存机制

-倒排文件缓存名称数值名称数值用户查询总数7,341,383I/O序列长度1,887,198结果缓存未命中个数3,522,968I/O序列唯一对象数112,145文档总数2,603,035PAGE序列长度20,808,025文档数据原始大小30.18GBPAGE序列唯一对象数965,929倒排文件大小5.77GB数据集基本统计统计信息第72页,共89页，2024年2月25日，星期天倒排文件缓存机制倒排文件缓存负载特性缓存策略的选择第73页,共89页，2024年2月25日，星期天倒排文件缓存机制-负载特性I/O序列对象大小位置数据访问产生的部分是固定大小（32KB）文档数据访问产生的对象大小分布很不均匀有效的缓存替换算法需要考虑对象的大小大量的小数据对象优先缓存，可以提高缓存的命中率大对象优先缓存可以提高缓存的字节命中率第74页,共89页，2024年2月25日，星期天倒排文件缓存机制-负载特性文档数据访问对象大小分布第75页,共89页，2024年2月25日，星期天倒排文件缓存机制-负载特性序列中对象的频度分布如果序列中对象访问频率分布不均匀缓存少数高频对象可以提高性能不区分出大量低频对象将降低性能对象访问频率和访问的时间局部性是相关的频率是倒排文件缓存替换算法应该考虑的一个因素I/O序列的频率特性比PAGE序列更有利于缓存第76页,共89页，2024年2月25日，星期天倒排文件缓存机制-负载特性I/O与PAGE序列序号--频度分布第77页,共89页，2024年2月25日，星期天倒排文件缓存机制-负载特性序列中对象的时间间隔分布序列的时间局部性可以从序列中对同一个对象的两次连续访问的时间间隔分布来考察I/O序列可以预期得到比PAGE序列更高的缓存命中率较强的时间局部性有利于缓存的设计第78页,共