我常說的詞典匹配到底怎么做

前言：背景1是應(yīng)霍華德大佬之邀，背景2是這東西我確實(shí)聊的最多卻其實(shí)沒聊清楚這里的細(xì)節(jié)，我的鍋，所以這篇文章無論如何都得寫了。

我已經(jīng)有好多詞都聊過分類、NER甚至匹配問題都可以用詞典來做了，問題是詞典到底怎么做，詞典匹配是怎么做的，具體實(shí)現(xiàn)方法是什么，我卻從來沒聊過，這次給大家一次性說清楚，帶上核心代碼，從而讓大家更好理解和使用。

詞典匹配的背景和場景

詞典匹配是NLP領(lǐng)域在工業(yè)界中非常常見的技術(shù)，尤其在互聯(lián)網(wǎng)領(lǐng)域，主要原因是詞典這個東西經(jīng)常比標(biāo)注樣本更易得，尤其是搜索領(lǐng)域，一方面很多數(shù)據(jù)資源其實(shí)就存在數(shù)據(jù)庫里，直接拿來清晰就能用，另一方面用戶query等數(shù)據(jù)也多容易挖掘，因此詞典匹配成為這個領(lǐng)域落地非常重要的方式，從在線流量視角，絕大部分的流量都是走的詞典匹配，尤其是高頻、簡單的問題，相比之下模型只是個泛化、兜底的功能，加上詞典匹配所特有的靈活性、可控性、高準(zhǔn)確性、高性能等優(yōu)點(diǎn)，詞典匹配絕對是一個實(shí)用且必備的能力。

詞典匹配的實(shí)現(xiàn)思路

要做技術(shù)設(shè)計，肯定是要理解需求。

功能上，給定一批詞典，然后給一個用戶query，找出query中包含的在詞典內(nèi)的詞，例如詞典內(nèi)有“故宮”，則對用戶query“故宮怎么走”，那要把這個“故宮”給匹配出來，復(fù)雜點(diǎn)的還要給出起點(diǎn)終點(diǎn)、正式詞“故宮博物院”等，這就是最基本的功能。其實(shí)這個就是一個NER功能，所以最直接的，詞典匹配就是一個NER任務(wù)。

但是，作為算法工程師，肯定還要考慮準(zhǔn)確性和性能的問題，尤其是性能問題，顯然，詞典是可更新的，可大可小的，小到幾個詞（例如停止詞），大到成千上萬甚至更多，例如人名地名之類的，可枚舉但是數(shù)量非常大，一個一個在詞典里面找，那復(fù)雜度可就非常高了，尤其是當(dāng)詞典非常大的時候，逐字逐詞匹配肯定不現(xiàn)實(shí)。這里非常考驗(yàn)大家解決數(shù)據(jù)結(jié)構(gòu)、復(fù)雜度問題的功力（刷算法題是確認(rèn)有用的！）。

直接說結(jié)論，使用的是最大逆向匹配方法，詞典的存儲則用的dict格式（數(shù)據(jù)結(jié)構(gòu)上，技術(shù)允許的話用trie樹最優(yōu)，hashmap也是沒問題的），在python里面就是用dict了（據(jù)說內(nèi)部key的存儲使用的trie，不確定，有知道的大佬出來聊聊）。

再展開沒啥必要，上代碼聊。

代碼

整塊核心代碼不到50行，非常舒服。

這里我把整個詞典匹配的工具寫成一個類（應(yīng)該是工程的基本操作了），主要兩個成員函數(shù)，初始化和預(yù)測。

初始化

初始化其實(shí)很簡單，就是加載詞典。首先來看我的詞典是一個什么結(jié)構(gòu)，樣例是這樣的：

總的來說兩列，用'\t'分隔，第一列是可匹配的詞，第二列是對應(yīng)詞匯內(nèi)部的信息，后續(xù)定義為'slot_info'這里定義是兩列，用'+++'分隔（linux環(huán)境一般用'\001'這種人為輸入幾乎不可能看見的詞匯），第一列是詞匯類型或者叫做槽位名，第二列該詞語正式的名字，后續(xù)可以用來做精確查詢。

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，因?yàn)橐粋€詞可能對應(yīng)很多種不同的實(shí)體，例如“斗羅大陸”既是小說又是動漫，那這里當(dāng)然是要存兩個元素的。另外為了保護(hù)詞典的合法性，避免出現(xiàn)異常數(shù)據(jù)而報錯，所以肯定是要有一些約束過濾的。

這樣加載好的詞典就是這樣的：

值得注意的是，在預(yù)測階段，無論如何，我們都是要看query的局部內(nèi)容是否在詞典里的，所以一定會出現(xiàn)類似if a in slot_dict的語句，python這么多原生數(shù)據(jù)結(jié)構(gòu)中，只有dict和set兩種類型的運(yùn)行速度最快（且不受到數(shù)據(jù)結(jié)構(gòu)內(nèi)部存儲的數(shù)據(jù)的大小影響），而set由只能存詞不能存slot_info，所以我們就選擇了dict，這是詞典匹配之所以能高性能的核心，這背后是對數(shù)據(jù)結(jié)構(gòu)，對python這門語言原生的東西的理解。

預(yù)測部分

先上代碼再來聊。

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

最大逆向匹配，就是從后面開始，從最大開始逐步縮小范圍，逐個匹配，查看每個局部是否在詞典內(nèi)存在，來看一個例子吧，query是“我想去南京的南京博物館”，來看匹配查詢的過程：

最大逆向匹配的一個假設(shè)是只取最長的實(shí)體，所以南京博物館出來了而這里的南京沒有單獨(dú)出來，大家可以理解到這里的匹配流程。

另外一個細(xì)節(jié)是在匹配到詞典后，直接就把需要輸出結(jié)果的結(jié)構(gòu)就整理好了，完成遍歷后就可以直接給出答案，還是“我想去南京的南京博物館”，這里提取的結(jié)果是這樣的：

[{
'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
}]

小結(jié)

坑終究是填上了，詞典匹配整個組件代碼也不復(fù)雜，結(jié)構(gòu)上也比較簡單（不排除以后你還要做一些別的優(yōu)化，例如熱更新之類的），只是比較考慮自己寫代碼的功底。后續(xù)，有了這個工具，詞典匹配做起來后，就能cover更多的問題，尤其是簡單、高頻的問題。

再留個坑，詞典具體可以怎么來，怎么挖掘，找個時間詳細(xì)聊聊~

最后送上完整版代碼，大家可以根據(jù)自己的需求進(jìn)行修改。