Project 3说明及评判标准

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Project 3 说明及评判标准,1,提纲,建索引,查询,文档,2,建索引：过程(1/3),预处理,分词,抽取posting,排序,输出,3,建索引：过程(2/3),1) 预处理,全文检索处理的对象是文字。因此，对于非纯文本格式的文件，如HTML，PDF等，需要去掉其中的格式信息，转换为纯文本。,假设文档都是纯文本的，不需要考虑非纯文本格式的预处理过程,2) 分词/词形变换,相对于英文全文检索，分词是中文独有的困难。由于词与词之间没有明显的边界，需要使用分词算法把句子分割成单词的序列。在目前的技术条件下，分词不能达到100%准确，而分词错误会直接影响查询效果。,词形变换：英文单词的单复数、时态等,分词可以使用ICTCLAS的分词工具（最后补充里介绍），我们也会提供已经分词处理过的测试文档集。,4,建索引：过程 (3/3),3) 抽取posting,文档-词,自然关系的倒置过程，生成,词-文档,把单词和对应的文档编号，出现位置相结合，生成三元组（posting）。,4) 排序,先按单词（字典顺序），其次文档id，最后出现位置pos，对所有posting排序，产生倒排表。,5) 输出,按顺序将倒排表写到磁盘上。,5,建索引：基本要求,设计一个方便的方式让用户对指定文件或指定目录下的文件建立索引,你可以,提供一个函数接口，让用户在程序中使用你的函数建立索引，比如：,int Indexer:index(const char* srcDir， const char* destDir),提供一个命令行界面,提供一个图形界面,C: index.exe D:/data D:/index,6,建索引：FAQ,索引是动态的还是静态的？,大家可以自由选择。,索引是否需要持久化，即写入硬盘？,一个完整的检索系统肯定需要索引的持久化，但是不作硬性要求，留作加分点。,其他,源数据是纯文本格式，不需要考虑HTML、WORD等文件格式。,不需要考虑英文的词形转换。,7,建索引：示例lucene索引结构,apple foo bar, apple applet aqua foo ,.tii(in memory),.tis, docIds for apple docIds for applet , proxs for apple proxs for applet ,.frq,.prx,顺序查找=,8,建索引：如何建立倒排文件,对于较小的文档集，可在完全在内存中对其建立倒排索引，再写到文件中。,当文档集很大时，问题就出现了：不可能在内存中对所有的文档建立倒排索引。,于是，必须把文档集分成若干块，分块建立索引。生成多个倒排文件后，再把它们归并成一个大文件。,如下图所示：,9,建索引：归并,I-1,I-2,I-3,I-6,I-4,I-5,I-8,I-7,4,1,5,2,I-1.2,I-3.4,I-5.6,I-7.8,3,6,I-1.4,I-5.8,7,I-1.8,10,提纲,建索引,查询,文档,11,查询：过程,从倒排文件中查找分三个基本步骤：,词典的查找。注意每个查询可能包含若干个词。,获得各个词的posting列表,对posting列表的处理。如处理词的相邻位置关系，布尔查询等。,12,查询：基本要求,必须,设计并提供一个查询接口，比如：,Hits* Searcher:search(const string,or,int Searcher:search(const string,查询结果,必须,起码给出查询到的文档们的路径。,13,查询：支持的基本查询,词查询,只有一个词，比如，你在google里输入 “中国”,返回包含“中国”的文档。,最基础的查询方式。,如何表示结果？,简单布尔查询,AND操作：即词查询的结果做集合与运算,“中国 AND 人民”,返回既包含“中国” 又包含“人民”的文档。,短语查询,“中国人民”,即中国 AND 人民，,并且“中国”和“人民”这两个词的位置在文档中是相邻的。,需要用到posting里的位置信息。,14,查询：可以考虑支持但不作要求的,Ranked查询,对返回的结果排个序，把认为重要的结果放在前面。,如何排序？,最简单原始的想法就是使用某个词在文档中出现的频率？,比如，对于词查询：“中国”， “中国”在文档1中出现了10次，在文档2中出现了20次，在文档3中出现了11次， 那么最后返回的结果应该是：,1. 文档2,2. 文档3,3. 文档1,TopK查询,返回前k条排序值最高的结果。,可以利用堆吗？,15,提纲,建索引,查询,文档,16,文档,对基本功能的实现情况,自己的特色,系统实现,接口描述,程序界面,建索引,查询：比如查询的函数，简单的查询语法,用户界面（如果有，大体描述下如何使用）,索引结构,逻辑结构,物理结构,其他优化,重要算法过程的描述,建索引算法,查询算法,小组成员之间的详细分工情况,其他想法和心得,17,其他注意事项,附加说明：,程序有诚实代码，最好每个文件都有，文档有签名（写明姓名，学号），每项占0.5分,如果没有则扣分。,文档部分写明自己的设计思路，如果是有特色的设计，一定要说明，因为助教看程序可能没有看出来。（比如：为了提高查询速度，我采用了什么样的独特设计）,再次提醒，提交正确的文档（正确作业（不要提交别的作业），编译通过，结果正确）,18,Thank You！,19,分词补充：ICTCLAS,中国科学院计算技术研究所在多年研究基础上，耗时一年研制出了汉语词法分析系统ICTCLAS(Institute of Computing Technology, Chinese Lexical Analysis System),功能有：中文分词；词性标注；未登录词识别。,分词正确率高达97%以上，未登录词识别召回率均高于90%，其中中国人名的识别召回率接近98%处理速度为31.5Kbytes/s。,可以根据需要输出多个高概率结果，有多种输出格式，支持北大词性标注集，973专家组给出的词性标注集合。,20,21,22,CResult类,输出,输入,23,New Folder-Add Files to Folder,24,