用户参与的语意搜索final.ppt

用户参与的语意搜索,Networm成员:李宇10648219梁双10648220刘锋10648221(组长),主要内容,问题的提出解决思想碰到的问题实现设计学习体会存在不足试验结果,问题的提出(碰到的问题),当我们想搜索一个人的信息的时候,却往往搜索出来了他参加会议,某个活动的信息.当我们想要搜索某一个某地自助游的信息,果搜索出来的很多并不是我们想要的内容.当我们想搜索图灵机的定义的时候,结果搜到的都并非很理想的结果.,问题的提出(为什么?如何解决),为什么会出现这样的情况?其中一个很大的原因是用户不能够清楚的表达自己的语意.另外一个原因是系统并没有针对用户的语意做出优化.所以提出了用户参与的语意搜索包括两个方面,一个是给用户更大的选择权,另外一个是要根据这些选择做出优化.,问题的提出(哪写可以改进?),哪写内容适合做语意搜索?语意清晰，容易定义，但是表达多样，用户处理难度较大这种情况。还有一些情况虽然定义并不容易,但是可以采用机器学习的方法来进行精化,也是可以在某些程度上提高搜索准确率的.,解决思想,使得用户在通用搜索的基础之上可以选择明确的搜索项目.或者在用户没有明确选择的时候可以在返回结果的同时返回可能相关的模版供用户选择.在服务器端按照已经定义的类型,对每个网页进行分类.每个网页有可能同时属于多个类别.分类之后在对网页进行rank的时候需要加重此类别属性所占的比例.,碰到的问题,如何在增加新类型的时候,可以非常容易的增加进去,效率比较高,而且不影响客户对原系统的使用可扩充性虽然增加了类型匹配,但是不能够大幅降低用户搜索代价.需要能够非常快速的将类型权重加入到rank计算当中高效性还有许多实际实现时候的问题.,设计实现,为了满足可扩充性,就需要在修改文档类型的时候不影响用户的使用.这就需要独立于用户使用通用查询的数据结构文档模版数组或者模版文档数组.而且不同的进程修改的都是不同的数据.这样是对读进程没有任何影响的,可以不用封锁就可以直接修改读取.又因为是独立数据结构,所以更不会影响用户使用通用查询.,设计实现文档模版数组图示,文档模版数组bit型,文档1后面的数组表示文档1符合模版1.空间消耗M*Nbit,扩充模版时相对麻烦.,文档模版数组Value型,文档1之后的75表示文档1和模版1的符合程度值.空间消耗M*N*2Byte,假设文档数为M,模版数为N,设计实现文档模版数组分析,一种是存储是或者否的结果,这样即使模版数量很大,空间消耗也可以承受.当判断一个文档是否属于用户查询类型的时候,依据文档ID作为下标找到模版数组,再以模版ID作为下标得到是否属于.一种是存储文件和每一个模版匹配的权重,这样更加精确,但是在实际中是否一定效果就比前一种好,还很难说.而且空间消耗也比较大.找到文档与用户请求模版是否匹配的时间效率为2.常数量级.,设计实现模版文档数组图示,模版文档数组bit型,模版1后面的数组表示符合模版1的所有文档.空间消耗为M*Nbit.可扩充性较强,算法简单.,模版文档数组Value型,模版1后面的数组表示符合模版1的所有文档.空间消耗约为2*M*logMbit,假设文档数为M,模版数为N,设计实现模版文档数组分析,一种是存储是或者否的结果,这样即使模版数量很大,空间消耗也可以承受.当判断一个文档是否属于用户查询类型的时候,依据文档ID作为下标找到模版数组,再以模版ID作为下标得到是否属于.时间复杂度也为2,常数量极.一种是存储和此模板匹配的每一个文件的编号,当模版比较远远少于文档数量的时候,这种存储效率也不一定高.但是时间复杂度就约为M/N.综上所述,这种方法不是很好.但当模版数量增大的时候,空间效率要求较高的时候可以考虑.,设计实现主要部分,主要分为crawler,正文处理,切词,建立倒排表,rank,模版匹配,模版建立,用户UI.其中crawler和切词部分是使用其他产品,并非自己开发.正文处理:处理掉html中的各种标签,并且进行编码转换.模版匹配:将正文与模版进行匹配,并且得到一个匹配度,用来计算rank使用.,设计的实现索引部分,倒排表结构目的是通过关键词快速查找到出现的文档以及位置信息；采用关键词作为Key，PostingList结构作为Value的哈希表方式，以提高查询的效率；Posting的结构为文档编号位置信息；工作时倒排表结构位于内存中，实现了倒排表文件的存取，方便备份；,设计的实现索引部分,文档信息索引目的是通过文档ID快速查找到文档的信息；采用文档ID作为Key，文档信息结构作为Value的哈希表方式；文档信息主要包括网页的URL，以及模板的匹配结果；同样实现了文档信息索引的文件存取，以方便备份；,设计的实现PageRank,一个输入-“内核编程指南”怎样能让对输入词组的完全匹配在前面？”内核编程指南”作为新词？在本应用中，由于用户输入样本少，挑选新词无法实施。位置算法。算出单个关键词（“内核”，“编程”，“指南”）在公共页面中的位置，然后计算它们是否属于相连。在某页面中：如果前两个词相连一次，页面权重+2，前三个词相连一次，页面权重+4，以此类推最后对所有公共页面，对他们的权重进行排序。,设计的实现PageRank,前面已经对公共页面排序。现在再算出公共页面的匹配度。将匹配度小于阀值（70）的页面抽出，排在后面,设计的实现PageRank讨论,上面使用的rank算法可以简单的将符合查询条件结果中符合模版的结果向前移动,算法简单,效率很高,而且非常有效.当检索词较多,而同时匹配的情况又不多的时候,匹配到部分检索词的结果如果符合模版该如何排序,应该如何计算rank?这是一个值得讨论的问题.,设计的实现(整体图例),学习体会(总体体会),除了CRAWLER还有切词功能之外,所有的程序都是小组自己实现.虽然功能相对简单,但是对于搜索引擎的基本原理有了更加深刻的认识.同时在程序处理的时候都效率优先,都会考虑到时间空间的消耗,并提出多种解决方案,根据空间和时间需求选择合适的解决方案.,学习体会(空间效率和效果讨论),除了上面讨论的两种匹配方案之外,如果空间效率要求非常苛刻的话,那么文档和模版之间的匹配就可以不存储下来,而是在用户检索结果的前N条来动态匹配.这样时间效率虽然低一些,是否可以接受还需要检验,但是考虑到空间效率也是一种解决方案.而且这种解决方案最灵活.,学习体会(时间效率讨论),在模版匹配的过程中,如果关键字比较少的话,而且当关键字切词被切为多个的时候,算法就需要统计位置信息,这样算法的效率还需要衡量.现在使用的是在建立倒排表的过程中,直接匹配的算法.效率经过测试还是比较高的,但是对于关键词比较多,而且不相关关键词位置信息也占比重较大的模版,这个算法就不能够较好的完成任务.,学习体会(时间效率讨论),上面讨论的直接匹配的算法对于新增模版的时候,效率也比较低,因为需要把每个文件重新读入一遍,所以为了避免这个结果,需要直接利用内存中文档和关键字之间的信息,将模版关键字作为倒排索引的key,得到所有的docID,遍历所有的docID,并修改docID的模版匹配度.最后根据位置信息再次修改匹配度.,存在不足,因为时间的问题,并没有能够对模版进行样本分析,只是使用人工定制模版的方法,而模版的样本分析对这个系统能够投入实际应用很重要.在计算匹配度的时候,并没有考虑具体的位置信息,虽然在一些模版当中位置信息并不是非常重要的,但是对于匹配度的准确还是有帮助的.,系统优点,即使在存在上诉不足的情况下,即使在模板都是很简单定义的情况下,搜索的rank也是得到了很大的改善.在定义的简历模版当中,凡是得分超过70分的,基本上99%都可以判定为简历模版.当然也会有一些疏漏,但是这个功能只是在通用搜索引擎之上增加的一个rank计算,所以只会提高符合的,对于那些不符合模版规范的,排名也不会下降太多.,系统优点,根据”如果希望用户多用搜索引擎，就要让第一页的内容尽量有吸引力”这个习惯,模版匹配增加rank值,能够很大程度上在不太增加搜索时间,存储开销的情况下,提高第一页的准确度.即使是简单的模版定义,已经足够提供给用户足够准确的信息了.而且不太影响其他网页在其他rank算法下的排