摘要：原文地址在簡單字典樹的實現(xiàn)一文中，我們以單詞輸入自動提示為引子，簡單介紹了字典樹的實現(xiàn)。前綴匹配本文講述前綴匹配的字典樹實現(xiàn)方案。在簡單字典樹的實現(xiàn)一文中，我們已經(jīng)實現(xiàn)了字典樹的基本操作，這里只需要再加上一個前綴匹配方法即可。

原文地址

在簡單字典樹(Trie)的實現(xiàn)一文中，我們以單詞輸入自動提示為引子，簡單介紹了字典樹的實現(xiàn)。那么，字典樹到底可以用于哪些場合呢？

前綴匹配：給定字典庫，輸入一段字符，返回以該字符串為前綴的所有單詞。

字頻統(tǒng)計：給出一段文本，統(tǒng)計其中指定單詞出現(xiàn)的頻數(shù)。

本文講述前綴匹配的字典樹實現(xiàn)方案。仍然假設(shè)我們有以下單詞：apps apple cook cookie cold，當(dāng)我們想獲得以co為前綴的單詞時，只需要在字典樹中依次找到c、o節(jié)點，然后搜索o節(jié)點的所有子樹，取出其中的單詞即可。

在簡單字典樹(Trie)的實現(xiàn)一文中，我們已經(jīng)實現(xiàn)了字典樹的基本操作，這里只需要再加上一個前綴匹配方法即可。具體流程如下，將前綴字符串標(biāo)記為當(dāng)前前綴，將根節(jié)點標(biāo)記為當(dāng)前節(jié)點，執(zhí)行操作1：

當(dāng)前前綴為空，對當(dāng)前節(jié)點執(zhí)行操作2。否則，取出當(dāng)前單詞的首字符，標(biāo)記為X，遍歷當(dāng)前節(jié)點的子節(jié)點，如果X存在于子節(jié)點N中，將N標(biāo)記為當(dāng)前節(jié)點，將剩余字符串標(biāo)記為當(dāng)前單詞，重復(fù)操作1；如果X不存在于子節(jié)點中，返回None。

以當(dāng)前節(jié)點為根節(jié)點，進行深度優(yōu)先搜索，取得當(dāng)前節(jié)點所有子樹下的所有單詞。

實現(xiàn)的偽代碼如下：

def pre_match_op(current_word, current_node):
    if current_word not empty:
        X = current_word[0]
        if X in current_node.child_node:
            current_word = current_word[1:]
            current_node = child_node
            return pre_match_op(current_word, current_node)
        else:
            return None
    else:
        return pre_match_bfs("", current_node)
        
def pre_match_dfs(keep_char, current_node):
    match_word = []
    for child in current_node.child_node:
        current_pre = pre_str + keep_char
        if child.isword = True:
            word = current_pre + child.char
            match_word.append(word)
        else:
            pass

        pre_match_dfs(current_pre, child)

    return match_word

具體程序以及測試?yán)臃旁趃ist上，可以在這里找到。測試了一下，兩千多個單詞，尋找共同前綴的單詞，速度還是蠻快的。

有時候我們需要統(tǒng)計一篇文章中一些單詞出現(xiàn)的次數(shù)，這個時候用字典樹可以很方便的解決這個問題。

在字典樹的簡單實現(xiàn)中，我們設(shè)計的節(jié)點數(shù)據(jù)結(jié)構(gòu)如下：

圖1. 用list實現(xiàn)字典樹

只要對這里節(jié)點的數(shù)據(jù)結(jié)構(gòu)稍作修改，就可以用于統(tǒng)計字頻了。把原來數(shù)據(jù)結(jié)構(gòu)中的標(biāo)記位改為頻數(shù)位，即保存該單詞出現(xiàn)的次數(shù)。然后，再把原有字典樹實現(xiàn)中的插入操作和查找操作稍微改動，就可以實現(xiàn)字頻統(tǒng)計功能了。

插入操作：將單詞標(biāo)記為當(dāng)前單詞，將根節(jié)點標(biāo)記為當(dāng)前節(jié)點，執(zhí)行操作1：

當(dāng)前單詞為空，當(dāng)前節(jié)點單詞出現(xiàn)頻數(shù)加1，終止操作；否則取出當(dāng)前單詞的首字符記為X，遍歷當(dāng)前節(jié)點的子節(jié)點：如果X存在于子節(jié)點N，將剩余字符標(biāo)記為當(dāng)前單詞，將N標(biāo)記為當(dāng)前節(jié)點，重復(fù)操作1，如果X不存在于當(dāng)前節(jié)點的子節(jié)點中，那么進入操作2。

取出當(dāng)前單詞的首字符記為X，新建一個節(jié)點M存儲X，M的父節(jié)點為當(dāng)前節(jié)點。剩余字符串記為當(dāng)前單詞，如果當(dāng)前單詞為空，M節(jié)點單詞出現(xiàn)頻數(shù)加1，終止操作；否則，將M標(biāo)記為當(dāng)前節(jié)點，重復(fù)操作2。

查詢操作：將單詞標(biāo)記為當(dāng)前單詞，將根節(jié)點標(biāo)記為當(dāng)前節(jié)點，執(zhí)行操作1：

當(dāng)前單詞為空，返回當(dāng)前節(jié)點字頻數(shù)，即為該單詞出現(xiàn)的次數(shù)。否則，取出當(dāng)前單詞的首字符，標(biāo)記為X，遍歷當(dāng)前節(jié)點的子節(jié)點，如果X存在于子節(jié)點N中，將N標(biāo)記為當(dāng)前節(jié)點，將剩余字符串標(biāo)記為當(dāng)前單詞，重復(fù)操作1；如果X不存在于子節(jié)點中，返回0。

實現(xiàn)偽代碼如下，插入操作如下：

def insert(word):
    current_word = word
    current_node = root
    insert_operation_1(current_word, current_node)

def insert_operation_1(current_word, current_node):
    if current_word not empty:
        X = current_word[0]

        if X in current_node.child:
            current_word = current_word[1:]
            current_node = child_node
            insert_operation_1(current_word, current_node)
        else:
            insert_operation_2(current_word, current_node)

    else:
        current_node.count++

def insert_operation_2(current_word, current_node):
    X = current_word[0]
    M.value = x
    M.father = current_node
    current_node.child = M

    current_word = current_word[1:]
    if current_word not empty:
        current_node = M
        insert_operation_2(current_word, current_node)

    else:
        current_node.count++

查詢操作：

def count(word):
    current_word = word
    current_node = root
    return find_opration(current_word, current_node)

def count_opration(current_word, current_node):
    if current_word not empty:
        X = current_word[0]
        if X in current_node.child_node:
            current_word = current_word[1:]
            current_node = child_node
            return find_opration(current_word, current_node)
        else:
            return 0
    else:
        return current_node.count

具體程序以及測試?yán)臃旁趃ist上，可以在這里找到。