网页搜索引擎

UCI CS 121(信息检索)· 2025 春季学期 · 四人团队

在课程提供的约 5 万个 UCI ICS 网页上建倒排索引,用 TF-IDF、PageRank、HITS 与标题匹配综合排序

技术栈

Python, NLTK (stemming), BeautifulSoup, NetworkX (PageRank), Requests, Streamlit

项目目标与最终效果

课程提供一份 UCI ICS 网页语料:每个页面一个 JSON 文件,包含 URL 和 HTML。作业是在它上面做一个完整的搜索引擎,从建索引、检索、排序一直到搜索界面。

最终系统:页面经解析、分词与词干化后写入倒排表,每条记录包含文档 ID、词频、词位置和所在 HTML 标签;索引按首字母分成 A–I、J–R、S–Z 和其他四个部分文件写入磁盘,再按词合并,并用一个 bookkeeping 文件记录每个词在文件中的字节偏移,查询时直接定位读取。查询对词干化后的词做布尔 AND;某个词没有倒排表时,退回 N-gram 模糊匹配(最多 200 毫秒)。排序分数是经 min-max 归一化的 TF-IDF、PageRank 与 HITS 权威度的加权和,再加上标题匹配项。建索引时去掉完全重复的页面(MD5)。Streamlit 界面高亮匹配词、分页,并保留浏览记录。

我们提交了两个版本:在完整语料上建索引的版本,以及先用我的过滤脚本剔除打不开、没有标题的页面,再建索引的「干净语料」版本。

我的职责与个人贡献

团队成员:Claire Li、Emily Sun、Richard Youn 和我。报告和 README 没有写个人分工,下面「我的部分」依据团队仓库的提交记录整理;其余部分由团队共同完成。

我的部分

  • 索引与查询:为每条倒排记录加入词位置(为后续的邻近度分析做准备),并对查询词做词干化,使之与词干化后的索引一致。
  • TF-IDF:把文档频率和 TF-IDF 的计算从分块写盘之前,移到所有分块按词合并之后(问题 1)。
  • 干净语料:编写 filter_dev_fast.py,在建索引前剔除打不开或没有标题的页面(问题 2);并加大标题匹配在最终分数中的权重。
  • 代码与提交:把代码整理为 app / core / data / utils 几个包,并完成最终提交。

团队共同完成

  • PageRank(NetworkX)与 HITS 链接分析;min-max 归一化的分数融合;完全重复页面检测;N-gram 模糊匹配;无标题页面过滤;Streamlit 搜索界面。

技术问题与解决办法

问题 1:分块计算的 TF-IDF 用错了文档频率

问题
建索引时,程序每处理一批文档就把内存里的索引写到磁盘,然后清空索引和文档频率(df)计数。TF-IDF 是在每次清空之前算的,所以一个词的 df 只统计了当前这一批文档,idf 用的也是「目前处理到第几篇」而不是语料总数;同一个词的倒排表还会分散在部分文件的多行里。
做法
  • 建索引时不再计算 TF-IDF。在合并步骤中,先把一个词在各部分文件里的倒排表全部拼接起来。
  • 再以合并后倒排表的长度作为 df,用语料总文档数 N 计算 idf = log(N / df),每条记录的权重为 (1 + log tf) × idf。
为什么这样做
df 是整个语料的统计量,而合并步骤是一个词的完整倒排表第一次出现的地方。在这里计算不需要额外多读一遍数据——合并本来就要逐行读完所有文件。
df = len(postings)
idf = math.log(total_docs / df) if df > 0 else 0.0

for posting in postings:
    tf = posting.get("tf", 1)
    tf_norm = 1 + math.log(tf) if tf > 0 else 0.0
    posting["tfidf"] = tf_norm * idf
摘自 utils/merge_jsonl.py:一个词的倒排表合并之后才计算 df 与 TF-IDF(已删去注释)。

问题 2:索引里混进了打不开的页面

问题
第一轮测试中,“machine learning” 和 “Software Engineering Course” 的第一条结果都是一个没有标题的文件目录列表(maven-contents.txt),其他结果里也有 404 页面和下载链接。语料里的每个文件都被建了索引,不管它是不是一个真实、可访问的网页。
做法
  • 编写在建索引之前运行的 filter_dev_fast.py:先跳过 JSON 无效、URL 为空、内容为空的文件,以及没有 <html>/<body> 结构或没有非空 <title> 的页面。
  • 对通过检查的页面向真实 URL 发一个 HTTP HEAD 请求(跟随重定向,超时 10 秒),只有状态码为 200 才保留;每个请求之间随机停顿 50–150 毫秒。
  • 保留下来的页面复制到 DEV_filtered,「干净语料」版本改为对这个目录建索引。同时加大标题匹配在最终分数中的权重。
为什么这样做
在建索引之前过滤一次,TF-IDF、PageRank 与 HITS 用的链接图以及索引大小就都不再受打不开的页面影响,而不必在查询时逐条修补结果。请求逐个发送、中间随机停顿,是为了不集中轰击学校的服务器。

结果与验证方法

完整语料版本的索引页面数
50,281
干净语料版本的索引页面数
8,694
四个标准测试查询的耗时
2.6–146 ms
  • 最终版本(完整语料)的标准查询:“cristina lopes” 58 条结果 2.6 毫秒,“machine learning” 2,622 条 37.0 毫秒,“ACM” 2,480 条 16.3 毫秒,“master of software engineering” 993 条 146.4 毫秒。
  • 评估方法:团队准备了 20 个测试查询(10 个应该表现好的,10 个困难的:过宽、拼写错误、只有停用词、不存在的词),分三轮运行,记录结果数、耗时和前几条结果。
  • 第一轮暴露了无标题的文件列表、重复页面和失效链接排在前面的问题;第三轮在我的过滤脚本生成的干净语料上,并加大标题权重后,重新跑了全部 20 个查询。
  • 两个索引的页面数来自提交目录里各自的 url_to_docid.json(都已去掉完全重复的页面)。

局限

  • HEAD 检查只反映过滤当时(2025 年 6 月)链接是否可用;任何非 200 状态都会剔除页面,包括拒绝 HEAD 请求的服务器。干净语料索引只有 8,694 个页面,完整索引是 50,281 个。
  • 过滤请求逐个发送、中间还有停顿,处理整份语料需要较长时间。
  • 排序权重(α、β、γ 与标题权重)是在测试查询上手动调整的,没有带标注的相关性数据来衡量准确率。
  • 过宽或只有停用词的查询仍然最慢(第二轮完整语料上 “the and or but” 287 毫秒)。
  • 尝试过但不在最终版本中:邻近度评分和 SimHash 近似重复检测都已实现,但在测试中被注释掉。

证据与资料

代码在团队的私有仓库里;这是计分的课程作业,所以不公开。