大海捞针：一个漂亮的大规模文本搜索算法教程

当遇到术语“文本搜索”时，人们通常会想到大量文本，这些文本以一种在用户输入时可以快速查找一个或多个搜索词的方式进行索引。 这是计算机科学家的经典问题，存在许多解决方案。

但是相反的情况呢？ 如果事先可用于索引的是一组搜索短语，并且只有在运行时才提供大量文本以供搜索，该怎么办？ 这些问题正是这个 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。