搜索引擎的组件

HTML 解析器 (HTML Parser)

  • 功能: 从 HTML 文件中提取内容, 将其转化为一系列标记(Tokens), 并区分这些词是出现在标题(Title)还是正文(Body)中;
  • 提取链接: 它还负责提取指向其他文档的链接以及对应的锚文本(Anchor text);
  • 挑战: 来源指出, 由于互联网上存在大量格式错误, 破损的 HTML 代码, 编写一个不崩溃且健壮的解析器往往是项目中最耗时且最具挑战性的部分;

爬虫 (Crawler)

  • link 管理: 管理一个待爬取的"前沿(Frontier)"链接池, 决定爬取的先后顺序, 并记录已爬取的页面以防重复;
  • 多线程协作: 为了不被慢速网站拖累, 爬虫必须是高度多线程的;
  • 合规性: 爬虫必须遵守 robots.txt 协议, 并应在 User-Agent 字段中留下联系方式, 以示"礼貌"并防止被视为拒绝服务(DOS)攻击;

索引 (Index)

  • 核心产物: 这是一个合并的倒排词索引(Inverted word index), 记录了每个单词出现的所有文档及其具体位置(Postings);
  • 工作原理: 它类似于书后的索引或古代的索引汇编(Concordance), 通过查找单词列表的交集, 可以快速找到包含特定组合词的页面;
  • 存储: 由于数据量巨大, 索引通常存储在磁盘上, 但会通过虚拟内存映射(Memory mapping)到进程空间中以提高访问速度;

约束求解器 (Constraint Solver)

  • 匹配文档: 根据用户提供的约束条件(如: 必须包含某些词或特定短语), 在索引中查找匹配的文档列表;
  • 技术实现: 它利用 索引流读取器(ISRs) 来扫描索引, 执行诸如 “与(AND)”, “或(OR)”, “非(NOT)” 以及短语匹配等逻辑运算;

查询语言/编译器 (Query Language / Compiler)

  • 指令转化: 将用户输入的原始查询文本(例如带引号的短语 “apollo moon landing”)编译成约束求解器能够理解的逻辑结构(如解析树);
  • 递归性: 查询语言和 ISR 通常是递归设计的, 以支持复杂的嵌套查询;

排名器 (Ranker)

  • 打分与挑选: 利用编译后的查询从索引中检索匹配页面, 然后通过统计, 启发式(Heuristic)前 10 个最佳结果;
  • 质量控制: 它综合考虑动态排名(页面与查询的匹配度)和静态排名(页面本身的质量, 如 PageRank 或域名权重);

前端 (Front End)

  • 结果呈现: 通常是一个简单的 HTTP 服务器, 负责将搜索结果反馈给用户, 通常还会包含页面摘要(Snippets);
    在实际运行中, 前三个组件(解析器, 爬虫, 索引)构成了索引构建端(Build side), 而剩余四个组件(求解器, 编译器, 排名器, 前端)构成了查询服务端(Serve side);

评估质量

搜索引擎最核心的评估目标是快速提供优质结果; 为此, 课件引入了两个经典的评估维度:

  • 准确率 (Precision): 指返回的结果中, 相关结果所占的比例;它衡量的是搜索结果的"精确度";
  • 召回率 (Recall): 指所有相关的结果中, 被成功返回的比例;它衡量的是搜索结果的"查全率";

动态排名有效性评估

为了让最好的结果排在最前面, 系统需要通过相关性 (Relevance) 评估来对结果进行排序;

  • 词袋模型 (Bag of Words): 一种传统方法, 仅考虑单词是否出现, 而不考虑它们的位置或相互关系; 其中最著名的是 tf-idf, 它认为 稀有单词 出现的频率越高, 相关性得分越高;
  • 启发式算法 (Heuristics): 现代搜索引擎(如微软)更倾向于使用启发式方法;
    • 评估标准包括: 单词顺序 是否正确, 单词是否 彼此靠近(紧凑程度/Spans) 以及匹配发生的位置(元流 Metastreams, 比如标题, 正文);
  • 权重评估: 微软的经验表明, 匹配位置的重要性排序为:
    • 锚文本 (Anchor text) > URL > 标题 (Title) > 正文 (Body text);

静态排名评估 (Static Rank)

这是在 不考虑查询词 的情况下, 对 页面本身质量 的评估:

  • 域名与URL: 例如 .gov 或 .edu 域名的页面通常优于 .biz;
  • 较短的 URL 和标题通常也被认为质量更高;
  • PageRank: 通过计算 链接到该页面的数量和质量 来评估其重要性, 这种方法被认为具有 “科学且公正” 的合法性;