NLP札记4-字典树
完全切分、正向最长匹配和逆向最长匹配这三种算法的缺点就是如何判断集合中是否含有字符串。
- 如果使用有序集合，复杂度高；
- 使用散列表，时间复杂度降低，但是内存复杂度上去
使用字典树这种数据结构，速度快、内存还省
字典树
什么是字典树
字符串集合常用字典树（trie树、前缀树）存储，字符串上的树形结构。特点如下
- 每条边对应一个数字
- 从根节点往下构成一个个字符串
- 字典树不是在节点上存储字符串，将词语视作根节点到某个节点之间的一条路径
- 字符串就是一条路径，从根节点开始，沿着路径往下走，就可以查询到该词语
字典树的节点实现
每个节点至少有自己的子节点和对应的边，以及自己是否对应一个词。如果是map映射而不是集合set ，还需要自己对应的值。
代码语言：javascript复制# 节点Node实现
class Node(object):
def __init__(self, value):
self._children = {}
self._value = value
def _add_child(self, char, value, overwrite=False):
child = self._children.get(char) # 先检查是否存在字符char对应的child
if child is None:
child = Node(value)
self._children[char] = child
elif overwrite: # 覆盖
child._value = value
return child字典树的增删改查
每个节点都是一个状态，从父节点到子节点的转义看做是一次状态转移。
代码语言：javascript复制# 字典树的实现
class Trie(Node):
def __init__(self):
super().__init__(None) # 魔术方法重载
def __contains__(self, key):
return self[key] is not None
def __getitem__(self, key):
state = self
for char in key:
state = state._children.get(char)
if state is None:
return None
return state._value
def __setitem__(self, key, value):
state = self
for i, char in enumerate(key):
if i < len(key) - 1:
state = state._add_child(char, None, False)
else:
state = state._add_child(char, value, True)
# 测试代码
if __name__ == "__main__":
trie = Trie()
# 增
trie['自然'] = "nature"
trie['自然人'] = "human"
assert "自然" in trie
# 删
trie['自然'] = None
assert '自然' not in trie
# 改
trie['自然语言'] = 'human language'
assert trie['自然语言'] == 'human language'
# 查
assert trie['入门'] == 'introduction'首字散列其余二分的字典树
散列函数：将对象转换成整数（散列值）。散列函数的基本要求：对象相同，散列值必须相同。如果对象不同，则散列值也不同，称之为完美散列。BinTrie的特点是根节点上实施散列策略，其余节点采用二分查找。
双数组字典树
DAT构成
双数组字典树，Double Array Trie，DAT，是状态转移为常数的数据结构。
- 元素base
- 下标check
# 状态b接受字符c转移到状态p
# 执行一次加法和整数比较的过程
p = base[b] c
check[p] = base[b]实现DAT
代码语言：javascript复制class DoubleArrayTrie(object): # 定义双数组
def __init__(self,dic):
m = JClass("java.util.TreeMap")()
for k, v in dic.items():
m[k] = v
dat = JClass("com.hankcs.hanlp.collection.trie.DoubleArrayTrie")(m)
self.base = dat.base
self.check = dat.check
self.value = dat.v
def char_hash(c): # python默认的方法是不适合散列函数的，通过Java的hashCode方法
return JClass('java.lang.Character')(c).hashCode()
def transition(self, c, b): # 转移函数实现
p = self.base(b) self.char_hase(c) 1
if self.base[b] == self.check[p]:
return p
else:
return -1
def __getitem__(self, key): # 查询函数
b = 0
for i in range(0, len(key)):
p = self.transition(key[i], b)
if p is not -1:
b = p
else:
return None
p = self.base[b]
n = self.base[p]
if p == self.check[p] and n < 0:
index = -n - 1
return self.value[index]
return NoneAC自动机
DAT全切分的复杂度是O(n^2)，AC自动机的复杂度是O(n)，常用于多字符串搜索。字典树是前缀树，从根节点上下来的路径对应公共路径。AC自动机在前缀树的基础上，添加了后缀树，节省了大量的查询时间，它的组成分为3个表：
- goto表（success表），本质上就是字典树
- fail表
- output表
基于双数组的AC自动机
基本原理是替换AC自动机的goto表，看作为一颗双数组字典树的每个状态附上额外的信息。构建原理是为每个状态base[i]和check[i]构建output[i]和fail[i]，具体分为3步：
- 构建普通的字典树，让终结点记住对应模式串的字典顺序
- 构建双数组字典树，在将每个状态映射到双数组中时，记住每个状态在双数组中的下标位置
- 构建
AC自动机，fail表中存储的就是状态的下标
准确率评测
混淆矩阵
四种组合的解释：
- TP：预测是P，真实值也是P———真阳
- FP：预测是P，真实值是N———假阳
- FN：预测是N，真实值是P———假阴
- TN：预测是N，真实值也是N———真阴
精准率precision
精准率指的是，在预测为P的结果中，正类数量占据全部结果的比率。分母是预测为阳性的数目
召回率recall
召回率指的是，在正类样本中，被找出来的比率。在搜索引擎评测中，召回率为相关网页被搜索到的比率。分母是真实值为阳性的数目
笔记：P和R是两个相互对立的指标：一个变大，另一个必然变小
F1值
值指的是精准率和召回率的调和平均值
中文分词中PRF_1的计算
混淆矩阵针对的是答案和预测数量相等的情况。中文分词中，标准答案和分词结果的单词书不一定是相等的。
- 混淆矩阵针对的是分类问题
- 中文分词针对的是分块问题
长度为n的字符串，分词结果是一系列的单词，单词在文本的起止位置记作区间[i,j],1leq i leq j leq n 。如下假设： 标准答案构成区间为A，作为正类（答案为P），区间之外构成负类 记分词结果所有单词区间构成集合B（预测结果为P）
def to_region(segmentation):
region = []
start = 0
for word in re.compile("\s ").split(segmentation.strip()):
end = start len(word)
region.append((start, end))
start = end
return region
def prf(gold, pred):
sizeA, sizeB, capAB = 0, 0, 0
with open(gold) as gd, open(pred) as pd:
for g, p in zip(gd, pd):
A, B = set(to_region(g)), set(to_region(p))
sizeA = len(A)
sizeB = len(B)
capAB = len(A & B)
p,r = capAB / sizeB, capAB / sizeA
return p, r, 2*p*r/(p*r)字典树的其他应用
- 停用词过滤
停用词指的是没有什么意义的词语，比如“的”、“甚至”等，去掉了对整个句子没有什么影响
- 简繁转化
简体中文和繁体中文之间的相互转化。HanLP将中文分为简体s、繁体t、台湾正体tw、香港繁体hk4这4种。
- 拼音转换
将拼音转换为汉字的问题。
