開發與維運

巧用 Trie 樹實現搜索引擎關鍵詞提示功能

原文鏈接

一、前言

我們幾乎每天都在用搜索引擎搜索信息,相信大家肯定有注意過這樣一個細節:當輸入某個字符的時候,搜索引框底下會出現多個推薦詞,如下,輸入「python」後,底下會出現挺多以python 為前綴的推薦搜索文本,它是如何實現的呢?
image.png
文章標題已經給出答案了,沒錯,用 Trie 樹。本文將會從以下幾個方面來簡述一下 Trie 樹的原理,以讓大家對 Trie 樹有一個比較全面的認識。

  • 什麼是 Trie 樹
  • Trie 樹的實現
  • 如何實現搜索字符串自動提示
  • 再談 Trie 樹

相信大家看了肯定有收穫

二、什麼是 Trie 樹

Trie 樹,又稱前綴樹,字典樹,或單詞查找樹,是一種樹形結構,也是哈希表的變種,它是一種專門處理字段串匹配的數據結構,用來解決在一組字符串集合中快速查找某個字符串的問題,主要被搜索引擎用來做文本詞頻的統計。
畫重點:快速字符串匹配,詞頻統計。
1、快速字符串匹配
假設想要在一串字符串如 a, to, tea, ted, ten, i, in, inn 中多次查找某個字符串是否存在,該怎麼做呢,很直觀的想法是用 hash,這種確實沒問題,如果 hash 函數設計得好的話,如果 hash 函數設計得不好,很容易產生衝突,進而退化成字符串間的比較,另外,在英文中其實有很多單詞有共同的前綴,比如中 tea, ted, ten 這三個單詞有共同的前綴 te, 如果用 hash 的話,無疑這些共同前綴相當於重複存了多次,比較費空間。
如果用 Trie 樹的話,能解決以上兩個問題,先來看下 trie 樹是如何表示的,以以上的一組字符串 a, to, tea, ted, ten, i, in, inn 為例,它們組成的 Trie 樹如下:
image.png
如果要查找某個字符串的話,從根節點出發,每次取待查找字符串中的一個字符往下遍歷,即可找到,可以看到它的查找時間複雜度為 O(N) (N 為字符串長度),還是很快的(英文單詞普遍比較短)。
2、詞頻統計
只要在每個結點上加一個計數器,遍歷單詞時,所有字符串的最後一個字符對應結點的計算器都加 1, 如以 a,an,and 構造的 Trie 樹如下,每個結點計算器都為 1,代表以此結點存儲字符為終止字符的單詞分別為 1 個。
image.png
從前面 Trie 樹的圖解可以看到 Trie 樹的本質就是前綴樹,通過提取出字符串的公共前綴(如果有的話),以達到快速匹配字符串的目的。
通過前綴匹配,使用 Trie 樹查找字符串的效率大大提高!
從以上 Trie 樹的圖解我們可以得出 Trie 樹的以下幾個特點

  1. 根節點不包含字符,除根節點外每個節點只包含一個字符
  2. 從根節點到某一節點,路徑上經過的字符連接起來,為該節點對應的字符串。如上圖中從根節點到結點 o,經過的字符為「t」和「o」,所以它表示單詞 to。
  3. 每個節點的所有子節點包含的字符都不相同,這一點也就保證了相同的前綴能夠得到複用。

那麼  Trie 樹該怎麼表示呢

三、Trie 樹的實現

從上文我們對 Trie 樹的剖析可以很明顯地看到 Trie 樹是一顆多叉樹,那麼多叉樹該怎麼表示呢,假設字符串都是由 26 個小寫字母組成,則顯然 Trie 樹應該是一顆 26 叉樹,每個節點包含 26 個子節點,如下
image.png
上圖可以看出,26 個子節點我們可以用大小為 26 的數組表示,所以 Trie 樹表示如下

/**
 * 26 個字母
 */
static final int ALPHABET_SIZE = 26;
/**
 * Trie 樹的節點表示
 */
static class TriedNode {
    /**
     * 根節點專用,存儲 "/"
     */
    public char val;
    /**
     * 以此結點字符為終止字符的字符串的個數
     */
    public int frequency;
    /**
     * 節點指向的子節點
     */
    TriedNode[] children = new TriedNode[ALPHABET_SIZE];
    public TriedNode(char val) {
        this.val = val;
    }
}
/**
 * Trie 樹
 */
static class TrieTree {
    private TriedNode root = new TriedNode('/'); // 根節點
}

Trie 樹的表現有了,現在我們來看下 Trie 樹的兩個主要操作

  1. 根據一組字符串構造 Trie 樹
  2. 在 Trie 樹中查找字符串是否存在

先來看如何根據一組字符串構造 Trie 樹,首先如何根據一個單詞來構造 Trie 樹呢,假設我們以單詞 「and」 為例來看下 Trie 樹的表現形式
image.png
注:圖中的數字表示數組的元素位置
可以看到構建 Trie 樹的主要步驟如下

  1. 構建根節點,此時根節點存有一個元素大小為 26 的數組
  2. 遍歷字符串「and」
  3. 遍歷第一個字符 a 時,將上述數組的第一個元素賦值為一個 TriedNode 實例(假設其名為 A)
  4. 當遍歷第二個字符 n 時,將 A 結點 TriedNode 數組下標為 n-a = 13 (a 的 ascii 為 97,n 的 ascii 碼為 110) 的元素賦值為一個 TriedNode 實例(假設其名為 N)
  5. 同理,當遍歷第三個字符 d 時,將 N 結點 TriedNode 數組的第 4 個元素(下標為 3)賦值為一個 TriedNode 實例(假設其名為 D),同時也將其結點的 frequency 加一,代表以此字符為終止字符的字符串多了一個。

由以上分析不難寫出根據字符串構建 Trie 樹的代碼,如下

/**
 * Trie 樹
 */
static class TrieTree {
    private TriedNode root = new TriedNode('/'); // 根節點
    /**
     * 以 String 為條件構建 Trie 樹
     * @param s
     */
    public void insertString(String s) {
        TriedNode p = root;
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            int index  = c-'a';
            if (p.children[index] == null) {
                p.children[index] = new TriedNode(c);
            }
            p = p.children[index];
            //Process char
        }
        p.frequency++;
    }
}

Trie 樹構造好了,再在 Trie 樹中查找某字符串是否存在就簡單很多了,遍歷字符串,查看每個字符在相應層級的數組位置的元素是否為空即可,如果是,說明不存在,如果不是,則繼續遍歷字符查找,直到遍歷完成,代碼如下

/**
 * 查找字符串是否在原字符串集合中
 * @param s
 * @return boolean
 */
public boolean findStr(String s) {
    TriedNode p = root;
    for (int i = 0; i < s.length(); i++){
        // 當前被遍歷的字符
        char c = s.charAt(i);
        int index  = c-'a';
        if (p.children[index] == null) {
            // 如果字符對應位置的數組元素為空,說明肯定不存在此字符,終止之後的字符遍歷
            return false;
        }
        // 如果存在,則繼續往後遍歷字符串
        p = p.children[index];
    }
    return true;
}

由於在節點中也用 frequency 保存了單詞數,所以如果在 Trie 樹中最終發現字符串存在,也可以隨便查找出此字符串的個數。

四、如何實現搜索字符串自動提示功能

有了 Trie 樹,相信大家不難解決開篇的這個問題,首先搜索引擎根據用戶的搜索詞構建一顆 Trie 樹,假設這個搜索詞庫是 a, to, tea, ted, ten, i, in, inn,則構建的 Trie 樹為
image.png
那麼當用戶在搜索框輸入「te」的時候,根據 Trie 樹的特性得知以  te 為前綴的字符串有 tea,ted,ten,則應該在搜索框提示詞中展示這三個字符串。這裡有一個小問題,一般搜索框只會展示 10 個搜索詞,但以用戶輸入字符串為前綴的字符串可能遠超 10 次,到底該展示哪 10 個呢,最簡單的規則是展示搜索次數最多的 10 個字符串,於是問題就轉化為了 TopK 問題,維護一個有 10 個元素的小頂堆,步驟如下

  1. 先根據用戶輸入的前綴在樹中找出含有此前綴的所有字符串
  2. 我們知道在節點中保存了字符串的被搜索次數,所以利用小頂堆即可算出被搜索次數最多的 10 個字符串,即可得最終展示給用戶的提示詞。

注意:這裡的求 TopK 要用是小頂堆,不是大頂堆哦,在搜索引擎背後的經典數據結構和算法_這篇文章中有讀者提出了疑問,不要搞混了,小頂堆是求最大的 Top K 值,大頂堆是求最小的 TopK 值,由於我們要求最多的前 10 個搜索詞,所以應該是用小頂堆)。_
這樣就解決了,考慮以下現象:我們在輸入搜索詞的時候,搜索引擎給出的提示詞可能並不是以用戶輸入的字符串為前綴的
image.png
如圖示:搜索引擎給出的搜索關鍵字並不包含有「brekfa」 前綴。
這種又是怎麼實現的呢,它實際上用到了字符串編輯距離的思想,所謂字符串編輯距離是說一個字符串可以通過增刪改查字符來變成另外一個字符串
image.png
_如圖示: brekfa 添加 a 之後變成了  breakfa_
顯然所作的增刪改查次數越少,效率越高,經過最少的字符中編輯變成另一個合法的字符串後,就以此字符串為前綴去 Trie 樹中查找提示詞。
當然了,像 Google 這樣的搜索引擎要實時顯示這些結果,背後肯定經過了很多改造。不過原理都大同小異。

五、再談 Trie 樹

從前面的介紹中我們可以看到使用 Trie 樹確實在能在快速查找字符串與詞頻統計上發揮重要作用,但天下沒有免費的午餐,如果字符集比較大的話,用 Trie 樹可能會造成空間的浪費,以上文中構建的 Trie 樹為例
image.png
每個結點維護一個 26 個元素大小的數組,共有 4 個數組,也就是分配了 26 x 4 = 104  個元素的空間,但實際上只有三個元素空間(a,n,d)被分配了,浪費了 101 個空間,空間利率率很低,所以一般更適用於字符串前綴重複比較多的情況,當然也可以考慮對 Trie 樹進行如下縮點優化,能節省一些空間
image.png
當然這麼優化後也增加了代碼的編碼難度,所以要視情況而定。
另外如果用 Trie 樹的話,一般需要我們自己編碼,對工程師的編碼能力要求較高,所以是否用 Trie 樹我們一般建議如下:

  1. 如果是字符串的精確匹配查找,我們一般建議使用散列表或紅黑樹來解決,畢竟很多語言的類庫都有現成的,不需要自己實現,拿來即用
  2. 如果需要進行前綴匹配查找,則用 Trie 樹更合適一些

六、總結

本文通過搜索引擎字符串提示簡要地概述了其實現原理,相信大家應該理解了,需要注意的是其使用場景,更推薦在需要前綴匹配查找的時候用 Trie 樹,否則像一般的精確匹配查找等更推薦用散列表和紅黑樹這些很成熟的數據結構,畢竟這兩數據結構實現一般在類庫中都是實現了的,不需要自己實現,儘量不要重複造輪子。

作者 | 碼海
來源 | 碼海

Leave a Reply

Your email address will not be published. Required fields are marked *