实现的搜索功能
首先获取很多的网页,然后根据用户输入的查询词,在这些网页中进行查找
用户输入查询词之后,如何让查询词和当前的网站进行匹配?
首先获取很多网页(爬虫->一个http客户端,发送http请求获取http响应结果(就是网站))(批量化的获取很多的页面),
再根据用户输入的查询词,在网页中进行查找
正排索引和倒排索引
能够让用户通过查询词非常高效的获取到结果
1.文档: 每个待搜索的网页(被爬虫技术,把各个网站的各个网页搜集在一起,然后保存到服务器上)
因为爬取过来的网页很多, 为了区分每个网页, 因此就要给一个类似于人的身份证这样的标识: 文档ID
2. 正排索引: 文档Id(身份标识)-> 文档内容(包含很多段落,句子,词..)
通过文档Id就能够快速高效的查询到文档的详细内容
3. 倒排索引: 词-> 文档id列表(包含词)
给一个词, 不管这个词在哪个文档里面出现 ,就会返回一个每一个都包含这个词的文档id列表(一系列文档都会包含这个词)
用户输入查询词之后,如何让查询词和当前这些网页进行匹配
->使用倒排索引
正排索引: 根据id就能够找到一个文档的内容
倒排索引: 根据一个词返回一系类包含整个词的文档id,也就是根据这个词我们找到对应的文档id,再通过这个id就能找到这个文档
项目目标
项目目标: 实现一个针对Java文档的搜索引擎
百度是属于"全站搜索",搜索整个互联网上的网站
B站是属于"站内搜索".只针对某个网站的内容进行搜索
针对这个文档实现搜索功能(官方是没有搜索框的) 实现一个站内搜索.
实现步骤
1> 获取网页到电脑主机上(下载离线文档)
我们直接从官方网站上下载压缩包
观察在线文档和离线文档路径的对应关系, 发现后半部分的url是一模一样的,因此我们再本地基于离线文档来制作索引, 实现搜索. 当用户在搜索页点击具体的搜索结果的url时候,就自动跳转到在线url
线文档和在线文档的路径都是对应的, 我们可以根据离线文档的路径直接构造出在线文档的路径
2> 扫描离线文档, 构造索引(正排,倒排)
3> 使用索引, 实现完整的搜索过程
模块划分
1> 索引模块
1) 扫描下载到的文档. 分析文档的内容. 构建出正排索引和倒排索引. 并且把索引的内容保存在文件中
2) 加载制作好的索引. 提供api实现查正排和倒排这样的功能
2> 搜索模块
1) 调用索引模块, 实现一个搜索的完整过程
输入: 用户的查询词
输出: 完整的搜索结果 (包含很多条记录, 每个记录有标题, 描述, 展示url, 并且点击能够跳转)
3> web模块(面向用户)
需要实现一个简单的 web 程序, 能够通过网页的形式来和用户进行交互
分词的概念
用户在搜索引擎中, 输入的查询词, 不一定真的只是一个词, 也可能是一句话.(
因此我们要把一个完整的句子切分, 然后经过分词结果, 每个词分别找到和它相关的文档
分词:
把一个完整的句子,切分为多个词
基于现成的第三方库来实现分词
中文分词很难, 但是英文分词很容易, 因为一句话每个词与词之间就存在空格作为分隔符
分词的实现原理
1. 基于词库
通过穷举出所有的词, 然后把穷举结果放到词典文件中, 每隔几个字就去词库查一下
但是局限性就是,现在网络构词很多, 频繁更新词库太不现实
如: 单身狗这种在词库里基本找不到,因为是网络造的词
2. 基于统计
收集很多的"语料库",然后通过人工标注/统计 => 某俩个字在一起使用的概率很大,此刻我们就可以把它们标注为一个词
基本上都是一起使用来应对更加复杂的分词
实现分词的第三方库: ansj
Another Nature Semantic Jieba
<dependency>
<groupId>org.ansj</groupId>
<artifactId>ansj_seg</artifactId>
<version>5.1.6</version>
</dependency>使用第三方库
getTerms()是把结果转化为java能够使用的像list这样的容器类
getName()获取分词的名字
实现索引模块
创建一个Parser类: 完成制作索引的过程
Parser: 读取下好的文档,然后解析文档内容,完成索引的制作
run是parser的入口类, 通过这个方法实现单线程制作索引
run()里面的执行步骤:
1. 根据指定的线下文档路径, 枚举出这个路径所有的html文件(包括文件里面的子目录),得到html线下文件路径
线下文件路径(点击html后产生的)
2. 针对上面罗列出来的文件路径, 依次打开文件, 读取文件内容, 并进行解析, 构建索引
3. 把在内存中构造好的索引数据结构, 保存在指定的文件中
1. 根据指定的线下文档路径, 枚举出这个路径所有的html文件(包括文件里面的子目录),得到html线下文件路径
使用ArrayList来接收所有的html文件
enumFile()方法是用来枚举线下文档的文件的
enumFile()方法的实现
listFiles()这个方法只能获取当前目录的内容(一个集合),它不会进行递归操作
此时我们要看到子目录内容, 就需要进行递归操作, 根据f的类型, 决定是否要递归
// 根据当前 f 的类型, 来决定是否要递归.
// 如果 f 是一个普通文件, 就把 f 加入到 fileList 结果中
// 如果 f 是一个目录, 就递归的调用 enumFile 这个方法, 来进一步的获取子目录中的内容.
isDirectory()这个方法是用来判断是不是文件夹, 如果是文件夹, 那么我们就进行递归调用enum()
反复递归执行, 就能把离线文档的所有html文件获取到fileList里面
问题: 我们把非html的文件也加入了
去除非html文件
我们通过文件的后缀(拓展名来进行判断是不是html)
一个文件的扩展名,都是随便起的,一般代表文件的格式
f.getAbsolutePath().endsWith(".html")//获取文件的绝对路径,并且看路径的拓展名是不是.html
2. 针对上面罗列出来的文件路径, 依次打开文件, 读取文件内容, 并进行解析, 构建索引
创建一个parseHTML方法, 来解析html
解析获取的html: 标题, 描述(正文的一段摘要, 我们先获取正文,再获取摘要),url
1) 解析出 HTML 的标题
创建parseTitle()方法解析html的标题
2) 解析出 HTML 对应的 URL
创建parseUrl()方法解析html对应的url
3) 解析出 HTML 对应的正文 (有了正文才有后续的描述)
创建parseContent()方法解析html对应的内容
4> 把解析出来的内容加入到索引当中
1) 解析出 HTML 的标题
标题就和我们的html文件名称一样, 我们就可以通过获取到html文件的内容来获取标题
我们通过文件getName()方法获取文件名, 然后通过string类的substring()方法,来截取去除.html为后缀的文件名称
完成
java计算长度
2) 解析出 HTML 对应的 URL
我们的url是用来点击进行跳转的
Java API 文档,有俩份
1. 线上文档
2. 线下文档(下载到我们本地的文档)
我们发现线上文档的后面docs开始都是一样的
我们希望用户点击线下文档的搜索结果,就能够跳转到线上的文档页面
我们把线上文档url不同的地方当成固定前缀. 然后拼接本地文档的后缀(变动)
具体代码实现
注意: 有/和\,但是因为浏览器的容错能力很强 ,因此没关系
subString(参数1): 这个只要一个参数的时候,就告诉它是从这个位置开始,一直截取到末尾,我们里面的参数就放置需要去除部分的前缀长度.从而我们就可以获取公共的变动的后缀.
最后进行拼接
3> 解析正文
一个完整的html文件 = html标签+内容
我们只关心内容,不要html标签
我们需要去掉标签
此时我们可以用正则表达式来去标签,正则表达式是一种计算机中进行字符串处理/匹配 常用的字段
核心就是通过一些特殊符号来描述字符串的特征, 然后看某个字符串是否符合这些特征
此时我们使用更加简单的方式来实现
html都是<>包裹起来的
我们依次去读这个HTML中的每个字符, 然后针对这个字符进行判断,如果是<,就从这个位置开始,直到遇到>,都不把字符放到结果中. 也就是说遇到的不是<, 就把当前的字符拷贝到结果中(StringBuilder)
使用一个flag标志位: 遇到 < 把flag设置为false, 就不拷贝遇到 > 就把flage设为true,就进行拷贝.
这样就实现了去除html标签, 只留下内容
html里面的内容<用<,>使用>来进行代替
具体实现
按照一个字符一个字符进行读取, 以 < , > 来控制拷贝数据的开关
关于读取字符,一个字节8个比特位, 一个字符有好几个字节
FileInputStream读取字节 FileReader读取字符
准备开关: isCopy, 和一个保存结果的StringBuilder(线程不安全,效率更高)
使用read(),一次读一个字符(返回的是int),关于为什么返回的不是char,因为读到文件末尾,继续读的话,int会返回-1进行提醒
如果不是-1就说明是一个合法的字符,我们再把int -> char,然后我们进行判需不需要拷贝
如果是<就不拷贝,其他的字符就进行拷贝. 遇到<把isCopy设置为false, 表示不拷贝,直到遇到>的时候,把开关设置为true,表示后面的字符是内容,就进行拷贝
但是html内容里面的换行太多了,读进去后展现出来不好看, 那么我们就把换行都换为空格
最后要进行资源的关闭
但是java里面的try可以设置,自动进行关闭资源(把创建文件语句放进去)
这就完全完成了内容的获取
此刻我们完成了标题, url, 内容的获取
创建Index类,通过这个类,使用解析出来的内容在内存中构造出索引
提供的方法:
1) 给定一个 docId, 在正排索引中, 查询文档的详细信息
public DocInfo getDocInfo(int docId) 给定docId返回一个DocInfo对象
2) 给定一个词, 在倒排索引中, 查询哪些文档和这个词关联
pulic List<Weight> getInverted(Sting term) 根据一个查询词,返回对应的含有这个词的一组Weight
返回值不能单单是一个整数, 因为词和文档是有"相关性"的: Weight
此时我们再创建一个类,包含了docId和相关性
3) 往索引中新增一个文档
public addDoc(String title,String url,String content), 把文档增加到索引里面去
4) 把内容中的索引结构保存在磁盘里面
pulic void save()
5) 把磁盘里面的索引数据加载到内存中
public void load()
创建DocInfo类来表述一个文档的相关信息
创建Weight: 把 docId 和文档与词之间的相关性权重进行一个包裹
weight属性值越大,相关性越大
4> 把解析出来的内容()加入到索引当中
3. 把在内存中构造好的索引数据结构, 保存在指定的文件中
构建正排序索引和倒排索引
索引大小就是设置的DocId
正排索引实现: id ->doc对象
倒排索引: 词->文档id
需要进行分词
权重值: 描述词和文档的相关性,我们此时通过词出现的次数表示相关性
计算权重的公式: 标题1次抵文章出现10次
迭代这些公式的方法
"小流量实验"
是否忽略大小
梳理倒排索引的步骤
什么时候使用for each
构建文档出现的问题
<dependency>
<groupId>com.fasterxml.jackson.core</groupId>
<artifactId>jackson-databind</artifactId>
<version>2.13.0</version>
</dependency>json格式
反序列化: 把串转为对象
创建匿名内部类的实例的目的
计算保存和加载的时间
paeser和Index的关系
生成文件的数据
衡量加载时间
性能优化
找到性能瓶颈(那个部位耗时最高)
说明遍历的耗时最多
把刚刚单线程的代码改成多线程
单线程: 18秒
提交任务操作很快,保存所有可能会有线程安全的问题
分析过程
保证在save之前把任务都处理完成
考虑线程安全: 多个线程是否同时使用公共的东西,尝试修改同一个对象, add里面有操作公共的对象
索引大小....
此处使用加锁的方式来解决线程安全问题
修改版本
我们分别操作正排和倒排是不会产生锁竞争的,因此我们不需要对整个index对象进行枷锁,我们对各种的正排和倒排进行加锁即可,让并发最大化
最终结果:使用八个线程来执行,只要7秒
放多少个线程合适?
细节问题
1> 守护线程
通过线程池创建的线程, 不是守护线程
当main方法执行完了,这些线程任然在工作(任然在等待)
程序依然在执行(进程没有退出)
进程顺利结束
2> 第一次制作索引的时候,速度很慢,第二次很快.关机后再第一次制作, 又会很慢..
主要是parsContent里面有读文件的操作,开销很大
猜想,是否开机之后,首次运行读取文件速度特别慢?
我们第一次运行
后面再运行
差距很大,主要是缓存的问题
解决从磁盘读文件速度慢的问题,
提前使用缓存区, 把数据进行缓存
验证索引加载逻辑
小结:
实现Parse类
实现Index类
核心方法
实现搜索模块
调用搜索模块,来搜索的核心操作
1. 分词
2. 触发
3. 排序
4. 包装结果
构造摘要: 包含正文的查询词或者查询词的一部分
生成的思路: 获取所有的查询词的分词结果, 遍历分词结果, 看哪个结果在正文中出现
正文转小写
还有个问题
因此在生成描述的时候,要找到整个词都是匹配的,而不是一个词的一部分,保证word在内容中是独立的一个词
实现
我们的HTML里面js代码,因此去标签后,js也在倒排索引里面了
去除js里面的内容,使用正则表达式, 特殊字符串 描述了一些匹配规则
. 表示匹配一个非换行字符
*表示前面的字符可以出现若干次
去掉script标签和内容,去除普通的标签(不去掉内容)? 表示非贪婪匹配: 匹配到符合条件的最短结果
结果空格太多 了
我们依然使用正则,把多个空格合并为一个空格
然后进行搜索测试,发现没有js的代码了
小结:
实现了search方法
实现Web模块
提供一个web接口, 最终以网页的形式,把我们的程序呈现给用户
前端+后端
约定前后端的接口
此处我们只需要实现搜索接口即可
首先基于sevlet来进行实现
引入依赖
<dependency><groupId>javax.servlet</groupId><artifactId>javax.servlet-api</artifactId><version>3.1.0</version><scope>provided</scope></dependency>
search里面是当前搜索引擎的核心代码逻辑, 构造索引, 实现搜索逻辑
api里面实现的是sevlet的代码
实现前端页面,实现搜索页
使用ajax前后交互的常用手段
拼接传过来的数据
对应进行拼接
出现的一些问题
针对内容太多,超出了屏幕
点击后, 搜索结果页被目标页面替换问题:在a标签那里设置_blank属性
俩次搜索结果混合在一起的问题
把内容的分词进行标红
1. 修改后端代码, 把查询词加上标记,套上<i>标签
2. 针对<i>设置样式,比如给<i>字体颜色设置红色
500异常
当 array list的时候,分词结果还加上了空格,因此会搜出很多其他没有用的东西
此处使用暂停词: 高频,但是没有意义的内容
停用词是哪些?
把暂停词表加载到内存里面
然后读取到hashset里面,然后遍历我们的分词,然后使用contains方法,判断在不在暂停词的表里面
此刻其实还有问题, 就是边界问题,我们之前是 " "查询词" "来保证分词的独立性,但是 查询词. 并没有排除,此时还是使用正则表达式\b
indexOf 不支持正则,但是replaceAll支持, 我们把所有的\\b都替换成空格,然后我们再进行查找
然后package-use就成功把array)给标红了
显示搜索结果的条数
我们修改前端
然后我们发现,同一个文档可能会出现俩次(一个文档既有array又有list)
这个就要和之前算权重的公式有关
去重,权重的合并步骤
分析俩路归并
分析多路归并
建立堆: 完全二叉树,小根堆
权重合并
先从若干行拿到最小的值,然后和上次插入的值一样,然后判断是不是一个文档,是一个文档就进行权重的合并,不是就进行插入
最后搜索结果
总结
