大海撈針：一個漂亮的大規模文本搜索算法教程

當遇到術語“文本搜索”時，人們通常會想到大量文本，這些文本以一種在用戶輸入時可以快速查找一個或多個搜索詞的方式進行索引。 這是計算機科學家的經典問題，存在許多解決方案。

但是相反的情況呢？ 如果事先可用於索引的是一組搜索短語，並且只有在運行時才提供大量文本以供搜索，該怎麼辦？ 這些問題正是這個 trie 數據結構教程試圖解決的問題。

應用

此場景的實際應用是將許多醫學論文與一系列醫學病症進行匹配，並找出哪些論文討論了哪些病症。 另一個例子是遍歷大量司法判例並提取它們所引用的法律。

直接方法

最基本的方法是遍歷搜索短語，並逐個搜索每個短語的文本。 這種方法不能很好地擴展。 在另一個字符串中搜索一個字符串的複雜度為O(n) 。 對m個搜索短語重複此操作會導致糟糕的O(m * n) 。

直接方法的（可能唯一的）優點是易於實現，如以下 C# 片段所示：

 String[] search_phrases = File.ReadAllLines ("terms.txt"); String text_body = File.ReadAllText("body.txt"); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count;

在我的開發機器 [1] 上針對測試樣本 [2] 運行此代碼，我得到了 1 小時 14 分鐘的運行時間——遠遠超出了你需要喝杯咖啡、起身伸展或任何其他藉口的時間開發人員習慣於跳過工作。

更好的方法 - 特里

可以通過多種方式增強前面的場景。 例如，搜索過程可以在多個處理器/內核上進行分區和並行化。 但是通過這種方法實現的運行時間減少（假設完美劃分為 4 個處理器/內核，總運行時間為 20 分鐘）並不能證明編碼/調試增加的複雜性是合理的。

最好的解決方案是只遍歷文本主體一次。 這要求搜索短語在一個結構中被索引，該結構可以與文本主體平行地線性橫向，一次通過，實現O(n)的最終複雜度。

一個特別適合這種情況的數據結構是trie 。 當涉及到搜索問題時，這種通用的數據結構通常被忽視並且不像其他與樹相關的結構那樣著名。

Toptal 之前的嘗試教程很好地介紹了它們的結構和使用方式。 簡而言之，trie 是一棵特殊的樹，能夠以這樣的方式存儲一系列值，即跟踪從根到任何節點的路徑會產生該序列的有效子集。

因此，如果我們可以將所有搜索短語組合到一個樹中，其中每個節點都包含一個單詞，那麼我們將把短語佈置在一個結構中，只要從根向下通過任何路徑進行追踪，就會產生一個有效的搜索短語。

trie 的優點是它顯著減少了搜索時間。 為了便於掌握本 trie 教程的目的，讓我們想像一個二叉樹。 遍歷二叉樹的複雜度為O(log 2 n) ，因為每個節點都分支成兩個，將剩餘的遍歷減半。 因此，三叉樹的遍歷複雜度為O(log 3 n) 。 然而，在 trie 中，子節點的數量由它表示的序列決定，在可讀/有意義的文本的情況下，子節點的數量通常很高。

文本搜索算法

作為一個簡單的例子，讓我們假設以下搜索短語：

• “同一個家庭”
• “不一樣的家庭”
• “分離存在”
• “聯盟成員”

請記住，我們事先知道我們的搜索詞組。 因此，我們首先以 trie 的形式構建索引：

後來，我們軟件的用戶向它展示了一個包含以下文本的文件：

歐洲語言是同一個家族的成員。 他們分開的存在是一個神話。

其餘的很簡單。 我們的算法將有兩個指示符（指針，如果你喜歡的話），一個從我們的 trie 結構中的根節點或“開始”節點開始，另一個從文本正文中的第一個單詞開始。 兩個指標一起移動，一個字一個字。 文本指示符簡單地向前移動，而 trie 指示符沿著匹配詞的軌跡深度遍歷 trie。

trie 指示器在兩種情況下返回開始：當它到達分支的末尾時，這意味著找到了一個搜索短語，或者當它遇到一個不匹配的詞時，在這種情況下沒有找到匹配項。

文本指示符移動的一個例外是當找到部分匹配時，即在一系列匹配之後，在分支結束之前遇到不匹配。 在這種情況下，文本指示器不會向前移動，因為最後一個單詞可能是新分支的開始。

讓我們將這個算法應用到我們的 trie 數據結構示例中，看看它是如何進行的：

可以看到，系統成功找到了“同家人”和“分居”這兩個匹配詞組。

真實世界的例子

對於最近的一個項目，我遇到了以下問題：一位客戶有大量與她的工作領域相關的文章和博士論文，並生成了她自己的短語列表，這些短語代表與同一領域相關的特定標題和規則工作。

她的困境是：給定她的短語列表，她如何將文章/論文鏈接到這些短語？ 最終目標是能夠隨機選擇一組短語，並立即獲得一個文章/論文列表，其中提到了那些準備好抓取的特定短語。

如前所述，解決這個問題有兩個部分：將短語索引到 trie 中，以及實際搜索。 以下部分提供了 C# 中的簡單實現。 請注意，文件處理、編碼問題、文本清理和類似問題不在這些片段中處理，因為它們超出了本文的範圍。

索引

索引操作只是逐個遍歷短語並將它們插入到 trie 中，每個節點/級別一個單詞。 節點用以下類表示：

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = id; } }

每個短語由一個 ID 表示，它可以像一個遞增的數字一樣簡單，並傳遞給以下索引函數（變量 root 是 trie 的實際根）：

 void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

搜索

搜索過程是上面教程中討論的 trie 算法的直接實現：

 void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List<int> foundPhrases = new List<int>(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

表現

此處提供的代碼是從實際項目中提取的，並且為了本文檔的目的進行了簡化。 在同一台機器上再次運行此代碼 [1] 並針對相同的測試樣本 [2] 導致構建 trie 的運行時間為 2.5 秒，搜索的運行時間為 0.3 秒。 休息時間這麼多，嗯？

變化

重要的是要承認本 trie 教程中描述的算法在某些邊緣情況下可能會失敗，因此在設計時已經考慮了預定義的搜索詞。

例如，如果一個搜索詞的開頭與另一個搜索詞的某些部分相同，例如：

• “與朋友分享和享受”
• “我有兩張票要和別人分享”

並且文本正文包含一個短語，該短語導致 trie 指針從錯誤的路徑開始，例如：

我有兩張票可以與朋友分享和享受。

那麼該算法將無法匹配任何術語，因為在文本指示符已經通過文本正文中匹配術語的開頭之前，trie 指示符不會返回到起始節點。

在實現算法之前，重要的是要考慮這種邊緣情況是否適用於您的應用程序。 如果是這樣，可以使用附加的 trie 指示符修改算法，以在任何給定時間跟踪所有匹配項，而不是一次只跟踪一個匹配項。

結論

文本搜索是計算機科學的一個深入領域； 一個充滿問題和解決方案的領域。 我必須處理的那種數據（23MB 的文本是現實生活中的大量書籍）可能看起來很少發生或專門的問題，但從事語言學研究、歸檔或任何其他類型數據操作的開發人員，定期遇到大量數據。

從上面的 trie 數據結構教程中可以看出，為手頭的問題仔細選擇正確的算法非常重要。 在這種特殊情況下，trie 方法將運行時間縮短了驚人的 99.93%，從一個多小時縮短到不到 3 秒。

這絕不是唯一有效的方法，但它很簡單，而且很有效。 我希望你發現這個算法很有趣，並祝你在編碼工作中好運。

[1]本次測試所用機器規格如下：

• 英特爾 i7 4700HQ
• 16GB 內存

在 Windows 8.1 上使用 .NET 4.5.1 和 Kubuntu 14.04 使用最新版本的 mono 進行了測試，結果非常相似。

[2]測試樣本由 280K 個搜索短語組成，總大小為 23.5MB，文本正文為 1.5MB。