数据结构与算法-21算法专项（中文分词)（END）

中文分词

搜索引擎是如何理解我们的搜索语句的？

mysql中使用【like “%中国%”】，这样的使用方案

缺点1：mysql索引会失效
缺点2：不能模糊，比如我搜湖南省就搜不到湖南相关的

1 trie树

Trie树，又称前缀树、字典树或单词查找树，是一种树形结构，用于快速检索字符串数据集中的键。Trie树的核心思想是利用字符串的公共前缀来降低查询时间的开销。在Trie树中，每个节点都代表一个字符串中的某个前缀，从根节点到某一节点的路径上的所有字符连接起来，就是该节点对应的字符串。Trie树中不存在值域，其值就隐含在树的路径中。

Trie树的基本性质包括：

根节点不包含字符，除根节点外每个节点都包含一个字符。
从根节点到某一节点路径上经过的字符连接起来，就是该节点对应的字符串。
每个节点的子节点包含的字符都不相同。

在这里插入图片描述

2 示例


package cn.zxc.demo.leetcode_demo.search_algoritm;class TrieNode {// 指向子节点的指针数组，假设只包含小写字母TrieNode[] children = new TrieNode[26];// 标记该节点是否是一个单词的结尾boolean isEndOfWord;public TrieNode() {isEndOfWord = false;for (int i = 0; i < 26; i++) {children[i] = null;}}
}public class Trie {private TrieNode root;public Trie() {root = new TrieNode();}// 插入一个单词到Trie中public void insert(String word) {TrieNode node = root;for (int i = 0; i < word.length(); i++) {int index = word.charAt(i) - 'a';  // 得到当前字母在数组中的索引if (node.children[index] == null) {node.children[index] = new TrieNode();}node = node.children[index];}node.isEndOfWord = true;}// 搜索Trie中是否存在一个单词public boolean search(String word) {TrieNode node = searchPrefix(word);return node != null && node.isEndOfWord;}// 搜索Trie中是否存在一个单词的前缀public boolean startsWith(String prefix) {TrieNode node = searchPrefix(prefix);return node != null;}// 辅助方法：搜索前缀，并返回最后一个节点private TrieNode searchPrefix(String word) {TrieNode node = root;for (int i = 0; i < word.length(); i++) {int index = word.charAt(i) - 'a';if (node.children[index] == null) {return null;}node = node.children[index];}return node;}  public static void main(String[] args) {Trie trie = new Trie();// 新增appletrie.insert("apple");System.out.println(trie.search("apple"));   // 返回 trueSystem.out.println(trie.search("app"));     // 返回 falseSystem.out.println(trie.startsWith("app")); // 返回 truetrie.insert("app");System.out.println(trie.search("app"));     // 返回 true}
}

3 分析

优点

快速搜索：Trie树通过利用字符串的公共前缀来减少查询时间，查询效率非常高。在Trie树中搜索一个字符串的时间复杂度为O(k)，其中k是字符串的长度，与树中存储的字符串数量无关。这使得Trie树特别适合于处理大量字符串的快速检索问题。
节省空间：Trie树通过共享公共前缀来节省存储空间。在Trie树中，每个节点只存储一个字符，并且只有必要的节点才会被创建，因此相比存储完整的字符串列表，Trie树可以显著减少存储空间的使用。
自动完成：Trie树非常适合实现自动完成功能，如搜索引擎中的自动补全、代码编辑器的自动提示等。通过遍历Trie树，可以快速地找到所有以用户输入的前缀开头的字符串，从而为用户提供有用的建议。
高效插入和删除：在Trie树中插入和删除字符串的操作也非常高效，时间复杂度同样为O(k)，其中k是字符串的长度。这是因为插入和删除操作只需要遍历从根节点到目标节点的路径，并在必要时添加或删除节点。
高效排序：由于Trie树中的字符串是按照字典序排列的，因此可以利用Trie树对字符串进行高效排序。此外，Trie树还可以方便地支持范围查询等高级操作。
紧凑表示形式：Trie树提供了一种紧凑的数据表示形式，特别适合于存储和处理大量具有公共前缀的字符串数据。

缺点

存储空间需求高：尽管Trie树在节省空间方面有一定优势，但当处理的字符串数量非常大且字符串之间缺乏公共前缀时，Trie树可能会占用大量的存储空间。这是因为Trie树需要为每个字符串的每个字符都创建一个节点，从而导致节点数量激增。
相较哈希表效率更低：在某些情况下，如当需要频繁地进行随机访问时，哈希表可能会比Trie树更高效。哈希表通过哈希函数将字符串映射到固定的内存位置，从而实现快速的随机访问。而Trie树则更适合于处理具有前缀关系的字符串数据。
空指针耗费内存空间：在Trie树中，由于每个节点都可能有多个子节点（对应于不同的字符），因此即使某些子节点不存在，也需要用空指针来表示这种不存在关系。这些空指针会占用一定的内存空间，从而增加了Trie树的内存开销。

4 ik分词器

IK分词器是一款在中文自然语言处理（NLP）领域广泛应用的中文分词工具，其以高效、准确、灵活的特点受到了开发者和研究者的青睐。

1 介绍

定义：IK分词器是一款基于Java开发的开源中文分词工具，它是Lucene的一个扩展，专门用于中文文本的分词处理。
功能：IK分词器结合了词典分词和基于统计的分词方法，旨在为用户提供高效、准确、灵活的中文分词服务。

2 分词原理

词典分词
- IK分词器会维护一个包含大量中文词汇的词典。
- 文本预处理：将输入的文本进行预处理，包括去除标点符号、空格等无关字符。
- 词典匹配：IK分词器会从文本的起始位置开始，依次与词典中的词汇进行匹配，使用“最大匹配法”策略，尽可能匹配最长的词汇。
基于统计的分词
- 对于词典分词无法准确匹配的新词、缩写词或特殊表达方式，IK分词器会利用统计模型进行分词。
- 统计模型通过大量已标注的语料库训练得到，能够学习到词汇之间的关联和出现频率等信息。
- IK分词器会对候选词进行打分，选择概率最高的候选词序列作为分词结果。
解决歧义
- IK分词器采用最短路径法和最大概率法来解决分词中的歧义问题。
- 允许用户定义自定义规则来处理特定的歧义问题，提高分词的准确性。

5 ik源码

在这里插入图片描述

black.dic 黑名单词典集

main.dic 核心词典集，主要用于匹配

stopword.dic 暂停词词典集

1 词典的加载

在这里插入图片描述

词典加载后以前缀树的方式进行存储

在这里插入图片描述

2 分词核心api

IKSegmenter.next

获取分词后的结果

	/*** 分词，获取下一个词元* * @return Lexeme 词元对象* @throws IOException*/public synchronized Lexeme next() throws IOException {if (this.context.hasNextResult()) {// 存在尚未输出的分词结果return this.context.getNextLexeme();} else {/** 从reader中读取数据，填充buffer 如果reader是分次读入buffer的，那么buffer要进行移位处理* 移位处理上次读入的但未处理的数据*/int available = context.fillBuffer(this.input);if (available <= 0) {// reader已经读完context.reset();return null;} else {// 初始化指针context.initCursor();do {// 遍历子分词器for (ISegmenter segmenter : segmenters) {segmenter.analyze(context);}// 字符缓冲区接近读完，需要读入新的字符if (context.needRefillBuffer()) {break;}// 向前移动指针} while (context.moveCursor());// 重置子分词器，为下轮循环进行初始化for (ISegmenter segmenter : segmenters) {segmenter.reset();}}// 对分词进行歧义处理this.arbitrator.process(context, this.cfg.useSmart());// 处理未切分CJK字符context.processUnkownCJKChar();// 记录本次分词的缓冲区位移context.markBufferOffset();// 输出词元if (this.context.hasNextResult()) {return this.context.getNextLexeme();}return null;}}

org.wltea.analyzer.core.CJKSegmenter.analyze

关键词：

tmpHits：存放命中项的集合

hit：命中项，可以是main.dic中匹配到的，也可以是前缀，如果是前缀的话存放在tmpHits中

Lexeme：存放分词后的结果

public void analyze(AnalyzeContext context) {if (CharacterUtil.CHAR_USELESS != context.getCurrentCharType()) { // 上下问中的字符串不是不可用的// 优先处理tmpHits中的hitif (!this.tmpHits.isEmpty()) {// 处理词段队列Hit[] tmpArray = this.tmpHits.toArray(new Hit[this.tmpHits.size()]);for (Hit hit : tmpArray) {// 匹配main.dichit = Dictionary.getSingleton().matchWithHit(context.getSegmentBuff(), context.getCursor(), hit);if (hit.isMatch()) { // hit命中的是完整的词// 输出当前的词Lexeme newLexeme = new Lexeme(context.getBufferOffset(), hit.getBegin(), context.getCursor()- hit.getBegin() + 1, Lexeme.TYPE_CNWORD);newLexeme.setProps(hit.getProps());context.addLexeme(newLexeme);if (!hit.isPrefix()) {// 不是词前缀，hit不需要继续匹配，移除this.tmpHits.remove(hit);}} else if (hit.isUnmatch()) {// hit不是词，移除this.tmpHits.remove(hit);}}}// *********************************// 再对当前指针位置的字符进行单字匹配Hit singleCharHit = Dictionary.getSingleton().matchInMainDict(context.getSegmentBuff(), context.getCursor(), 1);if (singleCharHit.isMatch()) {// 首字成词// 输出当前的词Lexeme newLexeme = new Lexeme(context.getBufferOffset(), context.getCursor(), 1, Lexeme.TYPE_CNWORD);newLexeme.setProps(singleCharHit.getProps());context.addLexeme(newLexeme);// 同时也是词前缀if (singleCharHit.isPrefix()) {// 前缀匹配则放入hit列表this.tmpHits.add(singleCharHit);}} else if (singleCharHit.isPrefix()) {// 首字为词前缀// 前缀匹配则放入hit列表this.tmpHits.add(singleCharHit);}} else {// 遇到CHAR_USELESS字符// 清空队列this.tmpHits.clear();}// 判断缓冲区是否已经读完if (context.isBufferConsumed()) {// 清空队列this.tmpHits.clear();}// 判断是否锁定缓冲区if (this.tmpHits.size() == 0) {context.unlockBuffer(SEGMENTER_NAME);} else {context.lockBuffer(SEGMENTER_NAME);}}