实体抽取：基于词典匹配的方法【珠峰书《知识图谱：认知智能理论与实战》配套】

本系列文章为珠峰书《知识图谱：认知智能理论与实战》配套的材料

在《知识图谱：认知智能理论与实战》一书中，对实体的定义为：

 实体（Entity）：是指一种独立的、拥有清晰特征的、能够区别于其他事物的事物。在信息抽取、自然语言处理和知识图谱等领域，用来描述这些事物的信息即实体。实体可以是抽象的或者具体的。

——王文广 《知识图谱：认知智能理论与实战》 P81

这是对1996年MUC-6会议对命名实体的扩展。MUC组委会在当时提出的“命名实体”任务要求从文本中识别出所有的人物名称（人名）、组织机构名称（机构名）和地理位置名称（地名），以及时间、货币和百分数的表述。如果仅仅识别人名、地名、机构名等实体的话，常见的分词库（如 jieba、HanLP、LAC 等）都支持的，可以直接使用这些库来识别，效果通常还不错。

而如果要在产业应用中进行实体抽取，仅仅能够处理这几个命名实体则远远不够。比如书名的识别、建筑物名称的识别、汽车品牌的识别、汽车零部件的识别等等。

在实践中，实体不一定是对物理事物的表述，也可以是对虚拟事物的表述。比如“经济指标”类型的实体“CPI”、人物或者组织机构发表的“观点”类型的实体、某个领域权威人物发表的“言论”类型的实体，在制造业质量和可靠性工程中的“失效事件”类型的实体，以及在各类机械与电子电器设备制造领域中的“性能”类型的实体等。

——王文广 《知识图谱：认知智能理论与实战》 P81

虽然机器学习和深度学习发展到成熟度很高的阶段，在大量的业务系统中已经非常常见，但基于规则的方法依然非常有效。《知识图谱：认知智能理论与实战》一书介绍了三种基于规则的方法：

• 基于词典匹配的实体抽取方法 3.2.1节，P83

• 编写正则表达式抽取实体 3.2.2节，P84

• 基于模板的实体抽取方法 3.2.3节，P85

一、基于词典匹配的实体抽取方法

本例子配合 《知识图谱：认知智能理论与实战》3.2.1节《基于词典匹配的实体抽取方法》使用更佳。

使用Trie树数据结构（也称字典树、前缀树）来构建词典，并通过前向最大匹配，从一串文本中找到词典中的实体。基于词典匹配的方法在深度学习兴起以前广泛应用在搜索引擎、分词和实体抽取中。即使在今天，许多场景下使用词典匹配的方法也能够很好地满足实体抽取的业务需求。

参考内容：

• Trie树结构说明：《知识图谱：认知智能理论与实战》3.2.1节《基于词典匹配的实体抽取方法》，P83-84

• Trie 树例子：《知识图谱：认知智能理论与实战》图3-1，P83-84

• wikipedia Trie 词条： 英文(https://en.wikipedia.org/wiki/Trie)  | 中文(https://zh.wikipedia.org/wiki/Trie)

 二、Trie树数据结构及正向最大匹配算法的 python 实现

class TrieNode:
    """Trie 树的节点"""
    def __init__(self, c):
        #  保存字符
        self.c = c
        # 是否是一个词的终止字
        self.is_end = False
        # 保存子节点，key 为字，value 为节点
        self.children = {}
       
class Trie(object):
    """Trie 树"""
    def __init__(self):
        """根节点，空的，不保存任何字符"""
        self.root = TrieNode('\x01')
   
    def add(self, w):
        """插入词，构建 Trie 树"""
        n = self.root
        # 插入到合适的节点中
        for c in w:
            if c in n.children:
                n = n.children[c]
            else:
                nn = TrieNode(c)
                n.children[c] = nn
                n = nn
        # 词的最后一个字所对应的节点
        n.is_end = True
   
    def fmm(self, s):
        """正向最大匹配(forward maximum matching)算法"""
        results = []
        slen = len(s)
        i = 0
        while i < slen:
            n = self.root
            w = ''
            for j in range(i, slen):
                c = s[j]
                if c in n.children:
                    n = n.children[c]
                    w += c
                else:
                    if n.is_end:
                        # 如果匹配出一个词，则从该词的结束位置开始下一次匹配
                        results.append(w)
                        i = j-1
                    break
            i += 1
        return results

三、省市县抽取实例

载入中国省市县数据（可从https://github.com/wgwang/kg-book/blob/main/codes/3.2/%E7%9C%81%E5%B8%82%E5%8E%BF%E8%AF%8D%E5%85%B8.txt 下载），构建 Trie 树。

t = Trie()
with open('省市县词典.txt') as f:
    for line in f:
        t.add(line.strip())

四、利用最大前向匹配抽取实体

从百度搜索“联系地址 site:gov.cn”，可以看到大量的地址信息，可用于测试。

s = '地址信息 地址:广东省深圳市龙岗区龙翔大道8033号 邮政编码:518100 电子邮箱:[e-mail] 技术支持:龙岗区政务服务数据管理局'
t.fmm(s)

']

五、参考

本问代码及数据可从 https://github.com/wgwang/kg-book 上获取