当前位置:   article > 正文

Java项目之搜索引擎_java实现搜索引擎

java实现搜索引擎

前置知识

搜索引擎的核心功能,就是查找到一组和用户输入的词/一句话 相关联的网页

关键字:搜索词;搜索结果的标题,搜索结果的描述,展示URL,跳转过去的目标页面,称为“落地页”;

对于一个搜索引擎来说,首先,需要获取到很多很多的网页;然后再根据用户输入的查询词,在这些网页中进行查找。

1.搜索引擎的网页是怎么获取到的?

此处主要是涉及到“爬虫”这样的程序(Http客户端)

2.用户输入了查询词之后,如何去让查询词和当前的这些网页进行匹配?

假设当前已经爬取到了一亿个网页,用户输入了一个"蛋糕"这样的查询词。这样的暴力搜索,是非常低效的,而搜索引擎需要能够让用户非常高效的获取到结果。

这时候就需要一种特殊的数据结构,倒排索引

倒排索引

先介绍几个概念

  1. 文档(document):指的是每个待搜索的网页
  2. 正排索引:指的是 文档id => 文档内容
  3. 倒排索引:指的是 词 => 文档id列表

举个例子
正排索引:

文档 id 为1的内容为 : 我要出去实习挣钱
文档 id 为2的内容为:我要发论文顺利毕业
  • 1
  • 2

倒排索引:

 我要       1,2
 出去	   1
 发论文     2
 实习       1
 顺利       2
 挣钱       1
 毕业	   2
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

项目目标:实现一个针对Java文档的搜索引擎

获取Java8官方文档下载地址

在本地基于离线文档来制作索引。实现搜索,当用户在搜索结果页点击具体的搜索结果的时候,就自动跳转到在线文档的页面。

模块划分

  1. 索引模块
    ①扫描下载到的文档,分析文档的内容,构建出正排索引+倒排索引。并且把索引内容保存到文件中
    ②加载制作好的索引,并提供一些API实现查正排和查倒排这样的功能

  2. 搜索模块
    调用索引模块,实现一个搜索的完整过程
    输入:用户的查询词
    输出:完整的搜索结果(包含了很多条记录,每个记录都有标题,描述,展示URL,并且点击能够跳转)

  3. web模块
    需要实现一个简答的web程序,能够通过网页的形式来和用户进行交互
    包含了后端和前端

创建 Maven 项目

针对用户输入的内容 进行分词

分词的原理

  1. 基于词库
    尝试把所有的 “词” 都进行穷举,把这些穷举结果放到词典文件中
    然后就可以依次的取句子中的内容。每隔一个字,在词典里查一下;每隔两个字,查一下。

  2. 基于统计
    收集到很多很多的“语料库” => 人工标注=>也就知道了那些字在一起的概率比较大

使用现成的第三方库 ansj 来实现分词。

import org.ansj.domain.Term;
import org.ansj.splitWord.analysis.ToAnalysis;

import java.util.List;

public class TestAnsj {
    public static void main(String[] args) {

        String str = "我要赶快做好简历,准备实习,先出去实习再说";
        // ToAnalysis.parse(str) 返回的是 Result 类型
        List<Term> terms = ToAnalysis.parse(str).getTerms();

        // Term 就表示一个分词结果
        for (Term term : terms) {
            System.out.println(term.getName());
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

代码运行的警告是因为没有配置字典。

Parser 类(根据文档路径 读取文件,构建索引 并 保存到指定文件中)

解析出 HTML 对应的 URL 说明

Java API 文档有两份:

  1. 线上文档
  2. 线下文档(下载到本地的文档)

线上: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
线下:D:\Java\javaDocument\docs\api\java\util\ArrayList.html

期望达到的结果是,用户点击搜索结果,能够跳转到对应的线上文档的页面。
以 https://docs.oracle.com/javase/8/docs/api/ 为固定前缀。
将本地文档的后半部分 java\util\ArrayList.html 提出出来与固定前缀进行拼接。

倒排索引

倒排索引,词 => 文档 id 之间的映射关系

首先就需要先知道当前这个文档,里面都有那些词

因此就需要针对当前文档也进行分词

  1. 针对标题
  2. 针对正文

因此就可以先针对当前文档进行分词,然后根据每个分词结果;去倒排索引中,找到对应的 value,然后把当前文档 id 给加入到对应的 value列表中即可。

如何来确定权重的值?

这个值描述了 词 和 文档 之间的“相关性”

此处单纯的通过 词 出现的次数,来表示相关性。

权重计算公式:标题中出现的次数+10 + 正文中出现的次数

保存索引结构到磁盘中

索引当前是存储在 内存 中的。构建索引的过程是比较耗时的。

需要把内存中的索引结构,变成一个“字符串”,然后写文件即可。

对应的,把特定结构的字符串,反向解析成一些结构化数据(类/对象/基础数据结构) (反序列化)

通过 json库 来实现序列化和反序列化。ObjectMapper对象

	objectMapper.readValue(forwardIndexFile, new TypeReference<ArrayList<DocInfo>>() {});
    objectMapper.readValue(invertedIndexFile,new TypeReference<HashMap<String,ArrayList<Weight>>>() {});
  • 1
  • 2

创建一个匿名内部类,这个类实现了 TypeReference.同时再创建一个这个匿名内部类的实例。创建这个实例最主要的目的,就是为了把 ArrayList 这个类型信息,告诉 readValue 方法。

关于 Parser 和 Index 之间的关系

Parser 相当于制作索引的入口 => 对应到一个 “可执行” 程序
Index 相当于实现了索引的数据结构,提供了一些 api

Index 类就要给 Parser 进行调用,才能完成整个制作索引的功能

性能优化

在这里插入图片描述

通过测试,发现当前主要的性能瓶颈,在循环便利文件上。
每次循环都要针对一个文件进行解析。读文件+分词+解析内容(主要还是卡在CPU运算上)

单个线程的情况,任务都是串行执行的。
多个线程,这些任务就可以并发执行.

线程池之保证所有文档处理完毕再保存索引

CountDownLatch 类似于跑步比赛的裁判
只有所有的选手都撞线,就认为这场比赛就结束了

给制作索引代码加锁

如果直接把 synchronized 加到 parseHTML 或者 addDoc 这样的方法上,是不科学的,这样做锁的粒度太粗了,并发程度不高,提高的效率有限。因此要把枷锁的粒度搞细一点。

在这里插入图片描述

解决进程不退出的问题

关于守护线程
如果要是一个线程是守护线程(后台线程),此时这个线程的运行状态,不会影响到进程结束。
如果要是一个线程不是守护线程,这个线程的运行状态,就会影响到进程结束。

前面学过的线程创建的手段,默认创建出来的都是非守护线程,需要通过 setDaemon 方法手动设置,才能成为守护线程。

通过线程池创建的线程,并不是守护线程。
当main方法执行完了,这些线程仍然在工作(仍然在等待新任务的到来)

开机之后,首次制作索引特别慢的问题

是由于缓存,parseContent的核心操作,就是读取文件。从磁盘进行访问,操作系统就会对“经常读取的文件”进行缓存。
首次运行的时候,当前的这些Java文档,都没有在内存中缓存。因此读取的时候只能从硬盘上读取。
后面再运行的时候,由于前面已经读取过这些文档了,这些文档在操作系统中其实已经有了一份缓存(在内存中),这次的读取不必直接读硬盘,而是直接读内存的缓存(速度就会快很多)

正则表达式

正则里面主要就是有很多特殊符号
. 表示匹配一个非换行字符(不是 \n 或者不是 \r )
* 表示前面的字符可以出现若干次
.* 匹配非换行字符出现若干次

去除script标签和内容
<script.*?>(.*?)</script>

去除 普通 的标签(不去掉内容)
<.*? > 既能匹配到开始标签,也能匹配到结束标签

? 表示“非贪婪匹配”,匹配到一个符合条件的最短结果
不带?的.* 表示“贪婪匹配” 匹配到一个符合条件的最长结果

约定前后端交互接口

此处只需要实现一个搜索接口即可。

请求:
GET /searcher?query=[查询词] HTTP/1.1

相应:
HTTP/1.1 200 OK

[
{
title:“这是标题1”,
url:“这是url1”,
desc:“这是描述1”,
}
]

实现标红逻辑

  1. 修改后端的代码。生成搜索结果的时候(生成描述),就需要把其中包含查询词的部分,给加上一个标记。
    例如,给这个部分套上一层<i>标签
  2. 然后在前端这里针对<i>标签设置样式,然后浏览器就可以根据<i>标签的样式来进行显示了。

在这里插入图片描述

处理停用词

网上搜到的停用词表,接下来可以让搜索程序加载这个停用词表到内存中。使用一个HashSet把这些词都存起来。
再针对分词结果,在停用词表中进行筛选。
如果某个结果在词表中存在,就直接干掉。

一个文档包含多个查询词,进行权重相加

要想实现这样的效果,就需要把触发结果进行合并。
需要把多个分词结果触发出的文档,按照 docId进行去重,同时进行权重的合并。

去重的核心思路:
数据结构阶段,链表~合并两个有序链表
此处按照类似的思路来合并两个数组

先把分词结果进行一个排序处理(按照 docId 升序排序)
再进行合并,合并的时候就可以根据 docId 值相同的情况,做权重相加。

注意!当前的分词结果,不一定就只是分成两个部分,很可能是多个部分,此时就变成了N个数组合并了。

多路归并

对于两路数组归并,核心就是对比指向两个数组元素的值的大小关系,找到小的,插入到结果中

对于多路数组归并,核心思路仍然是对比多个数组的值的大小关系,找到小的,插入到结果中

使用 堆(小堆)/优先级队列(√)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/862353
推荐阅读
相关标签
  

闽ICP备14008679号