Trie 數據結構：被忽視的寶石

從我們作為程序員的第一天起，我們就都在處理數據結構：數組、鍊錶、樹、集合、堆棧和隊列是我們的日常夥伴，經驗豐富的程序員知道何時以及為什麼要使用它們。 在本文中，我們將看到一個經常被忽視的數據結構trie是如何在具有特定功能的應用程序領域（如文字遊戲）中真正發揮作用的。

文字遊戲作為特里的例子

首先，讓我們考慮一個簡單的單詞拼圖：在 4x4 字母板上找到所有有效單詞，水平、垂直或對角連接相鄰的字母。 例如，在下面的板上，我們看到字母“W”、“A”、“I”和“T”連接起來形成單詞“WAIT”。

尋找所有有效詞的簡單解決方案是從左上角開始探索棋盤，然後將深度優先移動到更長的序列，再次從第一行的第二個字母開始，依此類推。 在 4x4 棋盤中，允許垂直、水平和對角線移動，有 12029640 個序列，長度從 1 到 16 個字符不等。

現在，我們的目標是找到實現這個有效詞檢查器的最佳數據結構，即我們的詞彙表。 需要記住的幾點：

• 從邏輯的角度來看，我們只需要每個單詞的一個副本，即我們的詞彙表是一個集合。
• 對於任何給定的單詞，我們需要回答以下問題：
  • 當前字符序列是否包含有效單詞？
  • 有沒有以這個序列開頭的更長的單詞？ 如果沒有，我們可以放棄我們的深度優先探索，因為更深入不會產生任何有效的單詞。

為了說明第二點，請考慮以下棋盤：探索後續動作沒有意義，因為字典中沒有以“ASF”開頭的單詞。

我們希望我們的數據結構能夠盡快回答這些問題。 ~O(1) 訪問時間（用於檢查序列）將是理想的！

我們可以像這樣定義 Vocabulary 接口（參見此處獲取 GitHub 存儲庫）：

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Trie 數據結構與替代方案

實現contains()方法需要一個支持數據結構，它可以讓您有效地找到元素，而isPrefix()方法需要我們找到“下一個更大的元素”，即我們需要以某種方式保持詞彙表的排序。

我們可以很容易地從候選列表中排除基於哈希的集合：雖然這樣的結構可以讓我們對contains()進行恆定時間檢查，但它在isPrefix()上的表現會很差，在最壞的情況下需要我們掃描整個放。

出於完全相反的原因，我們也可以排除排序的鍊錶，因為它們需要至少掃描列表直到大於或等於搜索詞或前綴的第一個元素。

兩個有效的選項是使用排序的數組支持列表或二叉樹。
在排序後的數組支持列表上，我們可以使用二進制搜索來查找當前序列（如果存在）或下一個更大的元素，成本為O(log2(n)) ，其中n是字典中的單詞數。

我們可以使用標準的java.util.ArrayList和java.util.Collections.binarySeach實現一個數組支持的詞彙表，它總是保持這樣的順序：

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

如果我們決定使用二叉樹，實現可能會更短、更優雅（同樣，這裡是代碼的鏈接）：

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

在這兩種情況下，我們可以預期每種訪問方法（ contains()和isPrefix() ）的O(log n)性能。 至於空間要求，array-backed implementation 和 tree-backed implementation 都需要O(n+M)其中 n 是字典中的單詞數，M 是字典的字節大小，即長度的總和字典中的字符串。

Trie 應用程序：何時以及為何使用 Trie

對數性能和線性內存還不錯。 但是我們的應用程序領域還有一些特徵可以使我們獲得更好的性能：

• 我們可以放心地假設所有單詞都是小寫的。
• 我們只接受 az 字母——無標點符號、連字符、重音符號等。
• 該詞典包含許多屈折形式：複數、共軛動詞、複合詞（例如，house –> housekeeper）。 因此，許多詞共享同一個詞幹。
• 單詞的長度是有限的。 例如，如果我們在 4x4 板上工作，所有超過 16 個字符的單詞都可以被丟棄。

這就是 trie（發音為“try”）的用武之地。但是 trie 到底是什麼？ 嘗試是被忽視的數據結構，在書本中可以找到，但在標準庫中很少見。

對於動機，讓我們首先考慮計算機科學的典型代表：二叉樹。 現在，當我們分析二叉樹的性能並說操作x為O(log(n))時，我們一直在談論以 2 為底的 log。但是如果我們使用三叉樹而不是二叉樹呢？每個節點都有三個孩子（或者，三個的扇出）。 然後，我們將討論以 3 為基數的日誌。（這是一種性能改進，儘管只是一個常數因素。）本質上，我們的樹會變得更寬但更短，並且我們可以執行更少的查找，因為我們不需要下降太多很深。

更進一步，如果我們有一棵樹的扇出等於我們數據類型的可能值的數量呢？

這就是 trie 背後的動機。 正如您可能已經猜到的那樣，trie 確實是一棵樹，可以說是一棵 trie 樹！

但是，與用於排序字符串的大多數二叉樹相反，那些將整個單詞存儲在其節點中的二叉樹，trie 的每個節點都包含一個字符（甚至不是那個，我們很快就會看到）和最大扇出等於字母表的長度。 在我們的例子中，字母的長度是 26； 因此，trie 的節點的最大扇出為 26。而且，雖然平衡二叉樹的深度為log2(n) ，但 trie 的最大深度等於單詞的最大長度！ （同樣，更寬但更短。）

在一個 trie 中，具有相同詞幹（前綴）的單詞共享對應於詞幹的內存區域。

為了可視化差異，讓我們考慮一個由五個單詞組成的小字典。 假設希臘字母表示指針，注意在 trie 中，紅色字符表示持有有效單詞的節點。

Java Trie 實現

正如我們所知，在樹中，指向子元素的指針通常使用左右變量來實現，因為最大扇出固定為兩個。

在索引 26 個字母的字母表的 trie 中，每個節點有 26 個可能的子節點，因此有 26 個可能的指針。 因此，每個節點都有一個包含 26 個（指向）子樹的數組，其中每個值可以為空（如果沒有這樣的子節點）或另一個節點。

那麼，我們如何在 trie 中查找一個單詞呢？ 這是給定String s的方法，它將識別對應於單詞最後一個字母的節點（如果它存在於樹中）：

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

LOWERCASE.getIndex(s.charAt(i))方法只返回字母表中第 i 個字符的位置。 在返回的節點上，一個布爾屬性node表示該節點對應於一個單詞的最後一個字母，即上例中標記為紅色的字母。 由於每個節點都有一個子節點數量的計數器，如果這個計數器是正數，那麼字典中有更長的單詞以當前字符串為前綴。 注意：節點實際上並不需要保留對它對應的字符的引用，因為它隱含在它在 trie 中的位置中。

分析性能

使 trie 結構在這些情況下真正表現良好的原因是查找單詞或前綴的成本是固定的，並且僅取決於單詞中的字符數，而不取決於詞彙表的大小。

在我們的特定領域中，由於我們有最多 16 個字符的字符串，因此需要 16 個步驟才能找到詞彙表中的單詞，而任何否定答案，即單詞或前綴不在 trie 中，都可以獲得最多16個步驟！ 考慮到我們之前在計算基於數組的排序列表和隱藏在字符串比較中的樹的運行時間複雜度時忽略了字符串的長度，我們也可以在這裡忽略它並安全地聲明查找已完成在O(1)時間內。

考慮到空間要求（並記住我們已經用M表示字典的字節大小），如果沒有兩個字符串共享前綴，則在最壞的情況下，trie 可能有M個節點。 但是由於我們觀察到字典中存在高度冗餘，因此需要進行大量壓縮。 示例代碼中使用的英文字典為 935,017 字節，需要 250,264 個節點，壓縮率約為 73%。

然而，儘管如此，即使是壓縮的 trie 通常也需要比樹或數組更多的內存。 這是因為，對於每個節點，至少需要 26 x sizeof(pointer)字節，加上對象和其他屬性的一些開銷。 在 64 位機器上，每個節點需要超過 200 個字節，而字符串字符需要一個字節，如果我們考慮 UTF 字符串，則需要兩個字節。

嘗試和性能測試

那麼，性能呢？ 詞彙實現在兩種不同的情況下進行了測試：檢查 20,000,000 個隨機字符串並在從同一單詞列表隨機生成的 15,000 個板上查找所有單詞。

分析了四種數據結構：一個數組支持的排序列表、一個二叉樹、上面描述的 trie，以及一個使用與字符本身的字母索引相對應的字節數組的 trie（一個較小且易於實現的性能優化）。 以下是結果，以毫秒為單位：

解決棋盤的平均移動數為 2,188。 對於每一步，都會進行一次單詞查找和前綴查找，即為了檢查所有棋盤，執行了超過 32M 單詞查找和 32M 前綴查找。 注意：這些可以一步完成，為了在說明中清晰起見，我將它們分開。 一步將它們壓實可以將解決板的時間減少近一半，並且可能會更傾向於嘗試。

如上所示，即使在使用字符串時，使用 trie 的單詞查找性能更好，使用字母索引時甚至更快，後者的執行速度是標準二叉樹的兩倍多。 解決板的差異更加明顯，快速 trie-alphabet-index 解決方案的速度是列表和樹的四倍以上。

包起來

trie 是一種非常專業的數據結構，它比樹和列表需要更多的內存。 但是，當應用特定的域特徵時，例如字符串第一部分中有限的字母和高冗餘，它可以非常有效地解決性能優化問題。

參考

可以在 Robert Sedgewick 的著作“算法，第 4 版”的第 5 章中找到對嘗試和字母表的廣泛解釋。 普林斯頓大學的配套網站有實現 Alphabet 和 TrieST 的代碼，比我的例子更廣泛。

也可以在 Wikipedia 上找到各種語言的 trie 和實現的描述，您也可以查看這個波士頓大學 trie 資源。