为什么要分词?

英文: 天然空格分割 + 词根

古文一般不加标点, 读书主要目的是”离经辨志” (“离”及断句), “明句读” (句号, 逗号).

20世纪后, 逐步统一规范了中文标点符号

有了标点符号后, 需进一步分词的意义

消除歧义

• 我们/中/出了/叛徒 VS 我们/中出/了/叛徒
• 广州市/长隆乐园/欢迎/你 VS 广州市长/隆乐园/欢迎/你

业务功能落地场景

• 词云/热词分析/关键词抽取: 基于某个筛选维度, 分析高频出现词语
• 文本搜索
• 训练数据量预处理
• 进一步信息抽取

分词评价指标

• 准确率/召回率
  • p = 准确词数 / 实际分词数
  • r = 准确词数 / 标注分词数
• 缺点: 分词边界一致但是粒度细粗不能很好体现
  • 标注: 太/高兴/了
  • 识别1: 太高兴了 (p=r=0)
  • 识别2: 太高/兴了 (p=r=0)
• 登录词/未登录词 (OOV): 主要考察新词发现能力
• 识别速度 / 内存需求: 具体到业务落地时非常重要

词典分词

字符串匹配算法

文本长度N, 词典大小M, 词最长为D

Trie / 前缀树

• 为了匹配实现简单, 节点单字, 树深为D
• 需提前构建好

最长前缀匹配 O(D)

应用场景: CIDR/路由表, 域名查找 (最长后缀)

全文匹配 (一个朴素的办法): 每个位置做一次前缀匹配 O(N*D). 问题: 不匹配时很多计算路径信息被浪费了

AC算法:

• 每个节点记住到当前节点的最大后缀节点, 用于匹配失败后从该节点继续 (类比: 自动存档/回档)
• O(N)

DAT (Double-array Trie) 双数组实现Trie, 优化内存占用

See Code

多种分法的决策

词典无权重信息

• 优化目标: 最长匹配 OR 最多匹配 ?
• 最长匹配: 正向/逆向/双向
  • 正向 / FMM (Forward Max Match): 找当前最长匹配词
  • 逆向: 反向FMM
  • 双向: 都来一遍得到两个结果再决断, 优先选
  • NOTE: 都是贪心算法, 不保证匹配词总长最长, 本身是NP-hard问题

词典有权重信息 (词频)

• 最大词典权重 = 最大化联合概率 = max(sum(log(p)))
• 等价于寻路问题

viterbi vs 寻路

都是DP, 保存到当前位置结束的最大权重及前向位置

OOV / 新词发现

不在词典中的片段, 直接当作新词肯定是不合适的, 需要尝试再切一下

HMM

Hidden Markov Model

HMM考虑点

• 状态分几种
  • 两个状态标注分词够了, 但是两个状态太少
  • BEMS: Begin开始 / End结束 / Middle内部 / Single单词
  • BB1B2MES 6元法…
  • POS时, 还需要乘上词性
• 基于字还是词
• 一阶(unigram)还是高阶(n-gram) / 和基于字/词有一定重复

选择后者效果越好, 需要训练数据越多, 计算效率越慢

词典分词 和 HMM交互

两阶段流程:

1. 词典分出来最大路径
2. 剩下的片段HMM尝试再切出最大概率

问题:

• HMM切的片段里面也是有在词典的, 词频能否利用上
• 多阶段求最大, 不一定是全局最大

改进办法 (beam search):

• 词典分词得到N个最大路径(及联合概率)
• 每个路径继续HMM再分(取最大或M个最大)
• 得到每种分法的联合概率, 取最大

词频及HMM参数学习

大量标注好的文本后直接统计即可得到

TODO

jieba (0.39)

https://github.com/fxsjy/jieba/tree/v0.39

• POS逻辑和单分词逻辑不太一样
• 词典匹配非单词一定分
• 词典加载词性固定
• 做了全局状态 / re_xxx
• 没有持续维护了
• 连续单字走HMM, 一些常见介词容易误连起来

jieba.lcut("我们中出了叛徒", HMM=True)
['我们', '中出', '了', '叛徒']

See Code

可优化点:

• 一般进去的文本时提前处理过的, 不用再正则切一遍
• 去掉全局变量
• 加载提前, 避免每次调用初始化检查
• 概率log计算可提前处理掉
• 不用考虑PY2
• get_DAG是两层循环, 可改用AC+DAT
• 状态转移数据可以改成文件加载/优化数据结构
• …

分词当作序列标注问题

序列标注: N*S DAG 网格上的最大路径选择

词性:

• 语言角度: 名词/形容词/动词/…
• 业务角度:
  • 时间/日期/价格/…
  • 地名/人名/品牌名/…
  • 品类名/成分词/功效词/营销词/…

MEMM & CRF & SP

• 2000 / MEMM / Max Entropy Markov Model
  • 辨别式模型
• 2001 / CRF / Conditional Random Field / 条件随机场
  • 解决标签偏置问题 (Label Bias Problem)
  • LAC
• 2002 / SP / Structured Perceptron / 结构化感知器
  • THULAC / LTP

深度学习模型

1. 表征层 (独热编码变稀疏表征): Embedding / BERT / …
2. 记忆层: RNN / Bi-LSTM / Bi-GRU
   • 学输入对每个状态的概率表达
3. 表达层: HMM / CRF / SP / …
   • 学状态迁移概率

LAC

https://github.com/baidu/lac

https://github.com/PaddlePaddle/models/tree/release/1.8/PaddleNLP/lexical_analysis

https://github.com/PaddlePaddle/PaddleNLP/tree/develop/examples/lexical_analysis

模型结构: Embedding + bi-GRU * 2 + CRF

• 评测分词质量优于jieba
• 长文本大概率彻底躺平不分
  • e.g.: 红烧酱汁料包正宗红烧味懒人专属红烧酱汁90克
• 识别速度慢
• 运行时依赖大 (近500M, 多个模型文件全打包进依赖, 即便用不到, 依赖Paddle)
• 百度KPI项目? 废弃整合进会PaddleNLP项目?
• (Paddle导致) 硬件avx指令集绑定, mac/win某些版本加载失败
• (包括Paddle) 代码质量差, 自行改logging, 内存泄露, …

逆向想法:

1. 模型参数提取, 构造相同网络结构后导出ONNX
2. 用于生成文本训练数据, 训练还原

LTP

TODO https://github.com/HIT-SCIR/ltp

HanLP

TODO https://github.com/hankcs/HanLP

文本搜索

搜索基本原理

搜索不同于单文档匹配, 是要高效处理海量文档

1. 文档分词
   • 进一步结合搜索场景的处理, 正则化, 同义词/别名关联, 等等
2. 建立词到文档的倒排索引
3. 搜索文本分词, 文档计算相似度, 排序

精准匹配: 搜索文本必须是返回文本的子序列

• 做法: 相似度里面提最高, 缺点是文本本身分词导致和搜索文本不一致时无法召回

不分词办法: 字索引. 缺点: 单字索引文档过多检索效率低, 没有管字的顺序性

最暴力序列匹配办法: 每个文本, 切成最大N片段, 对所有子序列做索引, 搜索时对文本同理处理

稍微优化一些: 剔除有包含关系的分法

基于分词的办法: 把所有字典出来的分词路径做索引

减少检索量, 高频词作为停用词忽略掉

分词粒度之于搜索

切分较细 / 词较短 / 召回优先 切分较粗 / 词较长 / 准确优先

搜索相似度指标

• TF-IDF (Term Frequency / Inverted Document Frequency)
  • 文档权重 = sum(log(词在该文档命中次数)/log(词频) for 词 in 文本)
• BM25 (Best Matching):
  • https://en.wikipedia.org/wiki/Okapi_BM25
  • ES默认: https://www.elastic.co/guide/en/elasticsearch/reference/current/index-modules-similarity.html
• …

业务上根据其他字段匹配自行再加权计算: 如标题匹配分值要高一些, 命中词间距最好短一些, 等等

ES分词插件

IK分词器: https://github.com/medcl/elasticsearch-analysis-ik

• ik_max_word 各种分词组合来一遍
• ik_smart 基于词典的分割

官方插件: https://www.elastic.co/guide/en/elasticsearch/plugins/current/analysis-smartcn.html

搜索质量严重依赖于分词及相似度计算指标, 很多搜不出来, 可惜现在没有例行评估优化

Zipf Law / Power Law / 幂律 / 长尾理论 / 马太效应 / 二八定律

ref: https://www.nature.com/articles/srep00812

• 词出现频次和排名成反比
• QQ-plot / quantile-quantile plot 是条直线 ??
• log-log plot 是条直线 ??

从分词后做词云角度考虑:

• 找腰部的, 有区分度的词

编码 / Tokenization / 压缩 / 无监督自学习生成字典

上述分词 (构造词典, 计算HMM经验概率) 需要大量标注好的数据, 如何无监督的方式出分词? 语料 -> 最小编码字典过程

无损压缩 OR 有损压缩 ?

有损压缩: 掐头去尾

• 丢掉词频最高的部分: 最大化减少编码后数据大小, 幂律下放弃最少的人减最大的负担
• 丢掉词频很低的部分: 减少编码表宽, 也是小样本不具备学习意义

合OR分, 是个问题: 分开后需要大精力学会来

业务上分词优化想法

• 正则规则提前处理洗一遍
• 用积累的非歧义关键词做词典切词 / 通用词典切词 / 不做HMM
  • HMM需要比较好的标注数据支撑, 不过现在网络新词构造也不怎么讲道理
• 剩下片段做NER提取出营销词汇 (需要全文喂进去看全貌, 再对结果不一致做后处理)
• 再剩下的视情况随便分一分
• 结合编码结果???

好的领域词典才是王道

Reference

• https://conf.umlife.net/pages/viewpage.action?pageId=64532712
• https://zhuanlan.zhihu.com/p/67475895
• https://www.cnblogs.com/en-heng/p/6234006.html
• http://www.matrix67.com/blog/archives/5044
• https://kexue.fm/archives/5542
• https://kexue.fm/archives/7213