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

原文地址

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

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

字頻統計：給出一段文本，統計其中指定單詞出現的頻數。

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

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

當前前綴為空，對當前節點執行操作2。否則，取出當前單詞的首字符，標記為X，遍歷當前節點的子節點，如果X存在于子節點N中，將N標記為當前節點，將剩余字符串標記為當前單詞，重復操作1；如果X不存在于子節點中，返回None。

以當前節點為根節點，進行深度優先搜索，取得當前節點所有子樹下的所有單詞。

實現的偽代碼如下：

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

具體程序以及測試例子放在gist上，可以在這里找到。測試了一下，兩千多個單詞，尋找共同前綴的單詞，速度還是蠻快的。

有時候我們需要統計一篇文章中一些單詞出現的次數，這個時候用字典樹可以很方便的解決這個問題。

在字典樹的簡單實現中，我們設計的節點數據結構如下：

圖1. 用list實現字典樹

只要對這里節點的數據結構稍作修改，就可以用于統計字頻了。把原來數據結構中的標記位改為頻數位，即保存該單詞出現的次數。然后，再把原有字典樹實現中的插入操作和查找操作稍微改動，就可以實現字頻統計功能了。

插入操作：將單詞標記為當前單詞，將根節點標記為當前節點，執行操作1：

當前單詞為空，當前節點單詞出現頻數加1，終止操作；否則取出當前單詞的首字符記為X，遍歷當前節點的子節點：如果X存在于子節點N，將剩余字符標記為當前單詞，將N標記為當前節點，重復操作1，如果X不存在于當前節點的子節點中，那么進入操作2。

取出當前單詞的首字符記為X，新建一個節點M存儲X，M的父節點為當前節點。剩余字符串記為當前單詞，如果當前單詞為空，M節點單詞出現頻數加1，終止操作；否則，將M標記為當前節點，重復操作2。

查詢操作：將單詞標記為當前單詞，將根節點標記為當前節點，執行操作1：

當前單詞為空，返回當前節點字頻數，即為該單詞出現的次數。否則，取出當前單詞的首字符，標記為X，遍歷當前節點的子節點，如果X存在于子節點N中，將N標記為當前節點，將剩余字符串標記為當前單詞，重復操作1；如果X不存在于子節點中，返回0。

實現偽代碼如下，插入操作如下：

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

具體程序以及測試例子放在gist上，可以在這里找到。