• 手动写一个搜索引擎（超详细）

    一、项目背景

            搜索引擎是现代设备中被广泛利用的一种系统软件，诸如百度、谷歌、搜索、bing等，或者抖音、快手、b站、小红书，甚至软件应用市场，Windows（操作系统）中的各类提供搜索功能的背后都有搜索引擎的影子。

    二、使用技术

    Spring + SpringMVC + Mybatis

    Spring 负责提供：IoC、AOP

    SpringMVC 负责提供：Web 业务处理

    Mybatis 负责提供：方便 SQL 处理

    三、项目功能

    根据用户检索的内容，把检索到的相关信息展现给用户。

    四、整体逻辑图

    五、具体实现

    1.基本流程（用户角度）：

    用户输入搜索词（一个词或者多个词），在已有文档中，找到文档包含这些词的所有文档信息，再给出搜索后的列表。

    2.设计

    （1）初步想法（不可行）

    首先，我们可以分析到，这实际上就是需要一个文档表，里面记录他的 id、标题、内容。然后在数据库中查找：select * from 文档表 where 标题 like '%搜索词%' or 内容 like '%搜索词%'

    但我们不使用这种方式（SQL），因为上述 SQL 的查找性能非常差。

    文档个数记为 m，文档的平均长度（标题 + 内容）记为 n。O(m*n)。

    现实中，m 非常大（几百亿篇文档），所以从性能上这个方案不可行。

    （2）可实行的方法

    使用倒排索引（inverted index）

    倒排索引的大概结构：key-value 形式。key：词，value：词出现在哪些文档中。 

    ①提前构造好倒排索引，倒排索引中有 id、单词、这个单词对应的文章编号、这个单词的权重。

    ②当我们比如说去搜索 “list” 这个单词的时候，根据倒排索引，我们可以找到这个单词出现在哪些文档中，根据文档的编号，取出对应的文档内容。

    ③我们再维护一个正排索引，这里面有 docid（文章的编号）、文章标题、文章的 URL、文章的内容

    ④当我们根据倒排索引搜索到单词对应的文章id时，比如只取前 20 篇文章，那我们就只需要进行 20 次正排索引查找即可。

    补充：文档是什么文档不重要，可以是 html、pdf、图片、视频等等。

    我们经常用到的搜索引擎（百度、搜狗），他背后的数据获取一般使用爬虫自动在互联网上搜集信息，将所有内容爬成文档下来，然后进行检索和排序等操作。

    我们这个项目只针对 JDK API 文档库中的 html 做搜索

    （3）构建两大模块

     3.构建索引模块

    不需要使用 web 功能，只需要执行一次

    我们写一个 Indexer 类（indexer/command/Indexer），这是：构建索引的模块，是整个程序的逻辑入口。@Slf4j ——添加 Spring 日志的使用           @Component —— 注册成 Spring 的 bean

    我们让这个类实现 CommandLineRunner 接口。

    1. @Component 
    2. public class Indexer implements CommandLineRunner {
    3.     @Override
    4.     public void run(String... args) throws Exception {
    5.         log.info("这里的整个程序的逻辑入口");
    6.     }
    7. }

    知识补充：

    CommandLineRunner 接口：

    Spring boot的CommandLineRunner接口主要用于实现在应用初始化后，去执行一段代码块逻辑，这段初始化代码在整个应用生命周期内只会执行一次。

    使用CommandLineRunner接口和@Component注解一起使用

    为什么要使用CommandLineRunner接口

    • 实现在应用启动后，去执行相关代码逻辑，且只会执行一次；
    • spring batch批量处理框架依赖这些执行器去触发执行任务；
    • 我们可以在run()方法里使用任何依赖，因为它们已经初始化好了；

    构造索引的大概步骤：

    1.扫描文档目录下的所有文档：目录遍历的过程 FileScanner

    1. // 1. 扫描出来所有的 html 文件
    2.         log.debug("开始扫描目录，找出所有的 html 文件。{}", properties.getDocRootPath());
    3.         List htmlFileList = fileScanner.scanFile(properties.getDocRootPath(), file -> {
    4.             return file.isFile() && file.getName().endsWith(".html");
    5.         });
    6.         log.debug("扫描目录结束，一共得到 {} 个文件。", htmlFileList.size());

    我们把这个类注册成 Spring bean —— @Service

    知识补充：

    1、@Service注解 是标注在实现类上的，因为 @Service 是把 spring 容器中的 bean 进行实例化，也就是等同于 new操作，只有实现类是可以进行 new 实例化的，而接口则不能，所以是加在实现类上的。

    2、要说明@Service注解 的使用，就得说一下我们经常在 spring 配置文件applicationContext.xml中看到如下图中的配置：

    2. <context:component-scan base-package="com.study.persistent" />

    在applicationContext.xml配置文件中加上这一行以后，将自动扫描指定路径下的包，如果一个类带了 @Service注解，将自动注册到 Spring容器，不需要再在applicationContext.xml配置文件中定义 bean 了，类似的还包括 @Component、@Repository、@Controller。

    具体在 indexer.util.FileScanner 中完成。

    • 以 rootPath 作为根目录，开始进行文件的扫描，把所有符合条件的 File 对象，作为结果，以 List 形式返回（把这个过程想象成一棵树）
    • 针对目录树进行遍历，深度优先 or 广度优先即可，确保每个文件都没遍历到即可，我们这里采用深度优先遍历，使用递归完成

                    1. 先通过目录，得到该目录下的孩子文件有哪些

    File[] files = directoryFile.listFiles();

                    2. 遍历每个文件，检查是否符合条件

    1. for (File file : files) {
    2.             // 通过 filter.accept(file) 的返回值，判断是否符合条件
    3.             if (filter.accept(file)) {
    4.                 // 说明符合条件，需要把该文件加入到结果 List 中
    5.                 resultList.add(file);
    6.             }
    7.         }

                    3. 遍历每个文件，针对是目录的情况，继续深度优先遍历（递归）

    1. for (File file : files) {
    2.             if (file.isDirectory()) {
    3.                 traversal(file, filter, resultList);
    4.             }
    5.         }

    2.针对每一篇文档进行分析、处理

    得到文档的 标题（这里就把他的文件名作为标题）、最终访问的 URL（实际上是一个相对路径）、文档下的内容（IO 读操作）

    标题：

     URL：

     

    进行分词后才能得到倒排索引中保存的key，也就是你想要搜索的词。

    这个分词引入第三方库来做NLP

    1. // 2. 针对每个 html 文件，得到其 标题、URL、正文信息，把这些信息封装成一个对象（文档 Document）
    2.         File rootFile = new File(properties.getDocRootPath());
    3.         List documentList = htmlFileList.stream()
    4.                 .parallel()         // 【注意】由于我们使用了 Stream 用法，所以，可以通过添加 .parallel()，使得整个操作变成并行，利用多核增加运行速度
    5.                 .map(file -> new Document(file, properties.getUrlPrefix(), rootFile))
    6.                 .collect(Collectors.toList());
    7.         log.debug("构建文档完毕，一共 {} 篇文档", documentList.size());

    具体在 indexer.model.Document 中完成

    • 扫描出来所有的 html 文件（需要依赖FileScanner 对象，构造方法注入的方式，让 Spring 容器，注入 FileScanner 对象进来）

    这里最好，把要扫描的文件路径放在配置文件（src/main/resources/application.yml）中，这样有利于以后修改会更方便

    1. List htmlFileList = fileScanner.scanFile(properties.getDocRootPath(), file -> {
    2.             return file.isFile() && file.getName().endsWith(".html");
    3.         });
    1. searcher:
    2.   indexer:
    3.     doc-root-path: E:\java程序\docs\api
    4.     url-prefix: https://docs.oracle.com/javase/8/docs/api/

    之后用 properties 的方式来读取

    1. package com.lingqi.searcher.indexer.properties;
    2.  
    3. import lombok.*;
    4. import org.springframework.boot.context.properties.ConfigurationProperties;
    5. import org.springframework.stereotype.Component;
    6.  
    7. @Component  // 是注册到 Spring 的一个 bean
    8. @ConfigurationProperties("searcher.indexer")
    9. @Data // = @Getter + @Setter + @ToString + @EqualsAndHashCode
    10. public class IndexerProperties {
    11.     // 对应 application.yml 配置下的 searcher.indexer.doc-root-path
    12.     private String docRootPath;
    13. }
    • 针对每个 html 文件，得到其 标题、URL、正文信息，把这些信息封装成一个对象（文档 Document——model/Document)

    标题：从文件名中，将 .html 后缀去掉，剩余的看作标题

    1.     private String parseTitle(File file) {
    2.         // 从文件名中，将 .html 后缀去掉，剩余的看作标题
    3.         String name = file.getName();
    4.         String suffix = ".html";
    5.         return name.substring(0, name.length() - suffix.length());
    6.     }

    URL：需要得到一个相对路径，file 相对于 rootFile 的相对路径 。

    比如：rootFile 是 E:\java程序\docs\api 。

               file 是 E:\java程序\docs\api\javax\sql\DataSource.html

    则相对路径就是：javax\sql\DataSource.html 

    把所有反斜杠(\) 变成正斜杠(/)

    最终得到 java/sql/DataSource.html

    正文信息：

    随便打开一篇文档：

     我们需要做的是：

    1. ...   这是我们不要的

    2.所有标签都不要：

    Hello

    World

    我们要的只是 Hello World

    3.所有的换行符替换成' '（空格）

    我们只保留纯文本内容，用来做分词

    因此使用正则表达式完成上述工作

    知识补充：

    正则表达式

    " . " 匹配 任意 字符，匹配多少个需要根据后续字符来判断，默认就是一个

    " /s " 匹配任意空格，包括" "，"\t"，"\r\n"，"\r"，"\n"

    " /d " 匹配任意数字（只有一位）0-9

    " a+ " 匹配 "a"，出现的次数 >= 1次

    " a* " 匹配 "a"，出现的次数 >= 0次

     " .+ " 匹配任意字符，出现次数 >= 1 次

     " .* " 匹配任意字符，出现次数 >= 0 次

    " ? " 可选的

    先把文章一行一行全部读取到 StringBuilder 中，再把 StringBuilder 中不需要的那些内容进行删除或者替换

    1. return contentBuilder.toString()
    2.          // 首先去掉 
    3.          .replaceAll(".*?", " ")
    4.          // 去掉标签
    5.          .replaceAll("<.*?>", " ")
    6.          // 把最后多出来的空格删除掉
    7.          .replaceAll("\\s+", " ")
    8.          .trim();

    3.进行正排索引的保存

    拿到分词后，我们就知道每一篇文档的 标题、URL、内容、标题和内容的每个词

    利用上述信息就可以构建索引了。正排索引、倒排索引

    正排索引有1W条数据，倒排索引有600W条。如果一条一条插入，需要循环600W次才可以插入完成。但我们可以设置成一次插入1000条数据，这样只需要循环6000次就可以了。

    因此我们只需要两张表存在数据库中：

    正排索引表（docid-pk、title、url、content）整体数量级不大，只有1W条，但是每一条比较大（content大）——批量插入的时候，每次记录不用太多（每次插入 10 条）

    倒排索引（id-pk、word、docid、weight）整体数量级较大，有600W条，每一条的记录比较小——批量插入的时候，每次记录多插入一些（每次插入 1W条）

    我们docid的生成方式利用 MySQL 的表中的自增机制作为docid

    MySQL 批量插入语法：

    insert into forward_indexs(title,url,content) values

            ('1','2','3'),

            ('4','5','6'),

            ('7','8','9')；

    既然需要批量插入，我就要用到 mybatis 的动态SQL特性

    遍历 collection="list"，其中，下标保存在 index （index=“index”），其中遍历时的每一项保存在item（item=“item”）

     写sql的：

    1. @Repository // 注册 Spring bean
    2. @Mapper     // 是一个 Mybatis 管理的 Mapper
    3. public interface IndexDatabaseMapper {
    4.     // 正排
    5.     void batchInsertForwardIndexes(@Param("list") List documentList);
    6.  
    7.     //倒排
    8.     void batchInsertInvertedIndexes(@Param("list") List recordList);
    9. }

    准备一个xml

    1. "1.0" encoding="UTF-8" ?>
    2. mapper
    3.         PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN"
    4.         "http://mybatis.org/dtd/mybatis-3-mapper.dtd">
    5. <mapper namespace="com.lingqi.searcher.indexer.mapper.IndexDatabaseMapper">

    在配置文件中也加入。在 Spring 的配置文件中，指定 mybatis 查找 mapper xml 文件的路径

    classpath：代表从 src/main/resources 下进行查找（这实际上是错误的理解，暂且可以这么简单理解关系不大）

     index-mapper.xml文件中设置的

    实际上对应的就是 我们用于写sql 的类 IndexDatabaseMapper。

    因为我们这里实际上就是一个插入，所以是 insert 语句，因此我们在index-mapper.xml中写入insert语句

    sql语句（写在index-mapper.xml中）：

     最终的到的 sql 就是拼接好的sql。

    1. <insert id="batchInsertForwardIndexes" useGeneratedKeys="true" keyProperty="docId" keyColumn="docid">
    2.         insert into forward_indexes (title, url, content) values
    3.         
    4.         <foreach collection="list" item="doc" separator=", ">
    5.             (#{doc.title}, #{doc.url}, #{doc.content})
    6.         foreach>
    7. insert>

     我们在 indexer/core/IndexManager 中完成插入

    • 批量生成、保存正排索引
     indexManager.saveForwardIndexesConcurrent(documentList);

     单线程版本：

    1. 批量插入时，每次插入多少条记录（由于每条记录比较大，所以这里使用 10 条就够了）

    int batchSize = 10;

    2. 一共需要执行多少次 SQL？ 向上取整(documentList.size() / batchSize)

    1. int listSize = documentList.size();
    2. int times = (int) Math.ceil(1.0 * listSize / batchSize);    // ceil(天花板): 向上取整

    3. 开始分批次插入

    1. for (int i = 0; i < listSize; i += batchSize) {
    2.     // 从 documentList 中截取这批要插入的 文档列表（使用 List.subList(int from, int to)
    3.     int from = i;
    4.     int to = Integer.min(from + batchSize, listSize);
    5.  
    6.     List subList = documentList.subList(from, to);
    7.  
    8.     // 针对这个 subList 做批量插入
    9.     mapper.batchInsertForwardIndexes(subList);
    10. }

    多线程版本：

    前面两步和单线程版本相同，在第三步循环插入中，把他们放到任务中去执行

    我们需要一个线程池，定义在 indexer/config/AppConfig 中：

    1. @Configuration
    2. public class AppConfig {
    3.     @Bean
    4.     public ExecutorService executorService() {
    5.         ThreadPoolExecutor executor = new ThreadPoolExecutor(
    6.                 8, 20, 30, TimeUnit.SECONDS,
    7.                 new ArrayBlockingQueue<>(5000),
    8.                 (Runnable task) -> {
    9.                     Thread thread = new Thread(task);
    10.                     thread.setName("批量插入线程");
    11.                     return thread;
    12.                 },
    13.                 new ThreadPoolExecutor.AbortPolicy()
    14.         );
    15.  
    16.         return executor;
    17.     }
    18. }
    1. @Timing("构建 + 保存正排索引 —— 多线程版本")
    2. @SneakyThrows
    3. public void saveForwardIndexesConcurrent(List documentList) {
    4.     // 1. 批量插入时，每次插入多少条记录（由于每条记录比较大，所以这里使用 10 条就够了）
    5.     int batchSize = 10;
    6.     // 2. 一共需要执行多少次 SQL？   向上取整(documentList.size() / batchSize)
    7.     int listSize = documentList.size();
    8.     int times = (int) Math.ceil(1.0 * listSize / batchSize);    // ceil(天花板): 向上取整
    9.     log.debug("一共需要 {} 批任务。", times);
    10.  
    11.     CountDownLatch latch = new CountDownLatch(times);   // 统计每个线程的完全情况，初始值是 times(一共多少批)
    12.  
    13.     // 3. 开始分批次插入
    14.     for (int i = 0; i < listSize; i += batchSize) {
    15.         // 从 documentList 中截取这批要插入的 文档列表（使用 List.subList(int from, int to)
    16.         int from = i;
    17.         int to = Integer.min(from + batchSize, listSize);
    18.  
    19.         Runnable task = () -> { // 内部类 / lambda 表达式里如果用到了外部变量，外部变量必须的 final（或者隐式 final 的变量）
    20.             List subList = documentList.subList(from, to);
    21.  
    22.             // 针对这个 subList 做批量插入
    23.             mapper.batchInsertForwardIndexes(subList);
    24.  
    25.             latch.countDown();      //  每次任务完成之后，countDown()，让 latch 的个数减一
    26.         };
    27.  
    28.         executorService.submit(task);   // 主线程只负责把一批批的任务提交到线程池，具体的插入工作，由线程池中的线程完成
    29.     }
    30.  
    31.     // 4. 循环结束，只意味着主线程把任务提交完成了，但任务有没有做完是不知道的
    32.     // 主线程等在 latch 上，只到 latch 的个数变成 0，也就是所有任务都已经执行完了
    33.     latch.await();
    34. }

    4.倒排索引的生成和保存

    针对文档进行分词，并且分别计算每个词的权重

    在倒排索引中，我们需要进行分词、处理词的权重问题，这里我们统一放到 Document 类中处理

     对于每个 Document 进行分词处理，需要第三方库的支持

    在pom.xml 中添加依赖，它支持中文和英文分词

    1. <dependency>
    2.     <groupId>org.ansjgroupId>
    3.     <artifactId>ansj_segartifactId>
    4.     <version>5.1.6version>
    5. dependency>

    用法示例：

    1. public void Ansj() {
    2. 		Result result = ToAnalysis.parse("我爱北京天安门，天安门上太阳升。");
    3. 		List termList = result.getTerms();
    4. 		for (Term term : termList) {
    5. 			System.out.print(term.getName() + ", ");
    6. 			System.out.print(term.getNatureStr() + ", ");
    7. 			System.out.println(term.getRealName());
    8. 		}
    9. 	}

    权重的设计

    比如说用户要查找 “list” 这个单词，找到了好几篇文档都含有 “list”  ，那么哪篇文章显示在前，哪篇在后？

    第一种：按照 docid 从小到大去显示：1，2，13，25，27，34，67，....

    第二种：按照匹配程度去显示：比如说：13号的 list 在标题出现了10次，在正文出现了 100 次；1号的 list 在标题出现了1次，在正文出现了 1次。那么13号文档更匹配，所以排名要在1号的前面。

    第三种：更加智能的计算：根据用户的点击数、点击频率、文档的更新频率、作者的维权程度、文档来源的权威程度等信息更精准的计算。

    第四种：谁给的钱多，谁靠前。

    我们这里采用的是第二种方法。

    所以，我们针对每个单词 ---> 每篇文档，都伴随一个 weight（权重），根据这个权重去排序（d倒序）

    权重的计算：10 * 单词出现在标题的次数 + 1 * 单词出现在正文中的次数。

    这里我们使用map 来维护，key就是某个词，value就是该词对应的权重

    • 标题 | 分词
    1. List wordInTitle = ToAnalysis.parse(title)  //对title进行分词
    2.     .getTerms()   
    3.     .stream()
    4.     .parallel()
    5.     .map(Term::getName)   
    6.     .filter(s -> !ignoredWordSet.contains(s))
    7.     .collect(Collectors.toList());
    • 标题 | 出现次数
    1. Map titleWordCount = new HashMap<>();
    2. for (String word : wordInTitle) {
    3.     int count = titleWordCount.getOrDefault(word, 0);
    4.     titleWordCount.put(word, count + 1);
    5. }
    • 正文 | 分词
    1. List wordInContent = ToAnalysis.parse(content)
    2.     .getTerms()
    3.     .stream()
    4.     .parallel()
    5.     .map(Term::getName)
    6.     .collect(Collectors.toList());
    • 正文 | 出现次数
    1.  Map contentWordCount = new HashMap<>();
    2. for (String word : wordInContent) {
    3.     int count = contentWordCount.getOrDefault(word, 0);
    4.     contentWordCount.put(word, count + 1);
    5. }
    • 计算权重值

    用map，某个词对应的权重是多少

    Map wordToWeight = new HashMap<>();

    1. 先计算出有哪些词，不重复

    就是使用set ，把所有的标题中的词初始化就都放入，然后再把所有正文的词也放入，set 中的元素是不能重复的。

    2.遍历set中的元素，看这个词在标题中出现多少次，在正文中出现多少次，最后计算权重：

    10 * 单词出现在标题的次数 + 1 * 单词出现在正文中的次数。

    3.最后把该词和他的权重放到map中，最后返回这个map即可。

    上述准备工作处理完成之后，我们开始进行倒排索引的生成和保护（在IndexManager类中）

    1.定义一个类 ，里面的对象用来映射 inverted_indexes 表中的一条记录

    1. // 这个对象映射 inverted_indexes 表中的一条记录（我们不关心表中的 id，就不写 id 了）
    2. @Data
    3. public class InvertedRecord {
    4.     private String word;
    5.     private int docId;
    6.     private int weight;
    7.  
    8.     public InvertedRecord(String word, int docId, int weight) {
    9.         this.word = word;
    10.         this.docId = docId;
    11.         this.weight = weight;
    12.     }
    13. }

    2.执行 sql 在index-mapper.xml 中

    2.     <insert id="batchInsertInvertedIndexes">
    3.         insert into inverted_indexes (word, docid, weight) values
    4.         <foreach collection="list" item="record" separator=", ">
    5.             (#{record.word}, #{record.docId}, #{record.weight})
    6.         foreach>
    7.     insert>

    单线程版本：

    3.设置 批量插入时，最多 10000 条

    int batchSize = 10000;

    4.准备一个List （recordList），里面是  InvertedRecord 类型的，然后根据分词不断向里面放入，放够10000条了就插入一次。（也就是本批次要插入的数据）

    5.遍历document 文件，调用 document.segWordAndCalcWeight() 方法，拿到分词结果。

    6.遍历每个单词，得到单词和权重，再得到他的docid。构建出这三个后把他们放入recordList中。

    7.如果 recordList.size() == batchSize，说明够一次插入了，够10000条了，就进行插入，插入完成之后清空 recordList。然后就会重新循环再走。

    8. recordList 还剩一些，之前放进来，但还不够 batchSize 个的，所以最后再批量插入一次。执行完成之后就可以认为是所有插入都完成了。

    多线程版本：

    一次插入10000条，一次处理50篇文档

    1. int batchSize = 10000;  // 批量插入时，最多 10000 条
    2. int groupSize = 50;

    提前把线程一批一批分好，分好之后交给线程去提交。

    1.     static class InvertedInsertTask implements Runnable {
    2.         private final CountDownLatch latch;
    3.         private final int batchSize;
    4.         private final List documentList;
    5.         private final IndexDatabaseMapper mapper;
    6.  
    7.         InvertedInsertTask(CountDownLatch latch, int batchSize, List documentList, IndexDatabaseMapper mapper) {
    8.             this.latch = latch;
    9.             this.batchSize = batchSize;
    10.             this.documentList = documentList;
    11.             this.mapper = mapper;
    12.         }
    13.  
    14.         @Override
    15.         public void run() {
    16.             List recordList = new ArrayList<>();    // 放这批要插入的数据
    17.  
    18.             for (Document document : documentList) {
    19.                 Map wordToWeight = document.segWordAndCalcWeight();
    20.                 for (Map.Entry entry : wordToWeight.entrySet()) {
    21.                     String word = entry.getKey();
    22.                     int docId = document.getDocId();
    23.                     int weight = entry.getValue();
    24.  
    25.                     InvertedRecord record = new InvertedRecord(word, docId, weight);
    26.  
    27.                     recordList.add(record);
    28.  
    29.                     // 如果 recordList.size() == batchSize，说明够一次插入了
    30.                     if (recordList.size() == batchSize) {
    31.                         mapper.batchInsertInvertedIndexes(recordList);  // 批量插入
    32.                         recordList.clear();                             // 清空 list，视为让 list.size() = 0
    33.                     }
    34.                 }
    35.             }
    36.  
    37.             // recordList 还剩一些，之前放进来，但还不够 batchSize 个的，所以最后再批量插入一次
    38.             mapper.batchInsertInvertedIndexes(recordList);  // 批量插入
    39.             recordList.clear();
    40.  
    41.             latch.countDown();
    42.         }
    43.     }
    44.  
    45.     @Timing("构建 + 保存倒排索引 —— 多线程版本")
    46.     @SneakyThrows
    47.     public void saveInvertedIndexesConcurrent(List documentList) {
    48.         int batchSize = 10000;  // 批量插入时，最多 10000 条
    49.         int groupSize = 50;
    50.         int listSize = documentList.size();
    51.         int times = (int) Math.ceil(listSize * 1.0 / groupSize);
    52.         CountDownLatch latch = new CountDownLatch(times);
    53.  
    54.         for (int i = 0; i < listSize; i += groupSize) {
    55.             int from = i;
    56.             int to = Integer.min(from + groupSize, listSize);
    57.             List subList = documentList.subList(from, to);
    58.             Runnable task = new InvertedInsertTask(latch, batchSize, subList, mapper);
    59.             executorService.submit(task);
    60.         }
    61.  
    62.         latch.await();
    63.     }

    4.搜索模块

    依赖索引构建完成之后才能进行，需要 web 功能

    使用SpringMVC 实现了Web服务

    只针对一个词进行搜索

    select docid,weight from inverted_indexes where word = 'list' order by weight desc;

    select * from forward_indexes where docid in (...);  这样排出来是无序的

    需要根据 weight 重新再进行一次排序

    把上述合并成一条联表 SQL

    select ii.docid,title,url,content,from inverted_indexes ii

    join forward_indexes fi on ii.docid = fi.docid

    where word = 'list'

    order by weight desc;   这样排完之后是有序的

    前端传过来这个词，根据词 去 倒排索引 + 正排索引中搜索，得到文档列表（可以做分页）

     查询很慢，只是一个词就需要1.8秒，如果搜索的多了，时间更久，没有人愿意等待这么久

    这里我们使用向表中新建索引来解决这个问题（针对 word 列去建索引）

    建索引的过程，就是把 word 列作为 key，docid 作为 value，新建一棵搜索树（B+树）

    从 key 查找 value，则时间复杂度变成O(log(n)) 21次 远远小于O(n) 200W 次

    建索引的速度很慢，而且会导致数据插入很慢，所以，在表中的数据已经插入完成的情况下，再添加索引

    给 word 和 weight 都添加索引，先用word 查，查完之后利用 weight 我们可以利用索引直接进行排序。

    建立索引之后，查询只需要0.2秒

    搜索树的 key：索引中的字段 word + weight（复合索引）

    左边是word，右边weight

    左边可以比较大小：索引的命中规则遵守靠左原则，select ... from 表 where word = ' ... ' 可以用上索引

    随后按weight 进行排序，因为 key 里就有 weight ，所以 key 本身就是按照 weight 排序好的（搜索树的有序原则）

    1. 不加索引的情况下查询慢（因为排序 和 查询都没有用到索引）。
    2. 针对 word 加索引，性能有所提升（查询使用了索引，排序没有用，相对快，但还不够快）。
    3. 针对word 和 weight ，使用索引，性能明显提升（查询和排序都使用了索引，非常快）

     1.动态资源 /web， qurty=... 必须填的 page=...选填，但必须是数字

    写一个Controller ，叫做 SearchController ，通过 @Controller 注解修饰，代表这是一个控制器。实现  @GetMapping("/web")，查询的url 是 /web。里面 return "search";最后会渲染 search.html 这个模板

    @GetMapping 注解

    @GetMapping是一个组合注解，等价于@RequestMapping (method = RequestMethod.GET)，它将HTTP Get请求映射到特定的处理方法上。

    2.之后就需要进行查询，定义一个 Document 类 模板，其中需要 title、url、content。

    3.这些东西需要根据数据库去查，因此我们需要一个接口——SearchMapper，用@Repository @Mapper 这两个注解来修饰。里面返回的是一组 Document 类型的 list

    1. @Repository
    2. @Mapper
    3. public interface SearchMapper {
    4.     List query(
    5.             @Param("word") String word,
    6.             @Param("limit") int limit,
    7.             @Param("offset") int offset);
    8.  
    9.     List queryWithWeight(
    10.             @Param("word") String word,
    11.             @Param("limit") int limit,
    12.             @Param("offset") int offset
    13.     );
    14. }

    @param 注解

    @param 标签提供了对某个函数的参数的各项说明，包括参数名、参数数据类型、描述等。

    @param 标签要求您指定要描述参数的名称。

    您还可以包含参数的数据类型，使用大括号括起来，和参数的描述。

    参数类型可以是一个内置的JavaScript类型，如 string 或 Object ，或是你代码中另一个标识符的 JSDoc namepath（名称路径） 。

    如果你已经在这namepath（名称路径）上为标识符添加了描述，JSDoc会自动链接到该标识符的文档。

    配置文件：

    1. spring:
    2.   main:
    3.     log-startup-info: false
    4.     banner-mode: off
    5.   datasource:
    6.     url: jdbc:mysql://127.0.0.1:3306/searcher_refactor?characterEncoding=utf8&useSSL=false&serverTimezone=Asia/Shanghai
    7.     username: root
    8.     password: 123456
    9.  
    10. mybatis:
    11.   mapper-locations: classpath:mapper/search-mapper.xml
    12.  
    13. logging:
    14.   level:
    15.     com.lingqi.searcher.web: debug

    具体的查询语句，这里使用 mybatis ，在 search-mapper.xml 语句中写具体的查询语句

    2.     <select id="query" resultMap="DocumentResultMap">
    3.         select ii.docid, title, url, content
    4.         from inverted_indexes ii
    5.         join forward_indexes fi
    6.             on ii.docid = fi.docid
    7.         where word = #{word}
    8.         order by weight desc
    9.         limit ${limit}
    10.         offset ${offset}
    11.     select>

    4. 在  SearchController 中写具体步骤

    • 得到查询的词是哪个词（query）参数的合法性检查 + 处理
    1. if (query == null) {
    2.     log.debug("query 为 null，重定向到首页");
    3.     return "redirect:/";
    4. }
    5.  
    6. query = query.trim().toLowerCase();
    7. if (query.isEmpty()) {
    8.     log.debug("query 为空字符串，重定向到首页");
    9.     return "redirect:/";
    10. }
    • 分词
    1. List queryList = ToAnalysis.parse(query)
    2.     .getTerms()
    3.     .stream()
    4.     .map(Term::getName)
    5.     .collect(Collectors.toList());
    • 如果分词后，queryList  为空，也就是分词后一个词都没有，那么证明没有找到这个词，让他重定向到首页
    • 处理分页的问题 （得到page，计算出limit + offset）
    1. int limit = 20;
    2. int offset = 0;
    3. int page = 1;
    4.  
    5. if (pageString != null) {
    6.     pageString = pageString.trim();
    7.     try {
    8.         page = Integer.parseInt(pageString);
    9.         if (page <= 0) {
    10.             page = 1;
    11.         }
    12.  
    13.         limit = page * 20;
    14.      } catch (NumberFormatException ignored) {}
    15. }
    • 执行SQL进行查询
    • 将数据添加到 model 中，是为了在 渲染模板的时候用到（这里使用了SpringMVC的模板渲染技术（ViewResover），这里具体使用的是 Thymeleaf）
    • Model 添加渲染需要的数据：query、docList、page
    1. model.addAttribute("query", query);
    2. model.addAttribute("docList", documentList);
    3. model.addAttribute("page", page);
    • 指定使用哪个模板来进行渲染 return "search" 对应 resources/templates/search.html

    5.搜索出来之后，展示基本内容部分

    首先我们可以拿到这个文本的内容，我们可以前面截取120 个字，后面截取120 个字。

    1. public Document build(List queryList, Document doc) {
    2.         // 找到 content 中包含关键字的位置
    3.         // query = "list"
    4.         // content = "..... hello list go come do ...."
    5.         // desc = "hello list go com..."
    6.  
    7.         String content = doc.getContent().toLowerCase();
    8.         String word = "";
    9.         int i = -1;
    10.         for (String query : queryList) {
    11.             i = content.indexOf(query);
    12.             if (i != -1) {
    13.                 word = query;
    14.                 break;
    15.             }
    16.         }
    17.         if (i == -1) {
    18.             // 这里中情况如果出现了，说明咱的倒排索引建立的有问题
    19.             log.error("docId = {} 中不包含 {}", doc.getDocId(), queryList);
    20.             throw new RuntimeException();
    21.         }
    22.  
    23.         // 前面截 120 个字，后边截 120 个字
    24.         int from = i - 120;
    25.         if (from < 0) {
    26.             // 说明前面不够 120 个字了
    27.             from = 0;
    28.         }
    29.  
    30.         int to = i + 120;
    31.         if (to > content.length()) {
    32.             // 说明后面不够 120 个字了
    33.             to = content.length();
    34.         }
    35.  
    36.         String desc = content.substring(from, to);
    37.  
    38.         // 这里添加i标签，可以使这个单词高亮显示
    39.         desc = desc.replace(word, "" + word + "");
    40.  
    41.         doc.setDesc(desc);
    42.  
    43.         return doc;
    44.     }

    针对多个词进行搜索

    和单词搜索的区别就是 权重值需要重新计算

     多次中，就需要有一个权重值聚合的问题

    docid 相同的，weight=sum（w1,w2,w3）

    docid=1  weight = 13 + 7 + 1

    docid=2  weight = 22

    把实际业务抽象成如下的简单题：给定3个有序数组（按照权重从大到排序），最终结果的权重（sum=w1+w2+w3|docid相同），给出第 x 到第 y 个元素

    假如需要【0，20），必须把 每个【0，20）找出，聚合权重，重新排序，算出结果中的【0，20）

    假如需要【20，40），必须把 每个【0，40）找出，聚合权重，重新排序，算出结果中的【20，40）

    假如需要【40，60），必须把 每个【0，60）找出，聚合权重，重新排序，算出结果中的【40，60）

    如果数据量太大，这种找法是不可能的，内存空间可能不足，时间效率也很低

    因此实际中我们会舍弃他的准确性，比如说某次考试，前1000名学生，各自的排名多少是非常重要的，不能出错。后1000名同学，排名略有错误，其实也不重要。实际上上就是牺牲正确性来换取性能。

    结果必须重新计算，所以没办法使用MySQL帮我们排序了

    • 首先我们先对所有的词进行查找，查找出来先放到 totalList 中
    1. List totalList = new ArrayList<>();
    2. for (String s : queryList) {
    3.     List documentList = mapper.queryWithWeight(s, limit, offset);
    4.     totalList.addAll(documentList);
    5. }
    • 针对所有文档列表，做权重聚合工作

    维护:docId -> document 的 map

    1.我们遍历 totalList 针对每一个docid 我们往里面放。遇到重复的，不断累加。

     2.此时我们就有了每个单词对应的权重了，这放在 documentMap 中，我们需要对这个权重进行一个排序，首要要拿到这些权重，放在 Collection 中

    3.但 Collection 没有排序这个概念（只有线性结构才有排序的概念），所以我们需要一个 List

    4. 按照 weight 的从大到小排序

    1. Collections.sort(list, (item1, item2) -> {
    2.     return item2.weight - item1.weight;
    3. });

     5. 从 list 中把分页区间取出来

    1. int from = (page - 1) * 20;
    2. int to = from + 20;
    3.      
    4. List subList = list.subList(from, to);
    5. List documentList = subList.stream()
    6.     .map(DocumentWightWeight::toDocument)
    7.     .collect(Collectors.toList());

     具体的查询语句，这里使用 mybatis ，在 search-mapper.xml 语句中写具体的查询语句：

    1.     <select id="queryWithWeight" resultMap="DocumentWithWeightResultMap">
    2.         select ii.docid, title, url, content, weight
    3.         from inverted_indexes ii
    4.         join forward_indexes fi
    5.         on ii.docid = fi.docid
    6.         where word = #{word}
    7.         order by weight desc
    8.         limit ${limit}
    9.         offset ${offset}
    10.     select>

    完整代码：

    构造索引：搜索引擎_构建索引模块: 写一个搜索引擎的项目

    搜索模块：https://gitee.com/hlingqi/search-engine-search-module

    项目测试：[测试] 搜索引擎的相关测试_我要敲代码6400的博客-CSDN博客

  • 相关阅读:
    [附源码]计算机毕业设计JAVAjsp校园自行车租售管理系统
    快速安装 kafka 集群
    深入理解@Transactional注解
    mysql 锁总结
    吴恩达深度学习笔记（七）——机器学习策略
    【CVPR2022 点云3D检测SOTA】SoftGroup for 3D Instance Segmentation on Point Clouds
    四种常见分布式限流算法实现！
    TypeScript开启
    公司新来了个00后卷王，一副毛头小子的样儿，哪想到...
    BeanPostProcessor(Spring后置处理器)如何使用呢？
  • 原文地址：https://blog.csdn.net/weixin_61567666/article/details/126300960