Trie|如何用字典樹實現搜索引擎的關鍵詞提示功能

Trie字典樹

Trie字典樹又稱前綴樹,顧名思義,是查詢前綴匹配的一種樹形數據結構

可以分為插入(創建) 和 查詢兩部分。參考地址極客時間

下圖為插入字符串的過程:

創建完成后,每個字符串最後一個字母標記為終結點(圖中显示為紅色)

下圖為查詢字符串:“her”的過程:綠色箭頭表示查詢路徑
我們將要查找的字符串分割成單個的字符 h,e,r,一個一個查詢

下圖為查詢字符串:“he”的過程:綠色箭頭表示查詢路徑
因為‘e’不是終結點,所以不能完全匹配上。

Trie字典樹的實現

1.首先是字典樹 數據結構定義的代碼實現

樹形結構,類比於二叉樹的存儲嘛,每個結點兩條分支(二叉樹);
而字典樹,每個節點可以最多有 26個分支(存儲英文字母)。

1-1二維數組存儲字母

int trie[MAX_NODE][26];//MAX_NODE表示結點數量,每個結點有26個字母結點
int k;

MAX_NODE表示結點數量,每個結點有26個字母結點
Trie[i][j]的值是0,表示trie樹中i號節點,並沒有一條連出去的邊滿足邊上的字符標識是字符集中第j個字符(從0開始);
trie[i][j]的值是正整數x表示trie樹中i號節點,有一條連出去的邊滿足邊上的字符標識是字符集中第j個字符,並且
這條邊的終點是x號節點。

1-2鏈表
我這裏用C++中的vector實現,

vector< pair<char, int> > trie[MAX_NODE];
int k;

也可以寫一個真正的鏈表,包含二元組字段<char,int>型的對應關係

1-3hash,

map<char, int> trie[MAX_NODE];

每次我們想找i號節點有沒有標識
是某個字符ch的邊時,只要看trie[i][ch]的值即可
但是實際上map時空複雜度的常數都比較大

2.插入 和 查詢 兩個函數的代碼實現

插入 查詢 實際上是類似的,就是從樹的根開始往下遍歷,

2-1插入:從樹的根開始往下遍歷,到達一個結點,沒有這個字母就插入到這個結點下,作為這個結點的子節點

基於二維數組結構的插入功能實現

代碼的第6~8行,一開始trie[][]被初始化為0,保證每個節點被創建出來時,都沒有子節點。K初
始化為1表示一開始只有1個節點,也就是0號節點根節點。Color是用來標記一個節點是不是終結
點。Color[i]=1標識i號節點是終結點。
第9~21行是插入函數insert(w),w是字符指針,實際上可以看作是一個字符串。
第11行是p從0號節點開始。
第12~19行是依次插入w的每一個字符。
第13行是計算w[i]是字符集第幾個字符,這裏我們假設字符集只包含26個小寫字母。
第14~17行是如果p沒有連出標識是w[i]的邊,那麼就創建一個。這裏新創建的節點一定就是k號節
點。所謂創建新節點實際上也沒什麼可創建的,新節點就是個編號。所以我們直接令trie[i][c]=k
即可,然後將k累加1,整個創建過程就完成了。
第18行是沿着標記着w[i]的邊移動到下一個節點。
最後第20行,是將最後到達的節點p標記為終結點。

2-2查詢:從樹的根開始往下遍歷,查看是否匹配上當前正在查的單詞
基於二維數組結構的查詢功能實現

第24行是從p=0也就是根節點開始。
第25~29行是枚舉s的每一個字符。
第26行是計算當前字符s[i]在字符集的序號。
第27行是判斷p節點有沒有連出標識s[i]字符的邊,如果沒有,說明現在無路可走,直接返回0;如
果有的話,
第28行就是移動到下一個節點。如果整個循環結束還沒有return 0,那就說明成功沿着s的每一個
字符到達了p節點。這時只要判斷p節點是不是終結點即可,也就是第30行的代

3.完整代碼C++版

public class Trie {
  private TrieNode root = new TrieNode('/'); // 存儲無意義字符

  // 往 Trie 樹中插入一個字符串
  public void insert(char[] text) {
    TrieNode p = root;
    for (int i = 0; i < text.length; ++i) {
      int index = text[i] - 'a';
      if (p.children[index] == null) {
        TrieNode newNode = new TrieNode(text[i]);
        p.children[index] = newNode;
      }
      p = p.children[index];
    }
    p.isEndingChar = true;
  }

  // 在 Trie 樹中查找一個字符串
  public boolean find(char[] pattern) {
    TrieNode p = root;
    for (int i = 0; i < pattern.length; ++i) {
      int index = pattern[i] - 'a';
      if (p.children[index] == null) {
        return false; // 不存在 pattern
      }
      p = p.children[index];
    }
    if (p.isEndingChar == false) return false; // 不能完全匹配,只是前綴
    else return true; // 找到 pattern
  }

  public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
    public boolean isEndingChar = false;
    public TrieNode(char data) {
      this.data = data;
    }
  }
}

Trie字典樹的時間複雜度 與 缺點

插入的時間複雜度:O(N),N為所有待插入字符串的長度之和
查詢的時間複雜度:O(K),K為待查詢字符串的長度

占內存:如果用二維數組實現,每個節點就會額外需要 26*8=208 個字節
優化思路:將每個節點中的數組換成其他數據結構,比如有序數組(可以二分查找)、跳錶、散列表、紅黑樹等。

Trie變體,縮點優化:對只有一個子節點的節點,而且此節點不是一個串的結束節點,可以將此節點與子節點合併

Trie字典樹的實際應用

1.搜索引擎輸入框關鍵詞提示

因為字典樹是查找 “與前綴匹配的字符串”,又稱為前綴樹。
關鍵詞提示就是 查尋找前綴匹配的前綴合適關鍵詞,當然還有更複雜的關鍵詞排名問題,這裏不再展開。

2.自動補全功能,如:IDE編譯器自動補全,輸入法自動補全等

原理與搜索引擎類似。

3.敏感詞過濾系統

4.其它

Trie在面試與算法競賽中的例題

1.hihoCoder1014

hihoCoder1014

解題思路:Trie字典樹

首先我們把集合中的N個字符串都插入到trie中。
對於每一個查詢s我們在trie中查找s,如果查找過程中無路可走,那麼一定沒有以s為前綴的字符串。
如果最後停在一個節點p,那我們就要看看以p為根的子樹里一共有多少終結點。
終結點的數目就是答案。

但是如果我們每次都遍歷以P為根的子樹,那時間複雜度就太高了。解決的辦法是用空間換時間,我們增加一個數組intcnt[MAX_NODE]
cnt[i]記錄的是以i號節點為根的子樹中,有幾個終結點。
然後我們每次insert一個字符串的時候,順便就把沿途的節點的cnt值都+1。
這樣就不用每次遍歷以P為根的子樹,而是直接輸出cnt[P]即可。

代碼:

2.hihoCoder1107微軟面試題

hihoCoder1014

其實就是找一個節點p,滿足以p為根的子樹中的終結點不多於5個,同時以p的父節點為根的子樹中的終結點大於5個。
和上題一樣用cnt數組標記,之後dfs查找終結點的數目

3.Trie應用在整數xor異或值最大的題目

給定一個包含N個整數的集合S={A1, A2, A3, … AN}。然
後有M個詢問,每次詢問給定一個整數X,讓你找一個Ai使得Ai xor X的值最大。

首先我們知道一個整數可以用二進製表示成一個01串。比如3=(011)2, 5=(101)2, 4=(100)2……。
我們假設輸入的整數都在0~2^32-1之間,於是我們可以用一個長度是32位的01串表示一個整數。
然後對於給定的N個整數A1, A2, A3, … AN,我們把它們對應的01串都插入到一個trie中。注意這裏字符集只有0和1,所以整個trie是一棵二叉樹。

下面我們舉一個例子,為了描述方便,我們假設整數都在0~7之間,也就是可以用3位01串表示。
現在假設S={1, 2, 7},也就是說我們要在Trie中插入{001, 010, 111}:

這時假設我們要查詢x=4,也就是哪個數和4異或結果最大?4=(100)2,
我們的做法是在trie樹中,盡量與4的二進制位反着走。
比如4的第一位(最高位)是1,我們從0出發第一步就盡量沿着0走。因為我們要異或和最大,01相反才能異或值是1。
並且這一步是可以貪心的,也就是說如果有相反的邊,那麼我們一定沿着這條邊走。因為最高位異或得1的話,即便後面都是0, 10000…000也要比最高位是0,後面都是1的011111…111大。
所以我們第一步沿着標識是0的邊,移動到了1號節點;4第二位是0,所以我們沿着標識是1的邊移動到4號節點;
4的第三位是0,但是4號節點沒有標識是1的邊,所以我們也只好沿着標識是0的邊移動到5號節點。
已經到了終結點,所以5號節點對應的A2=(010)2=2就是我們要求的答案,A2 xor 4 = 6是最大的。

【精選推薦文章】

自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司,幫您輕鬆架站!

評比前十大台北網頁設計台北網站設計公司知名案例作品心得分享

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

您可能也會喜歡…