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

原文地址

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

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

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

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

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

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

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

實(shí)現(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

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

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

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

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

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

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

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

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

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

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

實(shí)現(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

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