# NLP--中文分词处理

**Repository Path**: lxw804/NLP

## Basic Information

- **Project Name**: NLP--中文分词处理
- **Description**: 基于人民日报语料库，实现以下操作：加载语料库进行n-gram词频统计生成词典；用生成的词典生成有意义的语句；对任意输入语句进行正确分词，实现FMM和BMM的分词方法。有GUI界面
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2022-11-16
- **Last Updated**: 2022-11-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# NLP--中文分词处理

#### 介绍
使用语料库，对语句进行分词处理

#### 软件架构
软件架构说明
##### 1．n-gram模型
要做语言模型，基于统计概率来说，我们需要计算句子的概率大小，
也就是最终要求的一句话的概率了，概率大，说明更合理。
因为是不能直接计算，所以我们先应用条件概率得到
中间插入下条件概率：P(B|A)：A 条件下 B 发生的概率。从一个大的空间进入到一个子空间（切片），计算在子空间中的占比。

然而，如果直接算条件概率转化后的式子的话，对每个词要考虑它前面的所有词，这在实际中意义不大，显然并不好算。这个时候可以基于马尔科夫假设来做简化。
马尔科夫假设是指，每个词出现的概率只跟它前面的少数几个词有关。比如，二阶马尔科夫假设只考虑前面两个词，相应的语言模型是三元模型。引入了马尔科夫假设的语言模型，也可以叫做马尔科夫模型。
马尔可夫链（Markov chain）为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。
也就是说，应用了这个假设表明了当前这个词仅仅跟前面几个有限的词相关，因此也就不必追溯到最开始的那个词，这样便可以大幅缩减上述算式的长度。即式子变成了：

然后，我们就可以设置m=1，2，3，....得到相应的一元模型，二元模型，三元模型了：
当 m=1, 一个一元模型（unigram model)即为 ：

当 m=2, 一个二元模型（bigram model)即为 ：

当 m=3, 一个三元模型（trigram model)即为

而N-Gram模型也就是这样，当m=1，叫1-gram或者unigram ；m=2，叫2-gram或者bigram ；当 m=3叫3-gram或者trigram ；当m=N时，就表示的是N-gram。
##### 2．HashMap
HashMap是Java语言中用的最频繁的一种数据结构。

(1)hashmap的数据结构
要了解hashmap首先要弄清楚他的结构。在java编程语言中最基本的数据结构有两种，数组和链表。

数组：查询速度快，可以根据索引查询；但插入和删除比较困难；

链表：查询速度慢，需要遍历整个链表，但插入和删除操作比较容易。

hashmap是数组和链表组成的，数据结构中又叫“链表散列”。

(2)hashmap特点

①　快速存储 ：比如当我们对hashmap进行get和put的时候速度非常快。

②　快速查找（时间复杂度o(1)）当我们通过key去get一个value的时候时间复杂度非常的低，效率非常高。

③　可伸缩：数组扩容，边长。单线列表如果长度超过8的话会变成红黑树。

(3)hashmap的Hash算法
如果使用object对象get hashcode的话会得到要给int类型的指，我们在hashmap中主要是用他的key去计算它的值的。

①　Hash值的计算：
Hash值=（hashcode）^(hashcode >>> 16)
Hashcode予hashcode自己向右位移16位的异或运算。这样可以确保算出来的值足够随机。因为进行hash计算的时候足够分散，以便于计算数组下标的时候算的值足够分散。前面说过hashmap的底层是由数组组成，数组默认大小是16，那么数组下标是怎么计算出来的呢，那就是:
数组下标：hash&(16-1) = hash%16
对哈市计算得到的hash进行16的求余，得到一个16的位数，比如说是1到15之间的一个数，hashmap会与hash值和15进行予运算。这样可以效率会更高。计算机中会容易识别这种向右位移，向左位移。

②　Hash冲突
不同的对象算出来的数组下标是相同的这样就会产生hash冲突。Hash冲突会产生单线链表。当单线链表达到一定长度后效率会非常低。

##### 3．隐马尔可夫模型（HMM）
该模型是一个双重随机过程，我们不知道具体的状态序列，只知道状态转移的概率，即模型的状态转换过程是不可观察的（隐蔽的），而可观察事件的随机过程是隐蔽状态转换过程的随机函数。综合来看，HMM模型在处理庞大的语料库上有很大的优势，它的算法时间复杂度大大降低了。

隐马尔可夫模型是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有相应概率密度分布的状态序列产生。

隐马尔可夫模型（HMM）可以用五个元素来描述，包括 2 个状态集合和 3 个概率矩阵：
 
(1)隐含状态 S 
这些状态之间满足马尔可夫性质，是马尔可夫模型中实际所隐含的状态。这些状态通常无法通过直接观测而得到。（例如 S1、S2、S3 等等) 

(2)可观测状态 O 
在模型中与隐含状态相关联，可通过直接观测而得到。(例如 O1、O2、O3 等等，可观测状态的数目不一定要和隐含状态的数目一致。） 

(3)初始状态概率矩阵 π 
表示隐含状态在初始时刻 t=1 的概率矩阵，(例如 t=1 时，P(S1)=p1、P(S2)=P2、P(S3)=p3，则初始状态概率矩阵 π=[ p1 p2 p3 ]. 

(4)隐含状态转移概率矩阵 A。 
描述了 HMM 模型中各个状态之间的转移概率。 
其中 Aij = P( Sj | Si ),1≤i,,j≤N.表示在 t 时刻、状态为 Si 的条件下，在 t+1 时刻状态是 Sj 的概率。 

(5)观测状态转移概率矩阵 B （英文名为 Confusion Matrix，直译为混淆矩阵不太易于从字面理解）。 
令 N 代表隐含状态数目，M 代表可观测状态数目，则： 
Bij = P( Oi | Sj ), 1≤i≤M,1≤j≤N. 
表示在 t 时刻、隐含状态是 Sj 条件下，观察状态为 Oi 的概率。
总结：一般的，可以用λ=(A,B,π)三元组来简洁的表示一个隐马尔可夫模型。隐马尔可夫模型实际上是标准马尔可夫模型的扩展，添加了可观测状态集合和这些状态与隐含状态之间的概率关系。 
##### 4．前向最长匹配和后向最长匹配
FMM和BMM的编程实现，其实两个算法思路都挺简单，一个是从前取最大词长度的小分句，查找字典是否有该词，若无则分句去掉最后面一个字，再次查找，直至分句变成单词或者在字典中找到，并将其去除，然后重复上述步骤。BMM则是从后取分句，字典中不存在则分句最前去掉一个字，也是重复类似的步骤。

(1)前向最大匹配算法（FMM）是一种基于词典的分词方法，思想很简单就是从左向右扫描寻找词的最大匹配。
正向最大匹配的基本思想:假定分词词典中的最长词有i个汉字字符，则用被处理文档的当前字串中的前i个字作为匹配字段，查找字典。若字典中存在这个的一个i字词，则匹配成功，匹配字段被作为一个词切分出来。如果字典中找不到这样的一个i字词，则匹配失败，将匹配字段中的最后一个字去掉，对剩下的字串重新进行匹配处理。如此进行下去，直到匹配成功，即切分处一个词或剩余字串的长度为零为止。这样就完成了一轮匹配，然后去下一个i字字串进行匹配处理，直到文档被扫描完为止。
其算法描述如下：

①　从左向右取待切分汉语句的m个字符作为匹配字段， m为机器词典中最长词条的字符数。

②　查找机器词典并进行匹配。若匹配成功，则将这个匹配字段作为一个词切分出来。若匹配不成功，则将这个匹配字段的最后一个字去掉，剩下的字符串作为新的匹配字段，进行再次匹配， 重复以上过程，直到切分出所有词为止。
逆向匹配算法大致思路是从右往左开始切分。

(2)逆向最大匹配（BMM）的基本原理与FMM 法相同，不同的是分词切分的方向与FMM 法相反。
逆向最大匹配法从被处理文档的末端开始匹配扫描，每次取最末端的i个字符( i 为词典中最长词数)作为匹配字段，若匹配失败，则去掉匹配字段最前面的一个字，继续匹配。相应地，它使用的分词词典是逆序词典，其中的每个词条都将按逆序方式存放。在实际处理时，先将文档进行倒排处理，生成逆序文挡。然后，根据逆序词典，对逆序文档用正向最大匹配法处理即可。
由于汉语中偏正结构较多， 若从后向前匹配，可以适当提高精确度。所以，逆向最大匹配法比正向最大匹配法的误差要小。


#### 使用说明

使用eclips打开并运行即可

#### 参与贡献

1.  Fork 本仓库
2.  新建 Feat_xxx 分支
3.  提交代码
4.  新建 Pull Request


#### 特技

1.  使用 Readme\_XXX.md 来支持不同的语言，例如 Readme\_en.md, Readme\_zh.md
2.  Gitee 官方博客 [blog.gitee.com](https://blog.gitee.com)
3.  你可以 [https://gitee.com/explore](https://gitee.com/explore) 这个地址来了解 Gitee 上的优秀开源项目
4.  [GVP](https://gitee.com/gvp) 全称是 Gitee 最有价值开源项目，是综合评定出的优秀开源项目
5.  Gitee 官方提供的使用手册 [https://gitee.com/help](https://gitee.com/help)
6.  Gitee 封面人物是一档用来展示 Gitee 会员风采的栏目 [https://gitee.com/gitee-stars/](https://gitee.com/gitee-stars/)