前言继上一篇博客介绍whoosh搜索引擎后，打算写一个系列文章《从零开始写自己的搜索引擎》，但是想来想去，还是先写一篇介绍一下原理比较好，然后再从头再来，才有了这篇文章。我们生活中有两种类型的数据：结构化数据和非结构化数据。结构化数据：指格式固定或长度有限的数据，如数据库、元数据等非结构化数据：指长度可变或格式不固定的数据，如电子邮件、word文档等非结构化数据的别称是全文数据。根据数据的分类，搜索也分为两种类型：搜索结构化数据：比如搜索数据库，使用SQL语句。再比如元数据的搜索，比如用windows搜索文件名、类型、修改时间等。搜索非结构化数据：例如可以使用Windows搜索文件内容，Linux下使用grep命令，使用Google、百度搜索大量内容数据。非结构化数据即全文数据的检索方法主要有两种：一种是串行扫描法（SerialScanning）：所谓顺序扫描，例如查找包含某个字符串的文件，是一种documentandadocument看，对于每一个文档，从头到尾，如果这个文档包含这个字符串，那么这个文档就是我们要找的文件，然后再看下一个文件，直到扫描完所有的文件。例如，您也可以使用Windows搜索来搜索文件内容，但速度很慢。如果有一个80G的硬盘，如果要在上面查找包含某个字符串的文件，可能需要几个小时。Linux下的grep命令也是这样。这是一种比较原始的方法，但是对于数据量不大的文件，这种方法是最直接方便的。但是对于大量的文件，这种方法很慢。另一种是全文搜索（Full-textSearch）：即先建立索引，再搜索索引。索引是从非结构化数据中提取和重组的信息。全文搜索引擎的基本实现原理下图来自《Lucene in action》，但它不仅仅描述了Lucene和全文搜索引擎的大致流程。全文检索一般分为两个过程，索引创建（Indexing）和搜索索引（Search）。索引创建：从现实世界中所有结构化和非结构化数据中提取信息并创建索引的过程。搜索索引：是获取用户的查询请求，搜索创建的索引，然后返回结果的过程。索引创建全文检索的索引创建过程一般有以下几个步骤：第一步：一些待索引的原始文档（Document）。为便于描述索引创建过程，这里以两个文件为例：文件1：允许学生与朋友外出，但不允许喝啤酒。档案2：我的朋友Jerry去学校看望他的学生，但发现他们喝醉了，这是不允许的。第2步：将原始文档传递给Tokenizer。分词组件（Tokenizer）会做以下事情（这个过程称为Tokenize）：将文档分成单独的单词。去掉标点符号。去除停用词（Stopword）。所谓的停用词是一种语言中最常见的一些词。由于它们没有特殊含义，因此在大多数情况下不能用作搜索关键字。因此，在创建索引时，会去除此类词以减少索引。的大小。在英语中，停用词（Stopword）如：“the”、“a”、“this”等。对于每种语言的分词器，都有一组停用词。标记化（Tokenizer）后得到的结果称为标记（Token）。在我们的示例中，获取了以下标记：“Students”、“allowed”、“go”、“their”、“friends”、“allowed”、“drink”、“beer”、“My”、“friend”、“Jerry”、“went”、“school”、“see”、“his”、“students”、“found”、“them”、“drunk”、“allowed”。第三步：将获得的令牌（Token）传递给语言处理组件（LinguisticProcessor）。语言处理组件（linguisticprocessor）主要是对得到的令牌（Token）进行一些与语言相关的处理。对于英语，语言处理组件（LinguisticProcessor）一般会做以下事情：转为小写（Lowercase）。将单词缩减为词根形式，例如“cars”缩减为“car”等。这种操作称为：词干提取。将单词转换为词根形式，如“drove”转换为“drive”等。这种操作称为：词形还原。Stemming和lemmatization的相同点和不同点：两种方式不同：Stemming采用了一种“归约”的方式：“cars”到“car”，“driving”到“drive”。词形还原采用“转化”的方法：“驱”到“驱”，“驱”到“驱”。两者的算法不同：Stemming主要是采用某种固定的算法来做这个归约，比如去掉“s”，去掉“ing”加“e”，把“national”改成“ate”，把“tional”改成”变成“重”。词形还原主要是利用保存某种字典的方法来进行这种变换。例如，字典中有“driving”到“drive”、“drive”到“drive”、“am,is,are”到“be”的映射。修改的时候，只需要查字典就可以了。Stemming和Lemmatization不是相互排斥的，而是重叠的，有些词使用这两种方法可以实现相同的转换。语言处理组件（语言处理器）的结果称为词（Term）。在我们的例子中，经过语言处理后，得到的词（Term）如下：“student”、“allow”、“go”、“their”、“friend”、“allow”、“drink”、“beer”、“我的”、“朋友”、“杰瑞”、“去”、“学校”、“见”、“他的”、“学生”、“找到”、“他们”、“喝”、“允许”。正是因为有了语言处理步骤，搜索驱动器和驱动器也可以被搜索出来。查询索引当用户输入关键字进行搜索时，搜索引擎在索引中寻找匹配的索引，并通过索引找到原始文档。这就是查询索引的过程，但这还没有结束。您认为找到原始文件就可以了吗？？不，如果只有一个或十个文档包含我们的查询字符串，我们确实会找到它。但是如果结果有上千个，甚至上万个怎么办？您最想要的文件是哪个？这时候就需要根据打分算法计算出每个结果的权重，排序后展示给用户。查询索引一般要经过四个步骤：用户输入查询语句并对查询语句进行词法分析（识别词和关键词）、语法分析（根据查询语句的语法规则形成语法树）、语言处理（对原语言进一步处理）搜索索引得到符合语法树的文档根据得到的文档与查询语句的相关性，结果对词（Terms）之间的关系进行排序和判断的过程得到documentrelevance应用了一种叫做向量空间模型（VectorSpaceModel）的算法**下面仔细分析了两个过程：1.计算权重（Termweight）的过程。影响一个词（Term）在一篇文档中的重要性的因素主要有两个：TermFrequency（tf）：即这个Term在这篇文档中出现了多少次。tf越大，越重要。文档频率(df)：有多少文档包含此术语。df越大，它越不重要。容易理解吗？一个词（Term）在文档中出现的次数越多，该词（Term）对文档的重要性就越大。比如“搜索”这个词在这篇文档中出现的比较多，说明这篇文档主要是讲这方面的。但是，在一份英文文档中，如果这个出现的次数多了，是不是就代表它更重要呢？不，这是由第二个因素调整的。第二个因素说明包含这个词（Term）的文档越多，这个词（Term）就越常见，不足以区分这些文档，所以它越重要Low。这也好比我们程序员学的技术。对于程序员本身来说，对这门技术的掌握越深越好（掌握越深，阅读的时间越多，tf越大），找工作的时候也越有竞争力。但是，对于所有的程序员来说，知道这门技术的人越少越好（知道的人越少，df越小），找工作的竞争力就越大。人的价值在于其不可替代性。道理很清楚了，我们来看一下公式：这只是一个简单典型的术语权重计算公式的实现。不同的全文检索系统会有不同的实现，Lucene与此略有不同。2、通过判断词条之间的关系来获得文档相关性的过程，即向量空间模型（VSM）的算法。我们把一篇文档看成是一系列的词条（Term），每个词条（Term）都有一个权重（Termweight）。不同的词条（Term）根据其在文档中的权重影响文档相关性的评分计算。所以我们把这篇文档中所有词条（term）的权重（termweight）看成一个向量。Document={term1,term2,...,termN}DocumentVector={weight1,weight2,...,weightN}同理，我们把查询语句看成一个简单的文档，同样用一个向量表示。Query={term1,term2,...,termN}QueryVector={weight1,weight2,...,weightN}我们把所有搜索到的文档向量和query向量放到一个N维空间中，每个词（术语）是一维的。如图：我们认为两个向量夹角越小，相关性越大。因此，我们计算夹角的余弦值作为相关分数。夹角越小，余弦值越大，得分越高，相关性越大。有人会问，查询语句一般很短，包含的词（Term）很少，所以查询向量的维数很小，而文档很长，包含的词（Term）很多，文档向量的维数非常大。大的。为什么你的图中两个维度都是N？这里，由于它们要放在同一个向量空间中，自然维度是相同的。如果它们不同，则采用两者的并集。如果不包含某个词项（Term），则权重（TermWeight）为0。关联评分公式如下：例如查询语句有11个词项，一共搜索了3篇文档。各自的权重（Termweight）如下表所示。t1t2t3t4t5t6t7t8t9t10t11D100.4770.477.176000.1760D20.1760.4770000.9540.176D30.176000.176000.176.176Q00000.17600.4770.176于是计算，三篇文档同查询语句的相关性打分分别为：于是文档二相关性最高，先返回，其次是文档一，最后记录三。至此，我们就可以找到我们最想要的文件了。Lucene简单介绍索引创建和搜索过程索引过程：1)有一系列的索引文件2)对索引文件进行解析和语言处理，形成一系列的词（Term）。3）通过索引创建创建字典和反向索引表。4)通过索引存储将索引写入硬盘。搜索过程：a)用户输入查询语句。b)对查询语句进行语法分析和语言分析，得到一系列词（Term）。c)通过语法分析得到查询树。d)通过索引存储将索引读入内存。e)使用查询树搜索索引得到每个term(Term)的文档链表，对文档链表求交差，得到结果文档。f)对搜索结果文档与查询的相关性进行排序。g)将查询结果返回给用户。索引为了对文档进行索引，Lucene提供了五个基本类，它们是Document、Field、IndexWriter、Analyzer、Directory。下面分别介绍一下这五个类的用途：DocumentDocument用于描述文档，这里的文档可以指HTML页面、邮件或者文本文件。一个Document对象由多个Field对象组成。一个Document对象可以被认为是数据库中的一条记录，每个Field对象就是该记录的一个字段。FieldField对象用于描述文档的一个属性，例如一封电子邮件的标题和内容可以由两个Field对象来描述。在对文档进行索引之前，Analyzer首先需要对文档的内容进行切分，这部分工作由Analyzer完成。Analyzer类是一个具有多个实现的抽象类。为不同的语言和应用选择合适的Analyzer。Analyzer将分词后的内容发送给IndexWriter建立索引。IndexWriterIndexWriter是Lucene用来创建索引的核心类。它的作用是将每个Document对象添加到索引中。Directory类表示Lucene的索引的存储位置。这是一个抽象类。它目前有两个实现。第一个是FSDirectory，它表示存储在文件系统中的索引的位置。第二个是RAMDirectory，它表示索引在内存中存储的位置。搜索文档使用Lucene进行搜索就像建立索引一样简单。在上面的部分中，我们已经为目录中的文本文档创建了一个索引，现在我们需要在这个索引上进行搜索，以找到包含某个关键字或词组的文档。Lucene提供了几个基本类来完成这个过程，它们是IndexSearcher、Term、Query、TermQuery、Hits。下面我们分别介绍这几个类的作用。Query是一个抽象类，有多种实现，如TermQuery、BooleanQuery、PrefixQuery。该类的作用是将用户输入的query字符串封装成Lucene可以识别的Query。TermTerm是搜索的基本单位，一个Term对象由两个String类型的字段组成。可以使用以下语句生成Term对象：Termterm=newTerm(“fieldName”,”queryWord”);第一个参数表示要搜索文档的哪个Field，第二个参数表示要搜索的Keywords。TermQueryTermQuery是抽象类Query的子类，也是Lucene支持的最基本的查询类。生成TermQuery对象是通过以下语句完成的：TermQuerytermQuery=newTermQuery(newTerm(“fieldName”,”queryWord”));它的构造函数只接受一个参数，就是一个Term对象。IndexSearcherIndexSearcher用于在已建立的索引上进行搜索。它只能以只读模式打开一个索引，因此可以有多个IndexSearcher实例对一个索引进行操作。HitHits用于保存搜索结果。欢迎和我交流玩码直播间：https://live.bilibili.com/11883038微信公众号：DealiAxy知乎：https://www.zhihu.com/people/dealiaxy博客：https://blog.Deali.cn简书：https://www.jianshu.com/u/965b95853b9f
