心法利器[41] | 我常说的词典匹配到底怎么做
心法利器
本栏目主要和大家一起讨论近期自己学习的心得和体会，与大家一起成长。具体介绍：仓颉专项：飞机大炮我都会，利器心法我还有。
近期，我再次总结了我的历史文章，累积起来有50w字，百余篇文章了，有兴趣可以拿来看看，获取方式：七夕清流，百余篇累计50w字文章合集发布。
往期回顾
前言：背景1是应霍华德大佬之邀，背景2是这东西我确实聊的最多却其实没聊清楚这里的细节，我的锅，所以这篇文章无论如何都得写了。
我已经有好多词都聊过分类、NER甚至匹配问题都可以用词典来做了，问题是词典到底怎么做，词典匹配是怎么做的，具体实现方法是什么，我却从来没聊过，这次给大家一次性说清楚，带上核心代码，从而让大家更好理解和使用。
词典匹配的背景和场景
词典匹配是NLP领域在工业界中非常常见的技术，尤其在互联网领域，主要原因是词典这个东西经常比标注样本更易得，尤其是搜索领域，一方面很多数据资源其实就存在数据库里，直接拿来清晰就能用，另一方面用户query等数据也多容易挖掘，因此词典匹配成为这个领域落地非常重要的方式，从在线流量视角，绝大部分的流量都是走的词典匹配，尤其是高频、简单的问题，相比之下模型只是个泛化、兜底的功能，加上词典匹配所特有的灵活性、可控性、高准确性、高性能等优点，词典匹配绝对是一个实用且必备的能力。
词典匹配的实现思路
要做技术设计，肯定是要理解需求。
功能上，给定一批词典，然后给一个用户query，找出query中包含的在词典内的词，例如词典内有“故宫”，则对用户query“故宫怎么走”，那要把这个“故宫”给匹配出来，复杂点的还要给出起点终点、正式词“故宫博物院”等，这就是最基本的功能。其实这个就是一个NER功能，所以最直接的，词典匹配就是一个NER任务。
但是，作为算法工程师，肯定还要考虑准确性和性能的问题，尤其是性能问题，显然，词典是可更新的，可大可小的，小到几个词（例如停止词），大到成千上万甚至更多，例如人名地名之类的，可枚举但是数量非常大，一个一个在词典里面找，那复杂度可就非常高了，尤其是当词典非常大的时候，逐字逐词匹配肯定不现实。这里非常考验大家解决数据结构、复杂度问题的功力（刷算法题是确认有用的！）。
直接说结论，使用的是最大逆向匹配方法，词典的存储则用的dict格式（数据结构上，技术允许的话用trie树最优，hashmap也是没问题的），在python里面就是用dict了（据说内部key的存储使用的trie，不确定，有知道的大佬出来聊聊）。
再展开没啥必要，上代码聊。
代码
整块核心代码不到50行，非常舒服。
这里我把整个词典匹配的工具写成一个类（应该是工程的基本操作了），主要两个成员函数，初始化和预测。
初始化
初始化其实很简单，就是加载词典。首先来看我的词典是一个什么结构，样例是这样的：
五哈 VarietyShow+++哈哈哈哈哈
哈哈哈哈哈 VarietyShow+++哈哈哈哈哈
故宫 Attraction+++故宫博物院
南京 City+++南京市
南京博物馆 Attraction+++南京博物馆
斗罗大陆 Novel+++斗罗大陆
斗罗大陆 Carton+++斗罗大陆
总的来说两列，用'\t'分隔，第一列是可匹配的词，第二列是对应词汇内部的信息，后续定义为"slot_info"这里定义是两列，用'+++'分隔（linux环境一般用'\001'这种人为输入几乎不可能看见的词汇），第一列是词汇类型或者叫做槽位名，第二列该词语正式的名字，后续可以用来做精确查询。
init部分就是加载词典了，来看看代码：
def __init__(self, dict_path):
slot_dict = {}
with open(dict_path, encoding="utf8") as f:
for line in f:
ll = line.strip().split("\t")
if len(ll) != 2:
continue
slot_info = ll[1].split('+++')
if len(slot_info) != 2:
continue
if ll[0] in slot_dict:
slot_dict[ll[0]].append({"slot_name": slot_info[0], "slot_value": slot_info[1]})
else:
slot_dict[ll[0]] = [{"slot_name": slot_info[0], "slot_value": slot_info[1]}]
self.slot_dict = slot_dict
这里读取后，我们把第一列，也就是待匹配的词作为dict的key，而slot_info则也是通过dict的形式存储，但这里的value用向量形式，然后可以存多个slot_info，因为一个词可能对应很多种不同的实体，例如“斗罗大陆”既是小说又是动漫，那这里当然是要存两个元素的。另外为了保护词典的合法性，避免出现异常数据而报错，所以肯定是要有一些约束过滤的。
这样加载好的词典就是这样的：
{
'五哈': [{
'slot_name': 'VarietyShow',
'slot_value': '哈哈哈哈哈'
}],
'哈哈哈哈哈': [{
'slot_name': 'VarietyShow',
'slot_value': '哈哈哈哈哈'
}],
'故宫': [{
'slot_name': 'Attraction',
'slot_value': '故宫博物院'
}],
'南京': [{
'slot_name': 'City',
'slot_value': '南京市'
}],
'南京博物馆': [{
'slot_name': 'Attraction',
'slot_value': '南京博物馆'
}],
'斗罗大陆': [{
'slot_name': 'Novel',
'slot_value': '斗罗大陆'
}, {
'slot_name': 'Carton',
'slot_value': '斗罗大陆'
}]
}
值得注意的是，在预测阶段，无论如何，我们都是要看query的局部内容是否在词典里的，所以一定会出现类似if a in slot_dict的语句，python这么多原生数据结构中，只有dict和set两种类型的运行速度最快（且不受到数据结构内部存储的数据的大小影响），而set由只能存词不能存slot_info，所以我们就选择了dict，这是词典匹配之所以能高性能的核心，这背后是对数据结构，对python这门语言原生的东西的理解。
预测部分
先上代码再来聊。
def predict(self, query):
query_len = len(query)
idx = 0
idy = query_len
slot_get = []
tmp_slot_get_len = 0
while idy > 0:
while idx < idy:
if query[idx:idy] in self.slot_dict:
for item in self.slot_dict[query[idx:idy]]:
slot_get.append({"slot_word": query[idx:idy],
"slot_name": item["slot_name"],
"slot_value":item["slot_value"],
"slot_start":idx,
"slot_end":idy
})
break
idx = idx + 1
if len(slot_get) != tmp_slot_get_len:
idy = idx
idx = 0
tmp_slot_get_len = len(slot_get)
else:
idx = 0
idy = idy - 1
return slot_get
最大逆向匹配，就是从后面开始，从最大开始逐步缩小范围，逐个匹配，查看每个局部是否在词典内存在，来看一个例子吧，query是“我想去南京的南京博物馆”，来看匹配查询的过程：
我想去南京的南京博物馆
想去南京的南京博物馆
去南京的南京博物馆
南京的南京博物馆
京的南京博物馆
的南京博物馆
南京博物馆 -- 识别到南京博物馆-Attraction实体。
我想去南京的
想去南京的
去南京的
南京的
京的
的
我想去南京
想去南京
去南京
南京 -- 识别到南京-City实体
我想去
想去
去
我想
想
我
最大逆向匹配的一个假设是只取最长的实体，所以南京博物馆出来了而这里的南京没有单独出来，大家可以理解到这里的匹配流程。
另外一个细节是在匹配到词典后，直接就把需要输出结果的结构就整理好了，完成遍历后就可以直接给出答案，还是“我想去南京的南京博物馆”，这里提取的结果是这样的：
[{
'slot_word': '南京博物馆',
'slot_name': 'Attraction',
'slot_value': '南京博物馆',
'slot_start': 6,
'slot_end': 11
}, {
'slot_word': '南京',
'slot_name': 'City',
'slot_value': '南京市',
'slot_start': 3,
'slot_end': 5
}]
小结
坑终究是填上了，词典匹配整个组件代码也不复杂，结构上也比较简单（不排除以后你还要做一些别的优化，例如热更新之类的），只是比较考虑自己写代码的功底。后续，有了这个工具，词典匹配做起来后，就能cover更多的问题，尤其是简单、高频的问题。
再留个坑，词典具体可以怎么来，怎么挖掘，找个时间详细聊聊~
最后送上完整版代码，大家可以根据自己的需求进行修改。
# 使用最大逆向匹配进行提槽
class DictSlot:
def __init__(self, dict_path):
slot_dict = {}
with open(dict_path, encoding="utf8") as f:
for line in f:
ll = line.strip().split("\t")
if len(ll) != 2:
continue
slot_info = ll[1].split('+++')
if len(slot_info) != 2:
continue
if ll[0] in slot_dict:
slot_dict[ll[0]].append({"slot_name": slot_info[0], "slot_value": slot_info[1]})
else:
slot_dict[ll[0]] = [{"slot_name": slot_info[0], "slot_value": slot_info[1]}]
self.slot_dict = slot_dict
def predict(self, query):
query_len = len(query)
idx = 0
idy = query_len
slot_get = []
tmp_slot_get_len = 0
while idy > 0:
while idx < idy:
if query[idx:idy] in self.slot_dict:
for item in self.slot_dict[query[idx:idy]]:
slot_get.append({"slot_word": query[idx:idy],
"slot_name": item["slot_name"],
"slot_value":item["slot_value"],
"slot_start":idx,
"slot_end":idy
})
break
idx = idx + 1
if len(slot_get) != tmp_slot_get_len:
idy = idx
idx = 0
tmp_slot_get_len = len(slot_get)
else:
idx = 0
idy = idy - 1
return slot_get
if __name__ == "__main__":
dict_sloter = DictSlot("slot_dict.txt")
print(dict_sloter.predict("我想去南京的南京博物馆"))
print(dict_sloter.predict("我想看斗罗大陆"))
print(dict_sloter.slot_dict)