抖音技术能力大揭密!钜惠大礼、深度体验,尽在火山引擎增长沙龙,就等你来! 立即报名>> 了解详情
写点什么

海量数据搜索

2020 年 2 月 13 日

海量数据搜索

在我们平常的生活工作中,百度、谷歌这些搜索网站已经成为了我们受教解惑的学校,俗话说的好,有问题找度娘。那么百度是如何在海里数据中找到自己需要的数据呢,为什么他搜索的速度如此之快,我们都知道是因为百度的搜索引擎,那么搜索引擎到底是个什么东西呢?可能有的程序员会想到 es,但是并不能代表搜索引擎,它只是其中的一种工具,不过这种工具确实好用,效率很高。


本文会向大家讲述搜索引擎的基本知识以及中文分词的一些方法、然后会做一个小的 demo 去尝试一下数据检索。让大家初步了解搜索引擎的实现


一. 搜索引擎介绍


1. 搜索引擎是什么


这里引用百度百科的介绍:搜索引擎(Search Engine)是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息,在对信息进行组织和处理后,为用户提供检索服务,将用户检索相关的信息展示给用户的系统。


2. 搜索引擎分类


搜索引擎包括全文索引、目录索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、门户搜索引擎与免费链接列表等。


我们这里主要介绍一下全文索引,就是百度使用的搜索引擎分类。


全文索引:


首先是数据库中数据的搜集,搜索引擎的自动信息搜集功能分两种。一种是定期搜索,即每隔一段时间(比如 Google 一般是 28 天),搜索引擎主动派出“蜘蛛”程序,对一定 IP 地址范围内的互联网网站进行检索,一旦发现新的网站,它会自动提取网站的信息和网址加入自己的数据库。另一种是提交网站搜索,即网站拥有者主动向搜索引擎提交网址,它在一定时间内(2 天到数月不等)定向向你的网站派出“蜘蛛”程序,扫描你的网站并将有关信息存入数据库,以备用户查询。


当用户以关键词查找信息时,搜索引擎会在数据库中进行搜寻,如果找到与用户要求内容相符的网站,便采用特殊的算法——通常根据网页中关键词的匹配程度、出现的位置、频次、链接质量——计算出各网页的相关度及排名等级,然后根据关联度高低,按顺序将这些网页链接返回给用户。这种引擎的特点是搜全率比较高。


3.搜索引擎能解决什么问题


1> 高效查询数据(运用多种算法查询数据,查询速率是毫秒级别,无论是千万条数据还是上亿的数据)


2> 比较容易,将普通的数据库切换成搜索引擎比较容易。


3> 大数据量、时效性、高并发等等。


4. 搜索引擎的应用场景:


1> 数据库达到百万数据级别的时候 2> 要求检索时效性、性能要求高,Ms 级响应


我们来看一下在我们平常的互联网中搜索引擎的应用:


Solr


今天我们要讲的搜索引擎是 Solr,那么什么是 Solr 呢?它和 es 相比有什么优点和不足呢?我们先来简单地介绍一下 solr:


Solr 是一个基于 Lucene 的全文搜索服务器。同时对其进行了扩展,提供了比 Lucene 更为丰富的面向使用的查询语言,同时实现了可配置、可扩展并对查询性能进行了优化,并且提供了一个完善的功能管理界面。它支持 Xml/Http 协议,支持 JSONAPI 接口。


它具有如下特点:


  • 可扩展性: Solr 可以把建立索引和查询处理的运算分布到一个集群内的多台服务器上。

  • 快速部署:Solr 是开源软件,安装和配置都很方便,可以根据安装包内的 Sample 配置直接上手,可分为单机和集群模式。

  • 海量数据:Solr 是针对亿级以上的海量数据处理而设计的,可以很好地处理海量数据检索。

  • 优化的搜索功能:Solr 搜索速度够快,对于复杂的搜索查询 Solr 可以做到毫秒级的处理,通常,几十毫秒就能处理完一次复杂查询。


二 .分词介绍


接下来,我们要去了解一下分词是如何实现的,那么,我们为什么要去分词呢,这和搜索引擎有什么关系呢?我们在搜索框里输入的几个词或者一段话是如何拆成多个关键字的呢


大家听说过哪些分词器吗?比如 lucene 自带的中文分词器 smartcn,还有最常用的 IK 分词器等等,今天我们主要讲一下 IK 分词器。


IK 分词器


IK 分词器首先会维护几个词典来记录一些常用的词,如主词表:main2012.dic、量词表 quantifier.dic、停用词 stopword.dic。


Dictionary 为字典管理类中,分别加载了这个词典到内存结构中。具体的字典代码,位于 org.wltea.analyzer.dic.DictSegment。 这个类实现了一个分词器的一个核心数据结构,即 Tire Tree。


Tire Tree(字典树)是一种结构相当简单的树型结构,用于构建词典,通过前缀字符逐一比较对方式,快速查找词,所以有时也称为前缀树。具体的例子如下。


比如:我是北京海淀区中关村的中国人民


我们设置的词典是 北京、海淀区、中关村、中国、中国人民,那么我们根据词典组成的字典树就是这个样子:


1542019641705009817.png


然后我们根据这个字典树来对这段话进行词语切分。IK 分词器中,基本可以分为两种模式:一种是 smart 模式、一种是非 smart 模式,可以在代码中初始化的时候去配置。


我们其实不用解释这两种模式的字面含义,直接打印两种模式的结果就可以看出来:


原句:


我是北京海淀区中关村的中国人民


smart 模式:


北京、海淀区、中关村、中国人民


非 smart 模式:


北京、海淀区、中关村、中国、中国人民


显而易见,非 smart 模式是将能够分出来的词全部输出;smart 模式是根据内在的方法输出一个合理的分词结果,这就涉及到了歧义判断。


举个更有代表性的例子:张三说的确实在理。


根据正向匹配可能的词元链:


L1:{张三,张,三}


L2:{说}


L3:{的确,的,确实,确,实在,实,在理,在,理}


首来看一下最基本的一些元素结构类:


col 1col 2


1


2


3


4


5


6


7


8


9


10


11


12


13


14


15 | public class Lexeme implements Comparable{


``……


``//``词元的起始位移


``private int offset;


``//``词元的相对起始位置


``private int begin;


``//``词元的长度


``private int length;


``//``词元文本


``private String lexemeText;


``//``词元类型


``private int lexemeType;


``……


}


这里的 Lexeme(词元),就可以理解为是一个词语或个单词。其中的 begin,是指其在输入文本中的位置。注意,它是实现 Comparable 的,起始位置靠前的优先,长度较长的优先,这可以用来决定一个词在一条分词结果的词元链中的位置,可以用于得到上面例子中分词结果中的各个词的顺序。


col 1col 2


1


2


3


4


5


6


7


8


9


10


11


12


13


14


15


16


17


18


19


20


21


22 | /*


* 词元在排序集合中的比较算法


* @see java.lang.Comparable#compareTo(java.lang.Object)


*/


public int compareTo(Lexeme other) {


//起始位置优先


``if``(``this``.begin < other.getBegin()){


``return -``1``;


``}``else if``(``this``.begin == other.getBegin()){


``//词元长度优先


``if``(``this``.length > other.getLength()){


``return -``1``;


``}``else if``(``this``.length == other.getLength()){


``return 0``;


``}``else {``//this.length < other.getLength()


``return 1``;


``}


``}``else``{``//this.begin > other.getBegin()


``return 1``;


``}


}


smart 模式歧义消除算法:


词元位置权重比较(词元长度积),含义是选取长的词元位置在后的集合


L31:{的,确实,在理}11+22+3*2=11


L32:{的确,实,在理} 12+21+3*2=10


L33:{的确,实在,理} 12+22+3*1=9


最后的分词结果:张三,说,的,确实,在理


分词我们就讲这么多,大家可以去读一下 IK 分词器的源码,深入地了解一下,源码地址:https://github.com/quentinxxz/Search/tree/master/IKAnalyzer2012FF_hf1_source/


三. 倒排索引算法


1.介绍


我们可以把倒排索引算法想成查字典时的目录一样,我们把需要查的字的目录知道后,就会很快地查到我们需要的字。如果用专业的语言解释的话就是:


倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件,简称倒排文件(inverted file)。


倒排文件(倒排索引),索引对象是文档或者文档集合中的单词等,用来存储这些单词在一个文档或者一组文档中的存储位置,是对文档或者文档集合的一种最常用的索引机制。


搜索引擎的关键步骤就是建立倒排索引,倒排索引一般表示为一个关键词,然后是它的频度(出现的次数),位置(出现在哪一篇文章或网页中,及有关的日期,作者等信息),它相当于为互联网上几千亿页网页做了一个索引,好比一本书的目录、标签一般。读者想看哪一个主题相关的章节,直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页,一页一页的查找。


2. Lucene 倒排索引原理


Lucerne 是一个开放源代码的高性能的基于 java 的全文检索引擎工具包,不是一个完整的全文检索引擎,而是一个全文检索引擎的架构,提供了完整的查询引擎和索引引擎,部分文本分析引擎。目的是为软件开发人员提供一个简单易用的工具包,以方便在目标系统中实现全文检索的功能,或者以此为基础建立起完整的全文检索引擎。


设有两篇文章 1 和 2:


col 1col 2


1


2


3


4 | 文章``1``的内容为:


Jack lives ``in BeiJing,I live ``in BeiJing too.


文章``2``的内容为:


He lived ``in Taiyuan.


1> 取得关键词  


首先我们要用我们之前讲的方式先分词,然后由于英文的原因,我们需要讲 in、on、of 这些没用实际意义的词过滤掉,然后将第三人称单数加 s 或者过去式加 ed 这些的词还原回去,如 lived 变回 live,lives 变回 live,然后把不需要的标点符号也去掉。经过上面的处理之后,剩下的关键字为:


文章 1 的所有关键词为:[Jack] [live] [BeiJing] [i] [live] [BeiJing]


文章 2 的所有关键词为:[he] [live] [Taiyuan]


2>建立倒排索引


col 1col 2


1


2


3


4


5


6


7


8 | 关键词 文章号[出现频率] 出现位置


BeiJing ``1``[``2``] ``3``,``6


he ``2``[``1``] ``1


i ``1``[``1``] ``4


live ``1``[``2``] ``2``,``5``,


``2``[``1``] ``2


Taiyuan ``2``[``1``] ``3


tom ``1``[``1``] ``1


以上就是 lucene 索引结构中最核心的部分。我们注意到关键字是按字符顺序排列的(lucene 没有使用 B 树结构),因此 lucene 可以用二元搜索算法快速定位关键词。


3> 实现


实现时,lucene 将上面三列分别作为词典文件(Term Dictionary)、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词,还保留了指向频率文件和位置文件的指针,通过指针可以找到该关键字的频率信息和位置信息。


4> 压缩算法


为了减小索引文件的大小,Lucene 对索引还使用了压缩技术。


首先,对词典文件中的关键词进行了压缩,关键词压缩为


其次大量用到的是对数字的压缩,数字只保存与上一个值的差值(这样可以减小数字的长度,进而减少保存该数字需要的字节数)。例如当前文章号是 16389(不压缩要用 3 个字节保存),上一文章号是 16382,压缩后保存 7(只用一个字节)。


5> 使用原因


假设要查询单词 “live”,lucene 先对词典二元查找、找到该词,通过指向频率文件的指针读出所有文章号,然后返回结果。词典通常非常小,因而,整个过程的时间是毫秒级的。


而用普通的顺序匹配算法,不建索引,而是对所有文章的内容进行字符串匹配,这个过程将会相当缓慢,当文章数目很大时,时间往往是无法忍受的。


四. solr 基本配置以及使用


这里我们在 windows 系统中安装 solr


下载地址 http://lucene.apache.org/solr/downloads.html


解压后:


1542019660033039985.png


cmd 进入 solr 的 bin 目录,使用命令 solr start(为了更方便,可以配置 solr 的环境变量,配好后可以直接在 cmd 中使用 solr 命名)


1542019671531025846.png


看到这个界面,说明 solr 服务启动成功,端口号为 8983,访问 http://localhost:8983,会自动跳转到 http://localhost:8983/solr/#/


1542019682909047711.png


在这个页面会显示 solr 的基本信息,lucene 信息,Java 信息等


然后我们介绍一个 solr 的指令: solr -h 可以看到 solr 的基本信息


1542019699247082319.png


配置 solr


配置核心 core


 solr create -c mycore -d baisc_configs:-c 参数指定定义的核心名称,-d 参数指定配置目录


1542019711172077307.png


执行该命令后,会多出一个 test 目录。


1542019723726032719.png


访问 Solr Admin 页面:http://localhost:8983/,查看core,多了一个 test


1542019735767081028.png


在\solr-6.3.0\server\solr\test 目录下有 conf 和 data 目录,分别对应配置和数据。


1542019747853091027.png


给 core 添加数据


打开目录:\solr-6.3.0\server\solr\test\conf,添加一个字段:


col 1col 2
1<field name=``"name" type=``"string" indexed=``"false" stored=``"true" required=``"true" multiValued=``"false" />


然后重启 solr: solr restart -p 8983


1542019765614008519.png


到 Solr Admin 页面,选择 core-test-document,在 Document(s)中填写数据:


col 1col 2


1


2


3


4 | {


"id"``:``"1"``,


"name"``:``"宝马"


}


点击 submit,返回 Status: success,则代表添加数据成功。


1542019825522057525.png


多加几条后,点击 Query,查询数据:


1542019882628011656.png


查询界面的 q,代表 查询条件,如输入:name:“宝马”,再次执行查询


1542019872482019218.png


也可以直接 get 方式访问 url:http://localhost:8983/solr/test/select?q=name:宝马


1542019853076048506.png


本文转载自宜信技术学院网站。


原文链接:http://college.creditease.cn/detail/182


2020 年 2 月 13 日 21:46237

评论

发布
暂无评论
发现更多内容

未来法律科技发展现五大趋势,区块链、AI、大数据吸引资本目光

CECBC区块链专委会

5W1H聊开源之Who和How——谁、如何参与开源?

禅道项目管理

开源 开源文化

刷完了这份足足485页的“1000道Java工程师面经”,成功上岸字节

Crud的程序员

Java 程序员 架构 编程语言

字节跳动三面拿offer:网络+IO+redis+JVM+GC+红黑树+数据结构

云流

Java 编程 程序员 架构 面试

iOS面试残篇-辟邪剑谱

程序员 编程之路 移动开发 iOS面试 iOS 知识体系

阿里最新秋招面经,腾讯/美团/字节1千道Java中高级面试题

云流

Java 编程 程序员 架构 面试

41 位 Contributor 参与,1574 个 PR,不容错过的版本更新!

SphereEx

2021-06-25 从简书迁移来到InfoQ首文

林建

解析 Nebula Graph 子图设计及实践

Nebula Graph

数据库 图数据库 子图

数字人民币双层运营架构下缘何衍生出2.5层?看完才明白,原来这么重要!

CECBC区块链专委会

奇亚矿机系统源码,Bzz节点分币系统搭建

13823153121

Java 的函数式接口(必懂知识点!)

Java 白

Java MySQL java程序员 java面试

dubbo 2.7应用级服务发现踩坑小记

捉虫大师

dubbo 服务发现

Wasm合约生态的合约编程实践

Patract

polkadot Patract Wasm智能合约 Near Dfinity

臣卜木曹!火爆全网的这份阿里面试官手册,助多少人拿到了offer

Crud的程序员

Java 架构 编程语言 后端

Github自爆:阿里内部SpringBoot学习笔记,学完直接进大厂

Java架构师迁哥

数仓备机DN重建:快速修复你的数仓DN单点故障

华为云开发者社区

数据仓库 主机 华为云 备机 DN

Windows 11 这项亮点功能源自英特尔Bridge技术支持

新闻科技资讯

性能利器Takin来了!首个生产环境全链路压测平台正式开源

数列科技

高可用 性能测试 开源项目 压力测试

有没有字节工牌,Java并发安全的根本原因都得懂

慕枫技术笔记

Java 高并发

《Spring Framework 系列》- IOC

Geek_896619

ioc Spring Framework

领导说PHP已经过时了,让我滚!!

网络安全学海

php 网络安全 信息安全 渗透测试 安全漏洞

深入C语言中数据的存储

小写丶H

我的新书《C++服务器开发精髓》终于出版啦

张小方

c++ 网络编程 Linux服务器开发 C++后端开发 网路通信

TcaplusDB君 · 行业新闻汇编(6月24日)

TcaplusDB

数据库 nosql tencentdb

6月GitHub上star涨得最多的repo盘点

北游学Java

GitHub

国际禁毒日 | 和TcaplusDB向毒品说不!

数据人er

数据库 nosql tencentdb TcaplusDB

数字化时代,为什么解决信任问题是科技公司最重要的事情?

CECBC区块链专委会

多路三线RTD电阻温度采集电路设计方案

不脱发的程序猿

电路设计 硬件开发 RTD电阻 温度采集电路

网络攻防学习笔记 Day55

穿过生命散发芬芳

网络攻防 6月日更

5G时代,视频会议的未来

anyRTC开发者

音视频 WebRTC 视频会议 音视频开发

Study Go: From Zero to Hero

Study Go: From Zero to Hero

海量数据搜索-InfoQ