当前位置: 首页>后端>正文

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类

首先需要大致知道搜索引擎有大致几类:1.全文搜索引擎 2.垂直搜索引擎 3.类目搜索引擎等。

1.全文搜索引擎:是全文本覆盖的,百度,google等都是全文本搜索,就是我搜一个词项“方圆”,那么这个词项可以是数字平方的概念,可以是一个人名,可以是一首歌等,所有的相关分类的概念都会被检索到。检索范围是全覆盖的,也就是中间涉及到语义的概念。

2.垂直检索引擎:就是检索一个词项,在一个语义范围内检索,检索范围在一个语义内的。

3.类目检索引擎:一般就是我们所见到互联网公司建设的搜索引擎,比如电商,一个词项检索就是检索自己所有的商品类目,或者汽车之家,就是检索所有的汽车类目。

建设搜索引擎,肯定在数据量上都是海量数据,而且要求数据检索返回速率很快,一般都是秒级返回(通常衡量检索引擎的指标有1.准确率 BM25/TF-IDF 2.召回率)。我们都知道一个数据库的表要是表中的数据几十亿条数据,我们select where 条件具有索引,时间也远不止一秒。所以检索引擎不是单单索引的建立那么简单。而且检索引擎的概念是select *  like;是模糊匹配,不是固定匹配,所以检索更是范围巨大,远不是数据库索引检索那么简单。

搜索引擎在原理上很关键的几点,想到大家也会想到,1.数据结构的设计 2.索引结构的设计 3.数据存储方面的数据压缩机制(压缩之后检索更加高效)。首先我们先了解传统上数据的索引的数据结构B-Tree和B+tree.

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_elasticsearch,第1张

这是B树,但是需要普及一个知识点,不然大家不知道树存储到磁盘,在读取的时候涉及到的IO次数。我们磁盘最小的单元是一个扇区(512B),操作系统最小的读取单位是一簇4KB(8个扇区),那么我们在设置每一个树的节点也最小是4KB(在mysql中数据文件存储是16KB为一页,数据叶是最小存储单位)。那么B树每一个节点也要存储数据,如果数据部分很大,那么每一个节点上存储的分支个数就少了,那么树的深度自然要加大,那么在便利数据的时候,就需要遍历到一定深度的树才会检索到数据。每一次检索一个节点就是要读一个全新的数据叶,就是一次的IO磁盘读;那么这样检索上就需要很多次IO,效率很有限,因此引入了B+树:

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_elasticsearch_02,第2张

B+树呢,每一个节点不存储数据,数据都存储在叶子节点上,而且叶子节点是一个双向的链表进行每一个叶子块链接。这样每一个节点数据块上可以存储的节点 分支就会多达几十,那么树的深度实现大幅度的缩小,遍历起来也非常快。

对于检索引擎,一方面我们肯定把所有的资源信息完整存储,然后根据资源提取所有的“词项”信息,然后搜索引擎会把所有的出现的词项进行存储,词项数据多达千亿级别,词项提出越多,搜索引擎检索准确率也就越高。

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_搜索引擎_03,第3张

 这是基本的词项存储列表,词项在存储的时候,是根据id进行k-v Map形式存储,而且存储也是分布式的,根据id hash计算处对应存储的key,然后知道对应存储的卡槽和卡槽所在的计算机节点(redis和kafka的类似思维的结合)。然后呢,搜索引擎还根据词项字典建立了对应的词项字典索引,加快map块的遍历。上述的词项属性中有一个词项的资源列表的概念,这里是一个倒序排列的出现该词项的所有的资源id的列表(int 列表),为了能很好检索出来词项对应的资源,对应的资源列表信息肯定需要存储的,这是必不可少的存储的数据单元。普通来说资源数据量在千亿级以上,那么出现该词项的条件假如有100万条,那么100万 int列表就是400万B=4MB.千亿级资源至少也有其百倍的词项,就是100*千亿=10w亿,那仅仅词项的倒排资源列表就是巨大的,甚至达到不可有效存储的概念。所以搜索引擎中的压缩算法是必不可少的,根据压缩后的逻辑遍历数据,从而使得检索更快。搜索引擎通常使用的压缩算法有FOR(Frame of Reference),Boaring BitMap算法,至少elasticSearch(lucence引擎)使用该压缩算法。

1.FOR(Frame of Reference)算法,很简单就是对数据列表取差值,存储初始值和所有的差值即可。比如 一列数据,10000,10001,10002,10003...... 1000101;取完差值(第一个值保留原值)列表就是10000,1,1,1,1,1......;我们使用几个bit存储所有的差值即可(这里差值是1),之前存储所有的数据是靠整型存储,现在依靠bit存储差值。实现很好的压缩,对于该类压缩还经常使用到文本信息压缩,尤其全英文的或者全中文文字压缩,因为存储的都是ASCII码,范围在一个区间内(比较紧凑),那记录差值很简单。FOR压缩很紧凑的数据效率很好。

2.Boaring BitMap算法(位图算法),对于非紧凑的数据序列使用FOR压缩就不行了,如1,30,200,400,750,900,1030,... 差值和原值没有大幅度缩小,所以使用BM算法。一个bit列 1000100001...每一个位就是一个bit,每一个位对应的位置号就是1,2,3,4,5,6....;那么在对应的位置上的bit要是1就代表有该序号的数值存在。.........00101010..... 假如这是一列数前面有10000bit位省略了,那么第一个位置代表一万零一,这一串bit代表就是存储了1万零三,1万零五,1万零七三个数据,所以可以见的一串bit的位置是记录的数据大小,所以存储的数据列一定是不可以重复的,不重复的数据这样记录存储可以极大的压缩,要是资源id在几万几十万区间内或者上亿区间内,那么这样就是1百bit存储一百个大小一亿以上的数据(大小:4B*100)数据,同时我们记录设置初始位置记为1亿(就是bit列第一位置就是1亿)100bit=12.5B存储了400B,实现了几百倍上千倍的压缩。

对于关键词(Term)字典结构的存储,采用复用的思想;就是关键词都是由多个字符组成的,(中文是双字节的字符)那么在整个字典结构保存的时候,采用保存一个个的字符,字符之间通过有向的索引来进行串联起来。这就是前缀树结构,Trie-树结构(如下图所示,数字标记的圆就是一个字符节点)。

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_elasticsearch_04,第4张

那为什么采用这个复用的思想呢?直接通过散列映射k-v,hashMap结构把所有的关键词都存储起来,遍历也十分迅速,为什么采用这种复用的结构呢?一般搜索服务里面包含几十亿上百亿的资源,然后后台的服务会将这些资源文件中的文本进行解析,提取其中的关键词(或者关键句),一般一个资源文件中包含的关键词有几十到几百,考虑到关键词的重复,那么所有资源包含的关键词 也有百亿甚至更大的数量级别。那么将这些关键词(关键句)存储起来将是非常大的空间,大致计算下,加入平均每一个关键词是8个字符,那么百亿关键词就是100GB的大小的字典结构(这还是很保守的估算)。如果通过字符共用+有向拼接的思想,实现这个结构千倍、万倍的压缩,那么直接可以将这个字典结构放在内存中,那么就不需要每次检索去IO文件,性能表现也完全不一样。

为了实现前缀复用树(字典)结构能根据有向链接输出想要查询的Term(关键词),需要标记具体节点的状态,例如是不是某一个要查询的Term最后一个字符,某一个节点有几个输出的子节点、子结点个数、是否是最后的子节点(子节点的个数记为某一个节点的出度,有些文章把输出子节点直接叫成出度,这纯属概念混淆)等。既然节点有状态,且通过有向链接,那么就是有限状态机的概念(Finit state Machine  FSM)。如下图:

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_大数据_05,第5张

由此可见有限有序状态机其实是一个图结构,只是每一个节点有标记状态的数据。那么存储Term(关键词)字典结构肯定也是一个有向图结构,而且还是节点状态标记的图结构。只是每一次节点存储的是字符和节点状态等信息,而且Term存储结构还加入了起始点和终止节点,目的就是在遍历的时候单向有限,而且要求尽量去复用节点,这就是FSA(Finit state Accepter 有限状态接收器)的概念。如下图:

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_elasticsearch_06,第6张

上图中0是起始节点,7是终止节点 ;而且在有向路线上尽量复用节点。那么如何实现复用呢?这是最为核心的算法,也是关键词存储和检索的核心算法。很多博客上或者视频讲解中只是提到FSA具备线路输出值(或者权重)特征,有点类似哈夫曼树(也叫霍夫曼),尽量使得所有线路的权重值求和结果最小,而且一般要求FSA中相同的始末节点线路输出值是一致的(heap和area中a->e的线路输出值一致)。那么在所有字典节点确认好了之后,来检查线路输出值,相同的要进行合并,这样就容易达到公用线路的算法。如下图:

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_搜索引擎_07,第7张

线路遍历之后,合并线路:

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_elasticsearch_08,第8张

在FSA的建立之后,我们还需要对term存储的字典结构中存储每一个term的value,term字符串就是key,还需要像hashmap那样存储对应的value.所以我们又创造了每一个term结束字符节点的时候输出一个value,记为outputValue.这就是FST finit state transsioner.对于一系列的term,需要构造FST结构存储,事先就确定了每一个term的value,构建FST数据结构的一系列算法的集合 叫做FST构造器。构造器的构造过程如下:

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_垂直搜索引擎名称有哪些类型_09,第9张

所有的关键词term字符节点都被放置在一个叫做frontier的列表里面,去构建FST的时候,首先创造uncomplied[] 存储即将构建的term的字符,然后创建一个初始节点entry,然后 依次从uncomplied[](也叫做current[])中获取每一个term的起始节点,然后按照每一个term将其他的节点依次挂进去,并记为pendingEntry。如果一个节点挂载的pendingEntry较多的时候,就会合并在一起形成pendingblock,并将该队列中最后一个entry的线路值作为pendingblock的线路值。如果形成的pendingblock持续增长,长度达到一个条件,就会转换成两个floorblock挂载在该block下面,形成层级结构,每一个floorblock的第一个entry节点的线路值作为floorblock的线路输出值。这样就形成了组织架构,这样也是为了方便将term的字典树结构搭建起来,然后所有的term节点挂载完成之后,然后根据term最后的节点来链接到终止节点,接着根据终止节点来倒着扫描末尾节点的状态和输出线路值。逐个的将floorblock和pendingblock中的entry逐个的确定和隔离开来,形成确定的节点参数信息和线路值。

Arc:描述FST构建的重要类型,其中我们要着重理解的包括label、output、target和flags四个属性,其他属性我这里都已经做了详细的中文注释,这里我们来把刚才说的四个属性重点讲解一下。

label:描述当前输入词项中的一个字符,FST最终存储的是label对应字符的ASCLL的二进制。

output:存储Arc对象的附加值或者叫做输出值,output和finalOutput都属于output。

target:如果当前的祖父不是输入值的最后一个字符,target会存储当前字符的下一个字符在current数组中的flag值在current数组中的index即索引值。

flags:通用最小化算法要求任何对数据的压缩都要可以逆向运算,即数据可编码解码,因此在对于FST进行压缩的时候,flags的作用是以最小的代价标记若干个状态值,这里采用了一种位移算法,以实现其通用最小化的目的。这里label和output都很容易理解,但是target和flags相对难以理解。target的含义我们在FST的写入过程中给大家做详细介绍,但是这flags的含义我们有必要在这里展开来详细的讲解一下。

lastFrozenNode:当节点从frontier[]数组中摘下来的时候,节点和它包含的Arcs信息会被写入到current[]数组中,lastFrozenNode会记录当前被处理的节点的第一个Arc在current数组中的起始坐标,即flag的坐标。如果当前节点是终止节点,因为终止节点没有出度Arc,因此lastFrozenNode会输出-1。当lastFrozenNode的值和当前处理的Arc指向的target node在current数组的起始坐标不相同并且当前处理的Arc的target node不是Stop node(因为没有出度Arc)的时候,也就意味着最终构建的FST对象存储的current[]数组在读取的时候,当前Arc对应的label在数组中的下一个Arc不是当前term的下一个label,就需要记录当前Arc的下一个Arc在current数组中的坐标,此时flag就不会标记BIT_TARGET_NEXT值。

把该末尾节点输出线路值记为一个合理的数值out1,该term对应的数值是value,往前所有的线路输出值总和为value-out1;如果out1值被之前扫描到的term线路已经赋值了,那么:1.如果out1<=value;则其向前线路和为value-out1; 2.如果out1>value;则令out1=value;记temp=out1-value;temp的数值可能需要被其他term向前的其他线路作为补偿值,且该term向前的线路暂不输出值(不输出值标记为0)。这样倒向逐个确定节点的线路输出值,然后最后相同的线路进行扫描合并,确定每一个节点的出度和状态参数信息,从而达到固化的目的。然后再倒序扫描固化的节点,执行freezeTail加固话的节点信息存储到compiled array数组中,依次从数组的最前面开始放置。这样放置完成之后,发现数组最后的位置存储的term字典树的开始位置节点信息,类似一个栈结构;这也是为什么叫做倒排索引的原因

flags在FST结构读取的时候起着关键作用,flags是有几种有限的固定值的。

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_大数据_10,第10张

flags是这几种状态值的和,1,2,4,8,16,32者六种数值的几种组合,所以我们可以很轻松从flag的数值推断出来是哪几种状态值的累加。根据flag,我们在读取的时候很容易知道该节点在FST中的状态和位置。 

按照网上给的一个例子,图中红框内是term和对应的value数值,也就是k-v列表信息:

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_大数据_11,第11张

然后图中左边部分是要计算每一个节点的flags,和右边确定的FST节点的拓扑结构信息,可以动手大家画一下,很容易就可以画出来的。下面是输出的最终FST数组结构:

垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类,垂直搜索引擎名称有哪些类型 垂直引擎搜索三大类_elasticsearch_12,第12张


https://www.xamrdz.com/backend/3zz1931624.html

相关文章: