百亿级数据搜索引擎，Lucene，其当中的分词原理究竟是怎样的？

前情提要

关于搜索引擎的知识，在这里是连载的文章，大家观看文章，如果看不懂或者不理解，一方面的话可以在留言区进行技术留言，我将和大家一起探讨相关技术点；另一方面则是关注相关的Lucene专题，后续会慢慢，循序渐进的帮助大家解读相关的技术点！

Lucene有关java的sdk依赖包

上篇文章中没有给大家放Lucene有关java开发的依赖包，这里给大家补充上去，大家选取可以按照原理自行练习。由于Lucene不需要安装，应用起来也是比较简单的！

<properties>
  <java.version>1.8</java.version>   <!--规定最低jdk版本1.8-->
  <lucene.version>7.7.0</lucene.version><!--本次Lucene选取7.7.0的依赖-->
</properties>

<dependencies>
  <dependency>
    <groupId>org.apache.lucene</groupId>
    <artifactId>lucene-core</artifactId>
    <version>${lucene.version}</version>
  </dependency>
  <dependency>
    <groupId>org.apache.lucene</groupId>
    <artifactId>lucene-analyzers-common</artifactId>
    <version>${lucene.version}</version>
  </dependency>
  <dependency>
    <groupId>org.apache.lucene</groupId>
    <artifactId>lucene-queries</artifactId>
    <version>${lucene.version}</version>
  </dependency>
  <dependency>
    <groupId>org.apache.lucene</groupId>
    <artifactId>lucene-queryparser</artifactId>
    <version>${lucene.version}</version>
  </dependency>
  <dependency>
    <groupId>org.apache.lucene</groupId>
    <artifactId>lucene-analyzers-smartcn</artifactId>
    <version>${lucene.version}</version>
  </dependency>

  <dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-test</artifactId>
    <scope>test</scope>
  </dependency>
</dependencies>

今天和大家主要研究Lucene的分词相关的知识点以及原理！

分词算法概述

词是表达语言的最小单位。分词对搜索引擎很重要，可以帮助搜索引擎自动识别语句含义，使搜索结果匹配度达到最高，因此分词质量的好坏也就影响了搜索结果的精度。利用分词器，把短语或者句子切分成分词，才能保证搜索的质量和结果。

英文分词原理
基本流程：输入文本、词汇分割、词汇过滤（去Stop Word）、词干提取（形态还原）、大写转换，输出结果。

中文分词原理
中文分词比较复杂，因为中文句子中没有像英文中天然的空格来分隔。所以，中文分词主要有3种方法：
1.基于词典匹配
2.基于词频统计
3.基于词频统计

基于词典统计

该算法实际上就是把一个句子从左向右扫描一遍，遇见字典中有的词就标记出来，遇到复合词就找到最长的词匹配，遇到不认识的词就切分城单个词。按照匹配扫描方向不同，又分为：
1.正向最大匹配
2.逆向最大匹配
3.最少切分
真正实用的分词系统，都会把字典作为基础手段，再结合该语言自身的其他特征来提高切分的质量和精度。

基于词频统计

该算法的原理是：在中文文章中，相邻的字搭配出现的频率越高，就越有可能形成一个固定的词。根据两个字的统计信息，计算两个汉字的相邻共现概率，统计出来的结果体现汉字之间的紧密程度，当紧密程度高于某个阈值，便可认为该组合可能构成一个词。
基于词频统计的分词方法只需要对语料中的汉字组合频度进行统计，不需要词典，因此又叫做无词典分词或者统计分词法。

基于语义理解

基于语义理解的分词是模拟人脑对语言和句子的理解，达到识别句子的效果。

Trie树（字典树）

Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。它是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。

Lucene分词器

索引和查询都是以词为基本单词。在Lucene中分词主要依靠Analyzer类解析实现。Analyzer内部主要通过TokenStream来实现，Tokenizer和TokenFilter是Tokan的两个子类。Tokenizer处理单个字符组成的字符流，读取Reader对象中的数据，处理后转换城词元。TokenFilter完成文本过滤功能。
StopAnalyzer
停用词分词器。过滤词汇中的特定字符串和词汇，并完成大写转小写的功能。
StandardAnalyzer
根据空格和符号来完成分词，还可以完成数字、字母、Email地址、IP地址及中文字符的分析处理，还可以支持过滤词表，用来替代StopAnalyzer的过滤功能。
WhitespaceAnalyzer
使用空格作为间隔的分割分词器。处理时，以空格作为分隔符号。分词器不做词汇过滤，也不进行大小写字符转换，主要用来特定环境下的英文符号处理。不需要字典支持。
SimpleAnalyzer
处理时，以非字母字符作为分隔符号。分词器不做词汇过滤，值进行分析和分割。输出的结果完成大小写转换，去标点符号。不支持中文。不需要字典支持。
CJKAnalyzer
内部调用CJKTokenizer分词器，对中文进行分词，同时使用StopFilter完成过滤。
KeywordAnalyzer
把整个输入作为一个单独次元，方便特殊文本索引和搜索。主要针对ZipCode、Address等表示特定语义的信息。

中文分词器

SmartChineseAnalyzer
运用概率知识，对中英文混合的文本进行分词操作，先将文本进行分句，再分别对每句话进行分词。这个分词器是基于隐马尔科夫模型而设计的，并使用了大量的语料进行中文词频的统计，同时包含了来自 ICTCLAS1.0的统计数据作为词典。

IKAnalayzer

[IKAnalayzer adress:]{https://github.com/blueshen/ik-analyzer/tree/master}
相关java api依赖

<dependency>
  <groupId>org.wltea.ik-analyzer</groupId>
  <artifactId>ik-analyzer</artifactId>
  <version>7.5.0</version>
</dependency>

分词算法知识扩展

NLP的底层任务由易到难大致可以分为词法分析、句法分析和语义分析。分词是词法分析（还包括词性标注和命名实体识别）中最基本的任务，可以说既简单又复杂。分词算法根据其核心思想主要分为两种：
1.基于词典的分词，先把句子按照字典切分成词，再寻找词的最佳组合方式
2.基于字的分词，即由字构词，先把句子分成一个个字，再将字组合成词，寻找最优的切分策略，同时也可以转化成序列标注问题。
归根结底，上述两种方法都可以归结为在图或者概率图上寻找最短路径的问题。

基于词典的分词

最大匹配分词算法

最大匹配分词寻找最优组合的方式是将匹配到的最长词组合在一起。主要的思路是先将词典构造成一棵Trie树，也称为字典树

最短路径分词算法

最短路径分词算法首先将一句话中的所有词匹配出来，构成词图（有向无环图DAG），之后寻找从起始点到终点的最短路径作为最佳组合方式。

最短路径算法

基于Dijkstra算法求解最短路径。该算法适用于所有带权有向图，求解源节点到其他所有节点的最短路径，并可以求得全局最优解。Dijkstra本质为贪心算法，在每一步走到当前路径最短的节点，递推地更新原节点到其他节点的距离。

N-最短路径算法

N-最短路径分词是对Dijkstra算法的扩展，在每一步保存最短的N条路径，并记录这些路径上当前节点的前驱，在最后求得最优解时回溯得到最短路径。该方法的准确率优于Dijkstra算法，但在时间和空间复杂度上都更大。

基于字的分词

与基于词典的分词不同的是，基于字的分词事先不对句子进行词的匹配，而是将分词看成序列标注问题，把一个字标记成B(Begin), I(Inside), O(Outside), E(End), S(Single)。因此也可以看成是每个字的分类问题，输入为每个字及其前后字所构成的特征，输出为分类标记。对于分类问题，可以用统计机器学习或神经网络的方法求解。

生成式模型算法

生成式模型主要有NGram模型、HMM隐马尔可夫模型、朴素贝叶斯分类等。在分词中应用比较多的是n-gram模型和HMM模型。

判别式模型算法

判别式模型主要有感知机、SVM支持向量机、CRF条件随机场、最大熵模型等。在分词中常用的有感知机模型和CRF模型。

神经网络算法

在NLP中，最常用的神经网络为循环神经网络（RNN，Recurrent Neural Network），它在处理变长输入和序列输入问题中有着巨大的优势。LSTM为RNN变种的一种，在一定程度上解决了RNN在训练过程中梯度消失和梯度爆炸的问题。
至此，有关Lucene的分词相关的算法大概给大家介绍完了，由于算法当中涉及到机器学习的东西，在此没法和大家分享了，但是针对于Lucene的有关搜索引擎原理知识以及API层的应用会和大家一起分享！