53 | 算法实战（二）：剖析搜索引擎背后的经典数据结构和算法

倒排索引中记录了每个单词以及包含它的网页列表，想问一下“倒排索引”这个名字是怎么来的？其中的“倒排”体现在哪里呢？

搜集：将广度优先搜索的优先队列存储在磁盘文件links.bin（如何解析网页内的链接？），有布隆过滤器判重并定期写入磁盘文件bloom_filter.bin，将访问到的原始网页数据存入磁盘文件doc_raw.bin，计数分配网页编号并与其链接对应关系存入磁盘文件doc_id.bin。 分析：首先抽取网页文本信息，依据HTML语法规范，通过AC自动机多模式串匹配算法，去除网页中格式化部分，提取文本内容。然后分词并创建临时索引，分词的目的是找到能够标识网页文本“身份”的特征，可借助词库（通过Trie树实现）搜索文本中与词库匹配的最长词语，因为一般情况下越长信息越多，越剧有表征能力（为什么英文简单？）。分词完成后得到一组用于表征网页的单词列表，与其对应的网页编号存入磁盘文件tmp_index.bin作为临时索引，为节省空间单词是以单词编号的形式写入，单词文本与编号的对应关系写入磁盘文本term_id.bin。 索引：通过临时索引构建倒排索引文件index.bin。倒排索引其实是以单词为主键，将临时索引中的多个相同单词行合并为一行。通过以单词为主键的排序算法，可以将相同单词的行连续排列在一起，之后只要将单词相同的连续行合并为一行即可。由于数据量大，应采用分治策略。最后建立所有单词在倒排索引文件中位置的索引文件term_offset.bin，以方便快速查找。 查询：先对搜索条件文本做分词处理，然后去term_id.bin查单词们的编号，再查term_offset.bin找到单词们在倒排索引中的位置，到index.bin找到每个单词对应的网页编号，通过网页出现次数、预评权重和统计算法（如pagerank、tf-idf）计算网页的优先次序并输出。最后在doc_in.bin中找到网页链接按序输出显示给用户。 这样理解对不？

老师好 看了这篇之后我也想实现一个搜索引擎 现在很多公司里应该都用的cpp吧 我也想用cpp实现一个 请问下有没有可参考的代码 怕写到一半写不下去😂

有没有代码实现的例子？

可以讲讲到排序索引和普通索引区别？

爬虫按照广度优先的策略，不停地从队列中取出链接，然后“取“ -> “去“ 爬取对应的网页，解析出网页里包含的其他网页链接，再将解析出来的链接添加到队列中。 上面这段话里面有个词不是很通， 不知道后面还能修正么。

请问倒排索引这种结构比b树快是不是依赖于它的数据结构优势？

王老师，字典使用最长匹配？那例子中的”中国“”中国人“不就无法匹配到了吗

老师好，本文中好像没有看到ac自动机的应用

原理是看懂了，实现起来肯定会遇到各种各样的问题，手动实现一遍是有必要的，如果老师能提供一个参考代码就更好了。