该程序是基于 linux 和 c 语言运用倒排索引原理实现的一个本地搜索程序。分为两个部分:统计部分,搜索部分。
统计部分:
1 首先由用户提供的要统计路径开始向下遍历,根据后缀名筛选出要统计的文件,由零开始依此往后编号并写入名为“textfile.t”的文件。
2 从 textfile.t 中读入需要统计的文件,抽取出其中的字符串,对应上文档号,在内存中用快速排序对其排序写入后缀名为“i"的文件中,每个这样的文件最多能写入 150000 个单元。至此将得到诸多后缀名为”i”的文件,这些文件是在单个文件内部是呈字典序的,整体上是无序的。
3 用多路归并树归并这些文件,一定数量后将存储到硬盘,最终生成系列后缀名为”inv”文件。
4 再处理 inv 文件,将关键字(字符串)后的文档号排序,并记录每个词在该文档中的次数。生成后缀名为“ind"的文件。
5 在生成 inv 文件的过程中,记录每个文件第一个字符串,并和起所在文档对应,生成“Bfile.t“文件(B 树),为建立二次索引做准备。搜索部分:
首先将 textfile.t 文件、Bfile.t 文件读入内存,然后根据用户要提供的字符串先二分搜索 Bfile.t文件在内存中的映射表,得到关键字所在的 ind 文件名,将该文件读入内存,再二分搜索该文件得到所在文档的文档号,然后在 textfile.t 文件在内存中的映射表中找到路径名,打印出来。打印次序未经处理。如果是多个搜索字符串,则对搜索结果进行布尔计算,求交集,最终将包含所有这些字符串的文件路径打印出来。