47 | 搜索引擎（上）：如何通过倒排索引和向量空间模型，打造一个简单的搜索引擎？
黄申
该思维导图由 AI 生成，仅供参考
你好，我是黄申。
上一节，我们充分利用了哈希表时间复杂度低的特点，设计了一个简单的缓存系统。在实际项目中，哈希表或者类似的哈希数据结构，有着更为广泛的运用。比如，搜索引擎中的倒排索引，也是基于哈希表结构来设计的。这种倒排索引可以大大提升数据对象的检索效率。
除了搜索的效率，搜索引擎另一个需要考虑的问题是相关性，也就是说，我们需要保证检索出来的信息是满足用户需求的。最简单的基于倒排索引的实现，属于一种布尔排序模型，它只考虑了单词是不是出现在文档之中，如果出现了就返回相应的文档，否则就不返回，对应于布尔模型中的真假值。在这种实现中，只要出现了相关搜索词的文档都会被检索出来，因此相关性比较差。对于这点，我们可以利用向量空间模型，来衡量文档和用户查询之间的相似程度，确保两者是相关的。不过，向量空间模型需要涉及两两之间的比较，时间复杂度比较高。
考虑到上述两点，今天，我们就以文档检索为例，参照倒排索引加向量空间模型的设计思路，设计一个简单的搜索引擎。
搜索引擎的设计框架
之前在讲解向量空间模型的时候，我们介绍了信息检索的基础知识，而我们平时经常使用的搜索引擎，就是一种典型的信息检索系统。在讲解如何结合倒排索引和向量空间模型之前，我们先来看，常见的文本搜索引擎都由哪些模块组成。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了如何利用倒排索引和向量空间模型设计文本搜索引擎。首先，文章讲解了搜索引擎的设计框架，包括离线的预处理和在线的查询两个重要模块。离线预处理包括数据获取、文本预处理、词典和倒排索引的构建，而在线查询则是根据用户输入的查询条件，在倒排索引中快速检出文档，并进行相关性的计算。倒排索引的设计需要考虑存储词频、词频-逆文档频率、词条出现的条件概率等信息，并通过两两比较的方式来确定出现所有多个关键词的文档。此外，文章还介绍了向量空间模型在文本搜索中的应用，通过向量表示文档和查询，并利用夹角余弦来计算它们之间的相似度。借助倒排索引，可以过滤掉绝大部分不包含查询关键词的文档，从而提高搜索效率。总的来说，本文通过简洁清晰的语言，深入浅出地介绍了搜索引擎的设计原理和关键技术，对于想要了解搜索引擎工作原理的读者具有很高的参考价值。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《程序员的数学基础课》，新⼈⾸单¥68
《程序员的数学基础课》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(6)
- 最新
- 精选
建强思考题： 想用Python语言来实现一个简单的搜索引擎，现在暂时还没时间和精力去做，不过有了老师给出的框架和算法，实现起来应该不难 另外有两个细节问题再请教一下： (1)计算文档向量和查询向量的夹角余弦时，由于查询向量的关键词较少，对于出现在文档中的关键词，查询向量元素值取1，否则就取0，这样是否可行。 (2)分母部分，是把文档向量的L2范数在离线处理时先计算好，作为一个常量，然后在计算和查询向量的夹角时，只需要计算查询向量的L2范数然后再乘上事先计算好的文档向量的L2范数，是这样处理吗作者回复: （1）是可行的，不过在处理稀疏向量时，可以用哈希表提高效率 （2）这也是很好的优化，可以提高效率
2020-12-202
qinggeouye23节中基于自然语言预处理方法(分词/取词干和归一化/停用词/同义词和扩展词等)、35节把文档和查询转换为向量形式，为了减小计算查询向量和所有文档向量间的夹角余弦的时间复杂度，利用17节的倒排索引可先过滤掉与查询关键词无关的文档。作者回复: 是的，结合这多个技术来实现
2019-04-152
拉欧“如果文档中词条的平均数量是 n，查询中词条的平均数量是 m，那么计算某个查询和某个文档之间的夹角余弦，时间复杂度是 O(n×m)。” 这里两个向量的维度不同，怎么计算余弦夹角?作者回复: 其实是相同的，假设K是字典里所有词条的总数，那么两个向量的维度都是K，对于没有出现的词条，分量的值都是0，所以通常文档和查询向量都是稀疏向量，很多0分量。在计算夹角余弦的时候，0的分量都忽略不算了，所以时间复杂度会降低。这里再补充说明一下，如果向量存储使用哈希表，时间复杂度也可以降低到O(m)，假设m<<n
2019-04-042- 013923学习了搜索引擎上
作者回复: 很高兴这些课程对你都有价值
2022-09-15归属地：美国1 - Paul Shan倒排索引是通过词找出现这个词的文档集合。有了倒排索引，我们就可以快速找出包含用户输入的关键词序列的所有文档，这里用到了归并排序的思想加速求出包含所有关键字的文档集合。有了结果集合，下面找到结果集合的内部顺序，用的是向量夹角余弦从大到小排序。这里的两个向量分别是输入关键词序列对应的向量和文档对应的向量，每个分量是每个词的tf-idf值。向量夹角余弦可以看作两个单位向量的乘积，文档单位向量可以离线计算好，查询关键词向量维度少，容易计算。这样就能通过倒排索引快速找出相关程度从大到小的文档集合。2019-10-153
leslie其实觉得搜索这块真的没有答案：自己把数据库索引的性能几乎用到了极限。 搜索引擎觉得也如此：追求的是有效率，然后调整排序，适当调整各种顺序。。。 觉得这是一条没有终点的路：老师的课程中推荐的计算机的原理的书大多买了，看了多遍还是。。。2019-07-163
收起评论
