4

我在内存中有一个 T9 字典（trie/hash_map）。字典包含单词评级对，因此当从字典中挑选一个单词时，它的评级会增加，并且单词评级对在单词列表中上升。

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

在输入中，我有在电话上按下的数字字符串（1-9、'*' 来更改单词和''）。

问题：

  1. 有什么算法可以快速解析字符串吗？
  2. 哪种数据结构会更好？

升级版：

完整的问题文本（问题 D）

Hash_map 实现

尝试实现

4

1 回答 1

8

我认为特别有效的一种选择是将 trie 预处理为经过修改的结构，该结构专门优化用于根据击键预测单词。

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

  • 从 trie 的根开始。
  • 对于每个数字，请按照与该数字对应的指针。
  • 如果您离开特里，那么就没有任何建议可做。
  • 否则，查看优先级队列中可以精确由这些数字组成的单词，然后建议该优先级队列中具有最高使用计数的元素。

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

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

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

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

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

希望这可以帮助！

于 2011-08-26T22:35:43.467 回答