使用 Trie 实现自动完成功能

引言

如今，自动补全功能在数字环境中随处可见。您可能在智能手机上打字、发送电子邮件或进行Google搜索时，都遇到过简化生活的自动补全建议。通过预测并完成用户输入，这些建议有助于用户，使他们的体验更快、更有效。

Trie数据结构是自动补全功能背后的核心技术之一。发音为“try”；Trie是一种树状数据结构，它存储一组动态字符串，这使其成为快速查找和检索单词的理想选择。本文将解释自动补全的概念，并向您展示如何使用Trie将其付诸实践。

理解Tries

在我们开始开发自动补全功能之前，理解Trie数据结构至关重要。

Trie是一种树形结构，其中每个节点代表一个单词的字符。单词中的下一个字符由树中的下一级表示，根节点通常是空字符串。您可以通过沿着从根节点到叶节点的字符流来创建单词，从而遍历Trie。每个Trie节点都包含：

• 一个字典或数组，它使用键来表示字符，使用值来表示对子节点的引用，以便存储对子节点的引用。
• 一个二进制指示器，指示该节点是否表示一个单词的结尾。

由于Trie结构，它在存储和查找单词方面非常有效。它具有单词建议、部分匹配和快速查找——所有这些都是自动补全系统所必需的功能。

构建Trie

您必须首先建立一个Trie数据结构，才能实现自动补全功能。让我们回顾一下如何构建一个Trie。

步骤1：Trie节点定义

对于单词中的每个字符，都需要一个TrieNode类来表示。该类应包含一个标志以表示单词的结尾，以及用于子节点（表示下一个字符）的属性。

Python中的TrieNode类可以定义如下：

当一个节点表示单词的结尾时，is_end_of_word布尔标志被设置为True，而children属性则保存指向子节点的指针。

步骤2：创建Trie

现在让我们构建Trie类，它具有将单词添加到Trie和根节点的方法。

单词通过insert方法插入到Trie中，该方法是Trie类的一部分，该类有一个根节点。它遍历单词中的每个字符，根据需要添加新节点，并在添加完整个单词后标记单词的结尾。

使用Trie实现自动补全

建立Trie数据结构后，我们现在可以利用它来整合自动补全功能。我们的目标是识别共享特定前缀的每个术语。执行此操作的步骤如下：

步骤1：搜索前缀

从根节点开始遍历Trie，匹配前缀中的字符。为了完成此操作，前缀中的每个字符都必须被验证为子节点。如果一个字符不存在，则所有单词中都不存在该前缀。

步骤2：查找自动补全建议

为了找到所有具有相同前缀的单词，我们可以执行深度优先搜索（DFS），直到到达前缀的最后一个节点。DFS在遍历时构建单词，探索可能从当前节点引出的所有路径。

此代码中的递归函数查找单词，构建单词，并在到达单词结尾时将其添加到建议列表中。它通过检查所有可能从当前节点引出的路径来实现此目的。此过程确保包含包含指定前缀的每个单词。

代码

输出

代码解释

TrieNode类

• 表示Trie数据结构中的一个节点。
• 属性：children（用于存储子节点的字典）和is_end_of_word（布尔值，指示节点是否标记单词的结尾）。

Trie类

• 表示具有根节点的Trie。
• 方法：insert（将单词插入Trie）和find_words_with_prefix（查找具有给定前缀的单词）。

插入方法

• 通过遍历单词的字符并根据需要创建节点来将单词插入Trie。

查找带前缀的单词方法

• 通过遍历Trie并收集建议来返回具有给定前缀的单词列表。

主块

• 创建一个Trie（trie）并插入一个单词列表。
• 使用前缀“app”调用find_words_with_prefix并打印建议：['apple', 'appetizer']。