c++ - 实现 T9 文本预测

Question

我在内存中有一个 T9 字典(trie/hash_map)。字典包含词-评级对，因此当从字典中选取一个词时，它的评级递增，并且词-评级对在词列表中上升。

假设有一种方法可以从字典中挑选一个单词。该方法还执行一些单词评级例程。

在输入中，我有在电话上按下的一串数字(1-9，“*”来更改单词和“”)。

问题:

1. 有没有算法可以快速解析字符串？
2. 哪种数据结构比较好？

更新:

Full problem text (问题D)

Hash_map implementation

Trie implementation

Answer 1

我认为特别有效的一种选择是将 trie 树预处理为经过修改的结构，该结构专门针对基于击键的单词预测进行了优化。

直觉上，新结构是一个由可以在任何点按下的可能数字创建的 trie。然后每个特里树节点存储一个优先级队列，其中包含可能使用这些数字拼出的单词。然后，您可以通过以下算法预测要使用的词:

• 从 trie 的根开始。
• 对于每个数字，跟随与该数字对应的指针。
• 如果您退出 trie，则没有任何建议可以提出。
• 否则，查看可以由这些数字精确组成的单词的优先级队列，然后建议该优先级队列中使用次数最多的元素。

该算法耗时O(n + T_max)，其中n是数字串的长度，T_max是找到最流行的所需时间给定前缀的单词。对于二进制堆之类的东西，这可能是 O(1)，但对于更复杂的堆来说可能会更慢。

要构建此数据结构，您需要按如下方式预处理单词/频率的原始列表。对于每个单词，确定与其字母对应的数字系列。例如，单词“季风”将是 6667666，而单词“苹果”将是 27753。然后，将该序列插入数字特里，根据需要创建新节点。当到达这个数字串对应的最后一个节点时，将这个词插入到该节点对应的优先级队列中。这个操作的总时间实际上是相当不错的；给定一个包含 n 个字母的单词列表，这可以在 O(n T_insert) 时间内完成，其中 T_insert 是插入所需的时间一个词进入优先队列。这是因为我们最多需要访问每个字母三次 - 一次将其转换为数字，一次跟随数字 trie 中的适当边缘，一次将其插入优先级队列。

这种方法还可以很容易地将新词插入到预测器中。每当用户离开数字 trie 或选择一个不是第一个单词的单词时，您可以通过在 trie 中创建适当的一系列节点，然后将该单词插入正确的优先级来将该单词插入到数字 trie 中排队。

如果您将优先级队列从存储指向其最小元素的指针的平衡二叉搜索树中取出，您可以实现在 O(n) 时间内查找一系列 n 数字的最快单词，然后可以列出具有该前缀的所有其他单词均摊销 O(1) 时间。您还可以通过这种方式非常轻松地插入或删除新单词。

因为单词存储在一个 trie 中，您可以在 O(1) 中更新您对当前单词的猜测，只需从当前 trie 节点向下走到由当前数字给出的子节点。当用户按下空格键时，您只需重置回数字树的根。最后，当用户点击星标时，您可以使用上述技巧来查看给定 trie 节点的下一个最流行的词。

希望这对您有所帮助!