C++ 所有后缀的 Trie

在本文中，您将学习 C++ 中的所有后缀 Trie，包括其历史、实现、应用、优点和缺点。

C++ 中的 Trie 是什么？

Trie 也称为前缀树。它是一种树状数据结构，用于高效地存储和搜索动态字符串集。此数据结构用于许多高级算法，并且是各种技术的基础，尤其是在涉及文本或字符串的领域。在 Trie 中，每个节点代表一个字符串中的单个字符，并且从根到叶子的路径拼写出字符串。Trie 主要有助于进行自动完成建议和拼写检查，尤其适用于大量文本。总之，Trie 是一种非常强大的管理和检索动态单词集合信息的方式。

Trie 的历史

Trie 由 René de la Briandais 于 1959 年首次引入。它的名字来源于 "retrieval"（检索）的中间字母，因为它用于信息检索系统。然而，基本思想是一个非常古老的概念。Trie 可以更有效地存储大量字符串，就像您在字典中看到的那样，并对其进行操作。因此，这个概念在计算机科学和编程中广泛用于各种与字符串相关的任务。

示例 1

让我们用一个例子来说明 Trie 在 C++ 中的用法。

输出

Searching for 'ana' suffix: Found
Searching for 'xyz' suffix: Not Found

说明

1. TrieNode 类
   • 它代表 Trie 中的一个节点。
   • children：一个无序映射，用于存储每个字符的子节点。
   • isEndOfWord：它指示当前节点是否标记着单词的结束。
2. SuffixTrie 类
   • 它管理 Trie 结构和相关函数。
   • root：Trie 的根节点。
3. insertSuffix 函数
   • 一个用于将后缀插入 Trie 的辅助函数。
   • 它遍历后缀的字符，并在需要时创建节点。
4. buildSuffixTrie 函数
   • 它为给定的输入文本构建后缀 Trie。
   • 它为文本中不同位置开始的每个后缀调用 insertSuffix。
5. searchSuffix 函数
   • 它搜索 Trie 中特定的后缀。
   • 如果找到整个后缀，则返回 true；否则返回 false。
6. main 函数
   • SuffixTrie 类的示例用法。
   • 它为输入文本“banana”创建了一个后缀 Trie。
   • 它搜索后缀 “ana” 和 “xyz”，并打印它们是否被找到。

示例 2

让我们用另一个例子来说明 Trie 在 C++ 中的用法。

输出

Occurrences of 'ana' suffix: 2
Occurrences of 'xyz' suffix: 0

说明

1. TrieNode 类
   • 它代表 Trie 中的一个节点。
   • children：一个存储每个字符子节点的无序映射。
   • isEndOfWord：它指示当前节点是否标记着单词的结束。
   • occurrences：它跟踪后缀的出现次数。
2. SuffixTrie 类
   • 它管理 Trie 结构和相关函数。
   • root：它是 Trie 的根节点，存储为智能指针（shared_ptr）。
3. insertSuffix 函数
   • 一个用于将后缀插入 Trie 的辅助函数。
   • 它遍历后缀的字符，并在需要时创建节点。
   • 它会增加整个路径的出现次数。
4. buildSuffixTrie 函数
   • 它为给定的输入文本构建后缀 Trie。
   • 它为文本中不同位置开始的每个后缀调用 insertSuffix。
5. countOccurrences 函数
   • 它计算 Trie 中特定后缀的出现次数。
   • 如果找到整个后缀，则返回出现次数；否则返回 0。
6. main 函数
   • SuffixTrie 类的示例。
   • 它为输入文本 “banana” 创建了一个后缀 Trie。
   • 它计算并打印后缀 “ana” 和 “xyz” 的出现次数。

时间和空间复杂度

时间复杂度

如果后缀的长度为 m，并且 Trie 对于给定的后缀的最大深度为 m，则搜索后缀的时间复杂度为 O(m)。

• 构建后缀 Trie： O(n * m)
• 搜索后缀： O(m)

空间复杂度

如果考虑 TrieNode 结构以及边和节点的存储，则总空间复杂度为 O(n)。

• Trie 节点结构： O(n)
• 边 和节点存储： O(n)

Trie 的应用

Trie 有许多应用。Trie 的一些主要应用如下：

1. Trie：Trie 通常用于实现任何自动完成文本系统。通过将字典存储在 Trie 中，您可以根据用户到目前为止输入的内容快速预测和建议单词。
2. 拼写检查：Trie 也用于拼写检查算法，通过根据拼写错误的单词的字符遍历 Trie。
3. IP 路由和最长前缀匹配：在计算机网络中，Trie 用于 IP 路由和最长前缀匹配。它们有助于基于最长匹配前缀有效地确定路由表中的下一个跃点。
4. 数据压缩：Trie 用于数据压缩算法，例如 Huffman 编码。它们有助于有效地为不同字符表示可变长度编码。
5. 基因组数据分析：Trie 也用于生物信息学来分析基因组数据。它们可以有效地存储和搜索 DNA 序列和模式。
6. 子串搜索：Trie 对于子串搜索问题很有用。通过构建文本所有子串的 Trie，可以有效地搜索特定子串。
7. 编译器中的符号表：Trie 用于在编译器中构建符号表。它们提供了一种快速检查源代码中标识符和关键字的方法。
8. 网络路由协议：Trie 在像 Open Shortest Path First (OSPF) 这样的网络路由协议中使用，用于高效的路由查找。

Trie 的优点

Trie 有许多优点。Trie 的一些主要优点如下：

1. 文件系统索引：Trie 在前缀匹配搜索方面也很高效，可用于完全匹配搜索。此外，最终的完全匹配搜索运行时间会减少 O(k)，其中 k 是搜索序列中出现的字符串数量。
2. 自然语言处理 (NLP)：Trie 在许多 NLP 应用中使用。例如，存储字典、检索单词的基本形式、使用计数前缀来完成单词或自动完成。
3. 电话号码目录：Trie 也称为数字搜索树，可用于电话号码目录。这些目录具有搜索键，通常使用数字 0-9，并且结果以字典序打印。
4. DNA 序列中的子串匹配：Trie 可用于定位特定模式和序列，并且在 DNA 序列的子串匹配方面效率很高。它通常在生物信息学中使用。
5. 用于高效字符串搜索：您可以使用 Trie 在字典中搜索键。您可以执行插入 O(n)。同样，您可以在 O(m) 时间内查找存储在字符串集合中的特定字符串，其中 m 是目标字符串的长度。此外，在字符串集合中搜索特定字符串时，您可以获得给定目标字符串的前缀。
6. 前缀匹配：Trie 擅长前缀匹配。它们可以快速识别具有给定前缀的所有字符串，因此可用于自动完成和预测文本系统。
7. 空间效率：Trie 可以是空间高效的，尤其是在存储的字符串之间存在大量前缀重叠的情况下。公共前缀在 Trie 的多个分支之间共享，从而减少了总体内存需求。
8. 动态集合操作：Trie 高效地支持动态集合操作。插入新字符串、删除字符串或检查字符串是否存在都可以在 O(m) 时间内完成，其中 m 是字符串的长度。
9. 有序输出：Trie 自然地在存储的字符串之间维护顺序。此属性可用于需要有序输出的情况，例如在字典应用程序中或用于字母列表。

Trie 的缺点

Trie 有一些缺点。Trie 的一些主要缺点如下：

1. 空间复杂度：Trie 的主要缺点是其内存消耗开销在一定程度上很高，尤其是在有许多字符串且每个字符串都相当长的情况下。因此，由于每个节点代表一个字符，因此可能会发生开销。
2. 内存碎片：Trie 的使用也可能导致内存碎片，尤其是在处理不同长度的字符串时。它会过度使用内存并导致利用率低下。
3. 实现复杂度：与数据结构相比，实现 Trie 非常复杂。插入和删除操作需要仔细管理指针和内存分配，这可能导致复杂的情况并可能导致错误。
4. 对数字键无效：Trie 是为字符串设计的，因此不适合数字。您可能需要尝试其他数据结构，如哈希表或二叉搜索树。
5. 有限的字母表大小：如果字母表大小过大，Trie 会变得效率低下。
6. 构建 Trie 的时间复杂度：构建 Trie 的时间复杂度可能高于某些其他数据结构。构建 Trie 需要遍历每个字符串的每个字符，导致时间复杂度与所有字符串的总长度成正比。