实现T9文本预测

Question

我在内存中有一个T9字典(trie/hash_map).该词典包含词级对,因此当从词典中选取一个词时,其等级增加,并且词等级对在词列表中上升.

假设有一种方法可以从字典中选择一个单词.该方法也做了一些单词评级例程.

在输入中,我有一串数字(1-9,'*'来改变单词和''),这些是在电话上按下的.

问题:

1. 有没有算法快速解析字符串？
2. 哪个数据结构会好？

UPD:

完整问题文本(问题D)

Hash_map实现

Trie实施

Answer 1

我认为特别有效的一个选择是将trie预处理为一个经过修改的结构,专门针对基于击键来预测单词进行优化.

直观地说,新结构是由可能在任何点上按下的可能数字创建的特里结构.然后,每个trie节点存储可能使用那些数字拼写出的单词的优先级队列.然后,您可以通过以下算法预测要使用的单词:

• 从特里的根开始.
• 对于每个数字,请按照与数字对应的指针.
• 如果你走掉特里,那么就没有任何建议.
• 否则,查看可以从这些数字形成的单词的优先级队列,然后建议具有最高使用计数的该优先级队列中的元素.

该算法花费时间O(n + T _max),其中n是数字串的长度,T _max是找到给定前缀的最流行字所需的时间.对于像二进制堆这样的东西,这可能是O(1),但对于更复杂的堆可能更慢.

要构建此数据结构,您可以按如下方式预处理原始的单词/频率列表.对于每个单词,确定与其字母对应的一系列数字.例如,单词"季风"将是6667666,而单词"apple"将是27753.然后,将该序列插入到数字trie中,根据需要创建新节点.当您到达与该数字字符串对应的最终节点时,将该字插入该节点的相应优先级队列中.这次行动的总时间实际上相当不错; 给定一个总共有n个字母的单词列表,这可以在O(n T _插入)时间内完成,其中T _insert是将单词插入优先级队列所需的时间.这是因为我们需要访问每个字母最多三次 - 一次将其转换为数字,一次跟随数字trie中的相应边缘,一次将其插入优先级队列.

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

如果您将优先级队列从存储指向其最小元素的指针的平衡二叉搜索树中取出,则可以在O(n)时间内为一系列n位数找到最快的单词,然后可以列出所有的带有该前缀的其他单词,每个摊销的O(1)时间.您也可以通过这种方式轻松插入或删除新单词.

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

希望这可以帮助!