搜索引擎

功能1：候选词推荐 满足相似的特点

功能2：网页搜索 标题或者正文中要包含关键字

处理报错的经验

1.使用gdb为主 编译的时候加上-g

使用gdb启动程序，运行到崩溃，使用bt命令查看调用，用堆栈，找到第一个自己写的代码的位置，打上断点，

重新运行，看一下数据对不对

2.比较简单的问题，可以通过加日志or加打印的方式去定位问题

3.链接错误，-l的选项有问题

编译错误 一般头文件的路径写错了 编译的时候加一个选项 -I

vim ~/.ycm_extra_conf.py

前置知识点 reactor

  1. 把readLine改为收小火车 readLine–>readrain 两次readn，一次收头四字节，二次收车厢

    客户端—>clie/qt

  2. 业务 重写process函数 执行推荐和搜索的业务

  3. timefd要掌握 缓存阶段用得上

功能候选词推荐

用户输入的是关键词

返回的是候选词

设置这个功能的意义是纠错，候选词一定是热门的，

目标：用户输入一个可能输错的值，给她推荐热门&&相似的词

怎么找热门的词？

1.事先收集一些资料，从数据当中统计词的信息，即统计词频

实现收集的数据是预料，从语料中提取出词和频率

离线阶段

在用户请求之前要做好很多工作，

  1. 收集资料（语料）–>统计—>得到单词的词和他的频率的集合（词频）

    英文的词频处理 可以写一个单独的可执行程序（放到bin/下，该目录下存在多个可执行程序）：

    1. 清洗（去标点（把\r \n都去掉），去大写）

    2. 切割 istringstream >> word

    3. 统计词频 vecto<pair<string,int>>

    4. 把map保存到文件里面（data/dict.dat）

    5. 记录字符和单词的关联,构成位置索引库(map<string,set>保存为文件data/dicindex.dat)，例如

      22ba88332dc15d6d203cc40cb36fb7d1.png

中文处理

  1. 中文是采用utf-8编码，变长把中文汉字和英文分别提取出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(){
    string arr = "hi武汉花生";
    for(size_t i = 0; i < arr.size(); ){
        //判断是中文的首字符还是英文的首字符
        //按位与 1000 0000 & ch
        if(0x80 & str[i] == 0){
            cout << "英文 ch = " << str.substr[i,1] << '\n';
            ++i;
        }else{
            cout << "中文 ch = " << str.substr[i,3] << '\n';
            i += 3;
        }
    }
}

中文不一定是三个字符，所以可以用下面的函数 根据字符的首个字节算出这个字符的字节数

d9f7cce435ebd70c9fe61ab54bf943a9.png

  1. 中文词典不好生成，分词

使用cppjieba,jieba对象只构建一次，每次用的时候传指针

在线阶段

server第一步先把词典加载到程序里变成一个map结构（预热）

conf/myconf.conf 存放ip和port

首先要实现一个服务端去接受响应， 可以使用reactor或者workflow

如果使用reactor那要考虑协议的问题

8aa0053f46203dc73aed2af0f0178949.png

当用户输入了一个关键词，

  1. 把关键词切割成单个的字符或汉字

  2. 遍历map

  3. 找到相似并且热门的词

补充一个额外的数据结构，包含当前字符的所有单词，都记录下来

排序 精排

对候选词进行排序，指标：相似度和热门情况

越相似越靠前，相似度相同，越热门越靠前

相似度匹配：前缀匹配或，最小编辑距离，协同过滤（双塔模型）

使用最小编辑距离

898adf2c83cd9c48b7f9035580f522a8.png

最小编辑距离就是三

再例如dad–>daddy最小编辑距离是2

使用动态规划算法 if A[i] = B[j] dp[i+1][j+1] = dp[i][j]

​ if A[i+1] != B[j+1] dp[i+1][j+1] = min(dp[i][j+1],dp[i+1][j])+1

算出最小编辑距离（编辑距离一样用热度排序）用优先队列存储，priority-queue 也可以重载小于号运算符，然后返回结果用json序列化

网页搜索

查询方向：已知内容查标题 —>倒排索引

采集数据：爬虫 本质是http客户端，

数据清洗：把xml数据统一成/docid,content,title,url

docid顺序编号。注意：内容不一定是标签

有些数据格式有问题，需要去掉，内容清洗完保存到网页库

优化网页库的访问，网页库太大了，内存放不下，每次只读一个网页（直到该网页的起始位置，本网页的长度），把所有网页的起始位置和长度存起来称为网页偏移库（fsteam网页库，内存中要留一个‘\0’,已知i的pos length 网页库 seekg(pos),网页库read(length)）

去重，去重重复的网页 simhash

d4869e13519e098ad0108e0bdcb7984a.png

从文档中选取n个最重要的词，每个词都有一个权重，先用hasb把这个词转换为01序列，然后根据哈希值算出该权重是正还是负，再把最终哈希值每一列求和，然后再把算出来的值转回01序列，就是提取指纹

怎么判断指纹是否接近，计算两个指纹的海明距离（按位异或），如果海明距离小于3，就说明是相等的

去重步骤：遍历初始的网页库，算出每一篇网页的指纹，生成一个去重网页库，每加入一个网页就要和里面的所有网页做比对

还要生成去重网页偏移库

生成倒排索引，unordered_map<string(单词),set<pair<int,double>>> set用来记录该单词在那些文章中出现过（int）,double(权重)TF/IDF或bm25计算权重 使用log2要加一个-lm的链接选项

遍历所有去重后的网页库，文档内，先用cppjieba分词，统计词频&单词在文档的数量

保存成文件

在线阶段

先预热，把网页偏移库和倒排索引加载到内存

用户发请求，请求是一个句子—>分词（过滤停用词）

​ 每个词都查倒排索引

​ 取交集

排序 相关性 余弦相似度算法 把查询语句分词然后和文档的词计算余弦值

如果每一篇文章单词特别多，到此每次计算他的权重都很大，所以要做归一化处理

怎么算基准向量，TF/IDF算法，词频是单词在句子中出现的次数，文章数量就是1，排序的结果用json序列化

阶段二

buffer缓冲：是一个先进先出的缓冲区，例如平衡内存外存的读写速度差异的区域

cache缓存：存在两个速度差异很大的设备，A设备容量小，速度快，B设备容量大，速度慢，将一部分数据从B拷贝一份给A，这样访问该数据从A可以加快速度，（在高速设备上复制一份低速设备的数据）

需求：给搜索引擎加一个缓存

管理缓存的策略：FIFO 先来的消息先被淘汰 不太好

​ LFU 最近最小频率

​ LRU list unordered_map/map

实现版本一： redis保存

在一次请求来了之后在磁盘中找，找到之后就写入redis 再返回

实现版本二：把缓存作为进程内的数据

考虑临界资源的问题，要加解锁，但是有线程加锁做业务其他会阻塞，导致性能变差

解决方案一因为共享的要加解锁，那就给每个线程弄一个缓存，但这样会导致每个线程的缓存内容不一样，可能线程一已经查过并存缓存了，另一个线程没存，另一个线程在访问的时候又要查内存，导致缓存命中率下降

实现版本三：让所有的缓存内容一致，但不追求立刻一致，追求一段时间后一致，例如每一分钟同步一次（仍然要加锁，加锁频率下降）

同步的策略

a331391056b36714a327d82d842f54b5.png

选取第一个节点为主节点，然后将第二个节点和之后的节点合并，然后广播给所有人

方案一：整个过程一直加锁

bab26441399dbe43c669a6c6ef481f1c.png

但这样同步的时候无法处理用户请求，但这样影响不大

方案二：合并的时候加锁，合并完之后解锁，广播的时候加锁，广播完解锁

36ac7560f49f222db6a03475cbb699c0.png

会出现旧的数据把新的数据覆盖掉，影响也不大

问题LRU怎样才能实现合并

63bc7ff390a2383ea10d5fa3fd804894.png

维持一个额外的pending list结构,，这个结构记录了自分离之后lru中插入了什么东西，合并的时候只需要把别人的pendinglist插进来就算合并完成了

LRU怎么样实现广播

把主节点内容完全覆盖从节点的内容，然后情况pendinglist

版本4：双缓存机制

问题：还是觉得合并的时候还是有点长，想要让合并的时间尽可能短，减少对业务的影响，如何实现最短加锁时间？

分离 将合并、同步和处理用户请求分离

给线程弄两个缓存，一个缓存用来处理用户的请求，另一个缓存用来做合并、同步的工作

b13d24fc395ae9c4a5b8dcb7b4e98f10.png

用户读写C1,C1‘是cacheManager去同步的

每次同步完c1’就进行一个swap(c1,c1’ )交换两个内存的首地址，代价很小

为什么要自己做一个搜索引擎

27833b07b8a21d40f09ba422932cc87e.png