北京大学信息学院2007年秋季学期《数据结构与算法实习)》综合作业

P3. 文本文件的倒排索引（2-3人一个小组）___ 对文档建立倒排索引，首先把文档解析为<词，文档，词频>的三元组，这些三元组通过排序生成倒排文件。如果索引太大，需要存储在外存；首先在内存创建临时索引，当临时索引足够大时就写入硬盘；类似外排序里的一个run，最后merge所有的run为最终索引。这种方式比较灵活，一些全文检索系统，比如开源搜索引擎Lucene就是采用了这种方式。  _ 实现一个简单的倒排索引器，词典组织可以使用简单的结构，如二级索引，要求是能提供简单的单词查询，也就是给定一个词，返回包含该词的所有文档，以及该词在每篇文档里出现的频率。要求和提示：根据小组的能力，可以支持不同的功能和规模。(1) 如果做外存索引有困难，可以假设内存可以装下整个索引，通过两遍扫描文档集生成倒排索引。能完成这项功能，本题可以及格。(2) 支持多种查询方式，例如“与”、“或”等，甚至更复杂的查询表达式，请参考Google和Lucene。(3) 记录词在文档中的位置信息，查询该词时，能返回该词在文档中出现的摘要并用不同颜色显示查询词，请参考Google摘要。___ ……

张铭编写并发布_________________ mzhang@db.pku.edu.cn