一、泛论

作业日子中，查找引擎是咱们必不可少的东西，它能帮咱们快速的从全世界百亿级的海量网页和文档中快速查询到咱们需求的内容。本文首要解说查找引擎的检索原理，通过原理的共享，信任咱们就能很简单的理解为什么查找引擎能这么快了。
全球最大的中文查找引擎-百度
首要先介绍一下咱们日子中的数据类型：结构化数据和非结构化数据。
结构化数据：指具有固定格局或有限长度的数据，如数据库，元数据等。非结构化和半结构化数据：指不定长或无固定格局的数据，如邮件，word文档等。半结构化数据，如XML，HTML等。
依照数据的分类，查找也分为两种：
对结构化数据的查找：如对数据库的查找，用SQL句子。再如对元数据的查找，如运用windows查找对文件名，类型，修正时刻进行查找等。对非结构化数据的查找：如运用windows的查找也能够查找文件内容，Linux下的grep指令，再如用Google和百度能够查找很多内容数据。
对非结构化数据也即对全文数据的查找首要有两种办法：
一种是次序扫描法(Serial Scanning)：所谓次序扫描，比方要找内容包括某一个字符串的文件，就是一个文档一个文档的看，关于每一个文档，从头看到尾，假如此文档包括此字符串，则此文档为咱们要找的文件，接着看下一个文件，直到扫描完一切的文件。如运用windows的查找也能够查找文件内容，只是适当的慢。假如你有一个80G硬盘，假如想在上面找到一个内容包括某字符串的文件，不花他几个小时，怕是做不到。Linux下的grep指令也是这一种办法。咱们或许觉得这种办法比较原始，但关于小数据量的文件，这种办法仍是最直接，最便利的。可是关于很多的文件，这种办法就很慢了。
有人或许会说，对非结构化数据次序扫描很慢，对结构化数据的查找却相对较快（因为结构化数据有必定的结构能够采纳必定的查找算法加速速度），那么把咱们的非结构化数据想办法弄得有必定结构不就行了吗？
这种主意很天然，却构成了全文检索的基本思路，也行将非结构化数据中的一部分信息提取出来，重新组织，使其变得有必定结构，然后对此有必定结构的数据进行查找，然后到达查找相对较快的意图。
这部分从非结构化数据中提取出的然后重新组织的信息，咱们称之索引。
这种说法比较笼统，举几个比方就很简单理解，比方字典，字典的拼音表和部首检字表就适当于字典的索引，对每一个字的解说对错结构化的，假如字典没有音节表和部首检字表，在苍茫辞海中找一个字只能次序扫描。可是字的某些信息能够提取出来进行结构化处理，比方读音，就比较结构化，分声母和韵母，别离只要几种能够一一列举，所以将读音拿出来按必定的次序排列，每一项读音都指向此字的具体解说的页数。咱们查找时按结构化的拼音搜到读音，然后按其指向的页数，便可找到咱们的非结构化数据——也即对字的解说。
这种先树立索引，再对索引进行查找的进程就叫全文检索(Full-text Search)。
二、索引里边终究存些什么
索引里边终究需求存些什么呢？（咱们以JAVA开源的全文检索系统Lucene为例）。
Apache开源查找引擎项目Lucene与Solr
首要咱们来看为什么次序扫描的速度慢：
其实是因为咱们想要查找的信息和非结构化数据中所存储的信息不共同形成的。
非结构化数据中所存储的信息是每个文件包括哪些字符串，也即已知文件，欲求字符串相对简单，也就是从文件到字符串的映射。而咱们想查找的信息是哪些文件包括此字符串，也即已知字符串，欲求文件，也即从字符串到文件的映射。两者恰恰相反。所以假如索引总能够保存从字符串到文件的映射，则会大大提高查找速度。
因为从字符串到文件的映射是文件到字符串映射的反向进程，所以保存这种信息的索引称为反向索引。
反向索引的所保存的信息一般如下：
假定我的文档调集里边有100篇文档(网页也能够看作是一篇文档)，为了便利表明，咱们为文档编号从1到100，得到下面的结构
倒排索引
左面保存的是一系列字符串，称为词典。
每个字符串都指向包括此字符串的文档(Document)链表，此文档链表称为倒排表(Posting List)。
有了索引，便使保存的信息和要查找的信息共同，能够大大加速查找的速度。
比方说，咱们要寻觅既包括字符串“lucene”又包括字符串“solr”的文档，咱们只需求以下几步：
1. 取出包括字符串“lucene”的文档链表。
2. 取出包括字符串“solr”的文档链表。
3. 通过兼并链表，找出既包括“lucene”又包括“solr”的文件。

看到这个当地，有人或许会说，全文检索确实加速了查找的速度，可是多了索引的进程，两者加起来不用定比次序扫描快多少。确实，加上索引的进程，全文检索不用定比次序扫描快，尤其是在数据量小的时分更是如此。而对一个很很多的数据创立索引也是一个很慢的进程。
可是两者仍是有差异的，次序扫描是每次都要扫描，而创立索引的进程只是需求一次，今后就是一了百了的了，每次查找，创立索引的进程不用通过，只是查找创立好的索引就能够了。
这也是全文查找相关于次序扫描的优势之一：一次索引，屡次运用。
Lucene索引以及查找进程
当每次用户想要查找相关的网页或文档信息时，咱们都能够运用之前创立好的索引，快速的查询出相关信息。这就是查找引擎能从海量数据中快速地为用户找到信息的窍门了。

转载请注明出处。