关于分词的一些理解前言IK分词正向最大匹配反向最大匹配Jieba分词后记参考前言分词是NLP处理领域预处理的一种手段。因为我们如果想要对一段文本进行理解机器不会像人暂时不会一样能够看到一句话就大概知道是啥意思所以需要简化把文本进行拆分成基本的语义单元也就是 token然后就可以对这些基本的语义单元利用数学的手段进行各种处理最终服务于一些语义处理、匹配、情感分析、推荐等需求之中。原始中文文本分词器IK / jiebaToken 序列数学处理向量化 / 统计下游应用语义搜索情感分析智能推荐对这些 token 处理后的结果往往能反映出原文本段的一些语义或者其他特征信息。比如说下面一段文字我爱吃苹果我也爱吃香蕉我不爱吃葡萄分析之后就或多或少能分析出苹果、香蕉、葡萄这三种物体大概是属于一类的。英文分词比较简单最基本的可以按照标点符号进行分割当然实际上也需要处理如何优雅地剥离标点、拆分语法缩写等问题。而中文分词要复杂不少因为要处理复杂的语义问题。 “我爱吃苹果”中把“苹” 和“果” 分开语义的明确性就差了很多。下面简单总结下ElasticSearch中IK 和NLP 中的 jieba这两种分词。IK分词ES 作为搜索引擎底层的存储使用的是倒排索引。 这天然需要对输入的数据和查询的内容进行分词 然后进行相关性匹配即某个查询的分词在哪些文档中出现过。ES 中默认已经有了Standard分词器使用的是Unicode 文本分割算法对于中文分词来说会将中文文本按照字进行拆分效果不是很好。因此 ES 中如果要使用中文分词的特点大都会安装使用IK 分词。IK分词完全根据词典来进行文本切分。这个词典通常是以前缀树这样一种数据结构来进行组织。比如说“大数据软件工程”形成的一个字典树如下所示。根节点 ├─ 大 │ └─ 数 │ └─ 据 → 标记【完整词大数据】 ├─ 数 │ └─ 据 → 标记【完整词数据】 ├─ 软 │ └─ 件 → 标记【完整词软件】 │ └─ 工 │ └─ 程 → 标记【完整词软件工程】...IK 分词在匹配的时候有两种策略正向最大匹配一种是ik_max_word最细粒度也就是正向最大匹配递归拆分拆出所有字典中可能的词。比如说有一个字典词长词条4 字软件工程、人工智能3 字大数据、工程师、计算机2 字数据、技术、软件、工程、智能、人工、学习、和尚、尚未、结婚1 字所有单字兜底匹配不到长词就拆单字想要对“大数据工程师学习软件工程” 进行匹配。流程如下匹配流程如下指针在第 1 字「大」尝试最长 4 字「大数据工」→ 前缀树走不通无匹配尝试 3 字「大数据」→ 命中完整词切出大数据指针跳到第 4 字「工」指针在第 4 字「工」尝试 3 字「工程师」→ 命中切出工程师指针跳到第 7 字「学」指针在第 7 字「学」尝试 3 字「学习软」→ 无匹配尝试 2 字「学习」→ 命中切出学习指针跳到第 9 字「软」指针在第 9 字「软」尝试 4 字「软件工程」→ 命中切出软件工程指针到末尾结束正向最大匹配结果[大数据, 工程师, 学习, 软件工程] ok没啥问题。反向最大匹配正向最大匹配对于一些句子可能会产生歧义的划分逻辑。比如说“ 结婚的和尚未结婚的” 这个句子正向匹配之后的结果为 [结婚, 的, 和尚, 未, 结婚, 的] “和尚”一词在结婚的语境中拆分出来就有些突兀。所以 IK中还有一种匹配策略ik_smart智能模式反向最大匹配输出最粗粒度的合理切分。因为中文里偏正结构多、中心词在后面反向匹配的准确率通常比正向高歧义更少。比如说对于上面有歧义的句子的拆分过程如下从右往左匹配匹配流程如下从右往左末尾「的」单字→ 切出剩余「结婚的和尚未结婚」「结婚」命中→ 切出剩余「结婚的和尚未」「尚未」命中→ 切出剩余「结婚的和」「和」单字→ 切出剩余「结婚的」「的」单字→ 切出剩余「结婚」「结婚」命中→ 结束反向匹配结果[结婚, 的, 和, 尚未, 结婚, 的] 拆分的语义是 ok 的。从某种程度上说IK 分词使用的贪心的思路算的是局部的最优解所以可能会得出有歧义的分词方式即使是 smart 方式也会得出有歧义的拆分方式。Jieba分词jieba分词最核心的部分这里不考虑jieba 中 HMM 统计的模型也主要是基于词典来进行拆分不过于 IK不一样的地方在于Jieba 的字典是带有统计频率即词频的每个词条的词频都来自大规模中文语料的真实统计。因此在计算不同的拆分方式的时候可以计算出统计概率最大的那种拆分方式。如下图所示为“去北京大学玩” 相关的词典。词条词频乒乓球1000乒乓200球拍1200拍卖600卖400完了700球300在实际拆分的时候Jieba 会先找出文本中所有可能的词和所有可能的切分点构造出一个DAG(有向无环图)在实际加载主词典dict.txt 时jieba 会把每一个词条的所有前缀子串都存储词典。如下表所示。key前缀存储值含义乒0只是前缀不是完整词乒乓0只是前缀不是完整词乒乓球1000是完整词词频 1000最终构造的 DAG 如下乒乒乓乒乓球乓球球拍拍拍卖卖完完了了0: 乒1: 乓2: 球3: 拍4: 卖5: 完6: 了7: 结束代码表示就是dag{0:[1,2,3],1:[2],2:[3,4],3:[4,5],4:[5],5:[6,7],6:[7]}用动态规划从后往前算每条切分路径的总概率。本质上就是算 DAG 图的单源最长路径简要的示例代码如下# -*- coding: utf-8 -*- 基于 DAG有向无环图 最大路径分数的分词算法。 逻辑对应 split_token.go 中的核心实现。 DAG 结构dag_map[起点][终点] 该边的分数词频 目标从 0 到 n文本末尾中找到分数总和最大的一条路径 每条边对应一个词路径上的边序列即为分词结果。 fromtypingimportDict,List,Tupledefget_point_self_map(dag_map:Dict[int,Dict[int,int]])-Dict[int,List[int]]:构造反向邻接表每个节点由哪些节点指向它。point_to_self_map:Dict[int,List[int]]{}forpoint_node,next_mapindag_map.items():fornodeinnext_map:point_to_self_map.setdefault(node,[]).append(point_node)returnpoint_to_self_mapdefget_score(dag_map:Dict[int,Dict[int,int]],a:int,b:int)-int:获取边 a-b 的分数。ifanotindag_map:raiseKeyError(fnot found:{a})returndag_map[a].get(b,0)defsplit_token(dag_map:Dict[int,Dict[int,int]],n:int)-List[Tuple[int,int]]: 倒序动态规划求解 max_path[i] (从 i 出发到终点的最大分数, 该最大分数对应的下一节点) 参数 n 为 max_path 数组长度一般传 文本长度 1。 返回 [(score, next_node), ...] point_self_mapget_point_self_map(dag_map)# 初始化所有节点 (score0, next_node0)max_path:List[List[int]][[0,0]for_inrange(n)]# 从末尾向前推forindexinrange(n-1,-1,-1):ifindexnotinpoint_self_map:continueforpoint_nodeinpoint_self_map[index]:path_scoreget_score(dag_map,point_node,index)cur_scoremax_path[point_node][0]new_scorepath_scoremax_path[index][0]ifnew_scorecur_score:max_path[point_node][0]new_score max_path[point_node][1]indexreturn[(s,nn)fors,nninmax_path]defget_token_text(text:str,dag_map:Dict[int,Dict[int,int]])-List[str]: 按字符而非字节对文本进行分词。 dag_map 的下标以字符为单位0..len(text)。 max_pathsplit_token(dag_map,len(text)1)ans:List[str][]cur_node0whilecur_nodelen(text):next_nodemax_path[cur_node][1]ifnext_nodecur_node:# 防御若图不连通/未构造好避免死循环breakans.append(text[cur_node:next_node])cur_nodenext_nodereturnans# ------------------------------------------------------------------# 测试用例乒乓球拍卖完了## | 词条 | 词频 |# |---------|--------|# | 乒乓球 | 1000 |# | 乒乓 | 200 |# | 球拍 | 1200 |# | 拍卖 | 600 |# | 卖 | 400 |# | 完了 | 700 |# | 球 | 300 |## 字符下标0:乒 1:乓 2:球 3:拍 4:卖 5:完 6:了 (末位7)## DAG:# 0: [1, 2, 3]# 1: [2]# 2: [3, 4]# 3: [4, 5]# 4: [5]# 5: [6, 7]# 6: [7]# ------------------------------------------------------------------deftest_split_text()-None:text乒乓球拍卖完了dag_map:Dict[int,Dict[int,int]]{0:{1:1,2:200,3:1000},# 乒 / 乒乓 / 乒乓球1:{2:1},# 乓2:{3:300,4:1200},# 球 / 球拍3:{4:1,5:600},# 拍 / 拍卖4:{5:400},# 卖5:{6:1,7:700},# 完 / 完了6:{7:1},# 了}tokensget_token_text(text,dag_map)print(分词结果:,tokens)# 最优路径 0-2-4-5-7 : 乒乓/球拍/卖/完了# 分数 200 1200 400 700 2500if__name____main__:test_split_text()最终的切分结果就是: 乒乓/球拍/卖/完了从某种程度上说,jieba 分词是通过动态规划来寻找整句话出现概率最高拆分组合。后记IK 中的分词使用贪心匹配CPU 开销较低是专门为 搜索场景设计的不追求最精准的分词语义。而 jieba 主要是服务于文本理解、NLP 预处理、内容分析所以用了较为复杂的算法和性能消耗来换取准确率。分词其实还涉及到很多其他的内容比如说 jieba 中为了处理为登录词汇的 HMM 模型这里仅仅只是简单总结了 IK 和 Jieba 的简单原理更多、更复杂的内容还留待后面慢慢探索。参考【1】IK 分词【2】ES分布式搜索引擎【3】结巴分词原理介绍【4】结巴分词2–基于前缀词典及动态规划实现分词
关于分词的一些理解前言IK分词正向最大匹配反向最大匹配Jieba分词后记参考前言分词是NLP处理领域预处理的一种手段。因为我们如果想要对一段文本进行理解机器不会像人暂时不会一样能够看到一句话就大概知道是啥意思所以需要简化把文本进行拆分成基本的语义单元也就是 token然后就可以对这些基本的语义单元利用数学的手段进行各种处理最终服务于一些语义处理、匹配、情感分析、推荐等需求之中。原始中文文本分词器IK / jiebaToken 序列数学处理向量化 / 统计下游应用语义搜索情感分析智能推荐对这些 token 处理后的结果往往能反映出原文本段的一些语义或者其他特征信息。比如说下面一段文字我爱吃苹果我也爱吃香蕉我不爱吃葡萄分析之后就或多或少能分析出苹果、香蕉、葡萄这三种物体大概是属于一类的。英文分词比较简单最基本的可以按照标点符号进行分割当然实际上也需要处理如何优雅地剥离标点、拆分语法缩写等问题。而中文分词要复杂不少因为要处理复杂的语义问题。 “我爱吃苹果”中把“苹” 和“果” 分开语义的明确性就差了很多。下面简单总结下ElasticSearch中IK 和NLP 中的 jieba这两种分词。IK分词ES 作为搜索引擎底层的存储使用的是倒排索引。 这天然需要对输入的数据和查询的内容进行分词 然后进行相关性匹配即某个查询的分词在哪些文档中出现过。ES 中默认已经有了Standard分词器使用的是Unicode 文本分割算法对于中文分词来说会将中文文本按照字进行拆分效果不是很好。因此 ES 中如果要使用中文分词的特点大都会安装使用IK 分词。IK分词完全根据词典来进行文本切分。这个词典通常是以前缀树这样一种数据结构来进行组织。比如说“大数据软件工程”形成的一个字典树如下所示。根节点 ├─ 大 │ └─ 数 │ └─ 据 → 标记【完整词大数据】 ├─ 数 │ └─ 据 → 标记【完整词数据】 ├─ 软 │ └─ 件 → 标记【完整词软件】 │ └─ 工 │ └─ 程 → 标记【完整词软件工程】...IK 分词在匹配的时候有两种策略正向最大匹配一种是ik_max_word最细粒度也就是正向最大匹配递归拆分拆出所有字典中可能的词。比如说有一个字典词长词条4 字软件工程、人工智能3 字大数据、工程师、计算机2 字数据、技术、软件、工程、智能、人工、学习、和尚、尚未、结婚1 字所有单字兜底匹配不到长词就拆单字想要对“大数据工程师学习软件工程” 进行匹配。流程如下匹配流程如下指针在第 1 字「大」尝试最长 4 字「大数据工」→ 前缀树走不通无匹配尝试 3 字「大数据」→ 命中完整词切出大数据指针跳到第 4 字「工」指针在第 4 字「工」尝试 3 字「工程师」→ 命中切出工程师指针跳到第 7 字「学」指针在第 7 字「学」尝试 3 字「学习软」→ 无匹配尝试 2 字「学习」→ 命中切出学习指针跳到第 9 字「软」指针在第 9 字「软」尝试 4 字「软件工程」→ 命中切出软件工程指针到末尾结束正向最大匹配结果[大数据, 工程师, 学习, 软件工程] ok没啥问题。反向最大匹配正向最大匹配对于一些句子可能会产生歧义的划分逻辑。比如说“ 结婚的和尚未结婚的” 这个句子正向匹配之后的结果为 [结婚, 的, 和尚, 未, 结婚, 的] “和尚”一词在结婚的语境中拆分出来就有些突兀。所以 IK中还有一种匹配策略ik_smart智能模式反向最大匹配输出最粗粒度的合理切分。因为中文里偏正结构多、中心词在后面反向匹配的准确率通常比正向高歧义更少。比如说对于上面有歧义的句子的拆分过程如下从右往左匹配匹配流程如下从右往左末尾「的」单字→ 切出剩余「结婚的和尚未结婚」「结婚」命中→ 切出剩余「结婚的和尚未」「尚未」命中→ 切出剩余「结婚的和」「和」单字→ 切出剩余「结婚的」「的」单字→ 切出剩余「结婚」「结婚」命中→ 结束反向匹配结果[结婚, 的, 和, 尚未, 结婚, 的] 拆分的语义是 ok 的。从某种程度上说IK 分词使用的贪心的思路算的是局部的最优解所以可能会得出有歧义的分词方式即使是 smart 方式也会得出有歧义的拆分方式。Jieba分词jieba分词最核心的部分这里不考虑jieba 中 HMM 统计的模型也主要是基于词典来进行拆分不过于 IK不一样的地方在于Jieba 的字典是带有统计频率即词频的每个词条的词频都来自大规模中文语料的真实统计。因此在计算不同的拆分方式的时候可以计算出统计概率最大的那种拆分方式。如下图所示为“去北京大学玩” 相关的词典。词条词频乒乓球1000乒乓200球拍1200拍卖600卖400完了700球300在实际拆分的时候Jieba 会先找出文本中所有可能的词和所有可能的切分点构造出一个DAG(有向无环图)在实际加载主词典dict.txt 时jieba 会把每一个词条的所有前缀子串都存储词典。如下表所示。key前缀存储值含义乒0只是前缀不是完整词乒乓0只是前缀不是完整词乒乓球1000是完整词词频 1000最终构造的 DAG 如下乒乒乓乒乓球乓球球拍拍拍卖卖完完了了0: 乒1: 乓2: 球3: 拍4: 卖5: 完6: 了7: 结束代码表示就是dag{0:[1,2,3],1:[2],2:[3,4],3:[4,5],4:[5],5:[6,7],6:[7]}用动态规划从后往前算每条切分路径的总概率。本质上就是算 DAG 图的单源最长路径简要的示例代码如下# -*- coding: utf-8 -*- 基于 DAG有向无环图 最大路径分数的分词算法。 逻辑对应 split_token.go 中的核心实现。 DAG 结构dag_map[起点][终点] 该边的分数词频 目标从 0 到 n文本末尾中找到分数总和最大的一条路径 每条边对应一个词路径上的边序列即为分词结果。 fromtypingimportDict,List,Tupledefget_point_self_map(dag_map:Dict[int,Dict[int,int]])-Dict[int,List[int]]:构造反向邻接表每个节点由哪些节点指向它。point_to_self_map:Dict[int,List[int]]{}forpoint_node,next_mapindag_map.items():fornodeinnext_map:point_to_self_map.setdefault(node,[]).append(point_node)returnpoint_to_self_mapdefget_score(dag_map:Dict[int,Dict[int,int]],a:int,b:int)-int:获取边 a-b 的分数。ifanotindag_map:raiseKeyError(fnot found:{a})returndag_map[a].get(b,0)defsplit_token(dag_map:Dict[int,Dict[int,int]],n:int)-List[Tuple[int,int]]: 倒序动态规划求解 max_path[i] (从 i 出发到终点的最大分数, 该最大分数对应的下一节点) 参数 n 为 max_path 数组长度一般传 文本长度 1。 返回 [(score, next_node), ...] point_self_mapget_point_self_map(dag_map)# 初始化所有节点 (score0, next_node0)max_path:List[List[int]][[0,0]for_inrange(n)]# 从末尾向前推forindexinrange(n-1,-1,-1):ifindexnotinpoint_self_map:continueforpoint_nodeinpoint_self_map[index]:path_scoreget_score(dag_map,point_node,index)cur_scoremax_path[point_node][0]new_scorepath_scoremax_path[index][0]ifnew_scorecur_score:max_path[point_node][0]new_score max_path[point_node][1]indexreturn[(s,nn)fors,nninmax_path]defget_token_text(text:str,dag_map:Dict[int,Dict[int,int]])-List[str]: 按字符而非字节对文本进行分词。 dag_map 的下标以字符为单位0..len(text)。 max_pathsplit_token(dag_map,len(text)1)ans:List[str][]cur_node0whilecur_nodelen(text):next_nodemax_path[cur_node][1]ifnext_nodecur_node:# 防御若图不连通/未构造好避免死循环breakans.append(text[cur_node:next_node])cur_nodenext_nodereturnans# ------------------------------------------------------------------# 测试用例乒乓球拍卖完了## | 词条 | 词频 |# |---------|--------|# | 乒乓球 | 1000 |# | 乒乓 | 200 |# | 球拍 | 1200 |# | 拍卖 | 600 |# | 卖 | 400 |# | 完了 | 700 |# | 球 | 300 |## 字符下标0:乒 1:乓 2:球 3:拍 4:卖 5:完 6:了 (末位7)## DAG:# 0: [1, 2, 3]# 1: [2]# 2: [3, 4]# 3: [4, 5]# 4: [5]# 5: [6, 7]# 6: [7]# ------------------------------------------------------------------deftest_split_text()-None:text乒乓球拍卖完了dag_map:Dict[int,Dict[int,int]]{0:{1:1,2:200,3:1000},# 乒 / 乒乓 / 乒乓球1:{2:1},# 乓2:{3:300,4:1200},# 球 / 球拍3:{4:1,5:600},# 拍 / 拍卖4:{5:400},# 卖5:{6:1,7:700},# 完 / 完了6:{7:1},# 了}tokensget_token_text(text,dag_map)print(分词结果:,tokens)# 最优路径 0-2-4-5-7 : 乒乓/球拍/卖/完了# 分数 200 1200 400 700 2500if__name____main__:test_split_text()最终的切分结果就是: 乒乓/球拍/卖/完了从某种程度上说,jieba 分词是通过动态规划来寻找整句话出现概率最高拆分组合。后记IK 中的分词使用贪心匹配CPU 开销较低是专门为 搜索场景设计的不追求最精准的分词语义。而 jieba 主要是服务于文本理解、NLP 预处理、内容分析所以用了较为复杂的算法和性能消耗来换取准确率。分词其实还涉及到很多其他的内容比如说 jieba 中为了处理为登录词汇的 HMM 模型这里仅仅只是简单总结了 IK 和 Jieba 的简单原理更多、更复杂的内容还留待后面慢慢探索。参考【1】IK 分词【2】ES分布式搜索引擎【3】结巴分词原理介绍【4】结巴分词2–基于前缀词典及动态规划实现分词
)
