简介 转载于：心法利器[41] | 我常说的词典匹配到底怎么做 。
我已经有好多词都聊过分类、NER甚至匹配问题都可以用词典来做了，问题是词典到底怎么做，词典匹配是怎么做的，具体实现方法是什么，我却从来没聊过，这次给大家一次性说清楚，带上核心代码，从而让大家更好理解和使用。
1. 词典匹配的背景和场景 词典匹配是NLP领域在工业界中非常常见的技术，尤其在互联网领域，主要原因是词典这个东西经常比标注样本更易得，尤其是搜索领域，一方面很多数据资源其实就存在数据库里，直接拿来清晰就能用，另一方面用户query等数据也多容易挖掘，因此词典匹配成为这个领域落地非常重要的方式，从在线流量视角，绝大部分的流量都是走的词典匹配，尤其是高频、简单的问题，相比之下模型只是个泛化、兜底的功能，加上词典匹配所特有的灵活性、可控性、高准确性、高性能等优点，词典匹配绝对是一个实用且必备的能力。
2. 词典匹配的实现思路 要做技术设计，肯定是要理解需求。
功能上，给定一批词典，然后给一个用户query，找出query中包含的在词典内的词，例如词典内有“故宫”，则对用户query“故宫怎么走”，那要把这个“故宫”给匹配出来，复杂点的还要给出起点终点、正式词“故宫博物院”等，这就是最基本的功能。其实这个就是一个NER功能，所以最直接的，词典匹配就是一个NER任务。
但是，作为算法工程师，肯定还要考虑准确性和性能的问题，尤其是性能问题，显然，词典是可更新的，可大可小的，小到几个词（例如停止词），大到成千上万甚至更多，例如人名地名之类的，可枚举但是数量非常大，一个一个在词典里面找，那复杂度可就非常高了，尤其是当词典非常大的时候，逐字逐词匹配肯定不现实。这里非常考验大家解决数据结构、复杂度问题的功力（刷算法题是确认有用的！）。
直接说结论，使用的是最大逆向匹配方法，词典的存储则用的dict格式（数据结构上，技术允许的话用trie树最优，hashmap也是没问题的），在python里面就是用dict了（据说内部key的存储使用的trie，不确定，有知道的大佬出来聊聊）。
再展开没啥必要，上代码聊。
3. 代码 整块核心代码不到50行，非常舒服。
这里我把整个词典匹配的工具写成一个类（应该是工程的基本操作了），主要两个成员函数，初始化和预测。
3.1 初始化 初始化其实很简单，就是加载词典。首先来看我的词典是一个什么结构，样例是这样的：
1 2 3 4 5 6 7 五哈 VarietyShow+++哈哈哈哈哈 哈哈哈哈哈 VarietyShow+++哈哈哈哈哈 故宫 Attraction+++故宫博物院 南京 City+++南京市 南京博物馆 Attraction+++南京博物馆 斗罗大陆 Novel+++斗罗大陆 斗罗大陆 Carton+++斗罗大陆
总的来说两列，用’\t’分隔，第一列是可匹配的词，第二列是对应词汇内部的信息，后续定义为”slot_info”这里定义是两列，用’+++’分隔（linux环境一般用’\001’这种人为输入几乎不可能看见的词汇），第一列是词汇类型或者叫做槽位名，第二列该词语正式的名字，后续可以用来做精确查询。
init部分就是加载词典了，来看看代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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，因为一个词可能对应很多种不同的实体，例如“斗罗大陆”既是小说又是动漫，那这里当然是要存两个元素的。另外为了保护词典的合法性，避免出现异常数据而报错，所以肯定是要有一些约束过滤的。
这样加载好的词典就是这样的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 { '五哈': [{ '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这门语言原生的东西的理解。
3.2 预测部分 先上代码再来聊。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 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是“我想去南京的南京博物馆”，来看匹配查询的过程：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 我想去南京的南京博物馆 想去南京的南京博物馆 去南京的南京博物馆 南京的南京博物馆 京的南京博物馆 的南京博物馆 南京博物馆 -- 识别到南京博物馆-Attraction实体。 我想去南京的 想去南京的 去南京的 南京的 京的 的 我想去南京 想去南京 去南京 南京 -- 识别到南京-City实体 我想去 想去 去 我想 想 我
最大逆向匹配的一个假设是只取最长的实体，所以南京博物馆出来了而这里的南京没有单独出来，大家可以理解到这里的匹配流程。
另外一个细节是在匹配到词典后，直接就把需要输出结果的结构就整理好了，完成遍历后就可以直接给出答案，还是“我想去南京的南京博物馆”，这里提取的结果是这样的：
1 2 3 4 5 6 7 8 9 10 11 12 13 [{ '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 }]
4. 小结 坑终究是填上了，词典匹配整个组件代码也不复杂，结构上也比较简单（不排除以后你还要做一些别的优化，例如热更新之类的），只是比较考虑自己写代码的功底。后续，有了这个工具，词典匹配做起来后，就能cover更多的问题，尤其是简单、高频的问题。
再留个坑，词典具体可以怎么来，怎么挖掘，找个时间详细聊聊~
最后送上完整版代码，大家可以根据自己的需求进行修改。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 # 使用最大逆向匹配进行提槽 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)
