0

T9 词典是如何工作的？它背后的数据结构是什么。例如：有 16 个单词的列表/字典（全部大写）。您将输入数字，相应的输出应该是与字典中的数字匹配的单词。如何在 C/C++/JAVA 中实现这一点。[如果将任何单词添加到列表中，它也应该支持]

2:A/B/C
3:D/E/F
4:G/H/I
5:J/K/L
6:M/N/O
7:P/Q/R/S
8:T/U/V
9:W/X/Y/Z

LIST{DRAWING,PAINTING,DANCE.....}

输出窗口示例：

Input : 3729464
output : DRAWING
4

2 回答 2

1

如果简单直接查找完整单词就足够了，最好编写一个函数，将单词的字符替换为对应的数字：

A,B,C  -> 2
D,E,F  -> 3

等等

然后将该函数应用于所有字典条目并将结果存储为键，但将原始形式存储为哈希表（或类似数据结构）的值。由于每个数字可以表示多个不同的字符，因此可能必须将同一个键映射到多个值。您可以使用字符串列表作为值类型：

entries(3829464)  = [DRAWING]
entries(72468464) = [PAINTING]
entries(843)      = [THE,TIE]

等等。

然后，您可以直接针对散列的键搜索给定的输入数字序列，并轻松地将所有候选者检索为现成的列表。

实际的 T9 函数也支持延续：输入一个数字序列，并检索所有可能是输入序列的延续的字符串。为此，搜索树是一个很好的数据结构。同样，字符转换产生的数字最好用作 trie 的转换标签，字符串的原始形式最好存储在接受状态中。您可能希望在内部节点中存储其他信息，例如在给定节点下的子树中找到的接受状态的总数；这将帮助您在 O(1) 时间内决定是开始遍历 subtrie 以检索所有继续候选者，还是更好地等待用户提供更多输入。

于 2012-09-10T08:41:48.997 回答
0

不完全回答这个问题：

T9不也是做猜字之类的吗？我假设那里有像加权树一样的东西，猜测到目前为止输入的数字序列中最可能的（三个左右）单词。那将是相当多的 O(1) 。

看来，这里并不真正需要，但我只是好奇。

于 2012-09-10T09:06:54.750 回答