请考虑以下几点：
- 我们有一个可用的词典
- 我们输入了许多段落的词语，我希望能够根据这些输入预测句子中的下一个词语。
假设我们有几句话，例如“大家好，我的名字是@Tom”，“他的名字是@jerry”，“他去的地方没有水”。我们检查哈希表中是否存在某个词。如果不存在，我们为其分配一个唯一ID并将其放入哈希表中。这样，我们就不需要将一连串的词语存储为一组字符串，而只需存储一列唯一的ID即可。
以上，我们可能会有例如（0, 1, 2, 3, 4），（5, 2, 3, 6）和（7, 8, 9, 10, 3, 11, 12）。请注意，3代表“is”，我们会在发现新词时添加新的唯一ID。假设我们给定一个句子“她的名字是”，这将是（13, 2, 3）。我们想知道，在这种情况下，下一个词应该是什么。这是我想到的算法，但我认为它不够高效：
- 我们有一列N个链（观察到的句子），其中一个链可能例如是3,6,2,7,8。
- 每个链的平均大小为M，其中M是平均句子长度
- 我们给定一个大小为S的新链，例如13, 2, 3，我们希望知道下一个词最可能是哪个？
算法：
-
首先扫描整个链列表，查找包含完整S输入（本例中为13,2,3）的链。由于我们必须扫描N个链，每个链长度为M，并且每次比较S个字母，其复杂度为O(N*M*S)。
-
如果扫描中没有链包含完整的S，接下来通过删除最不重要的词（即第一个词，去掉13）进行扫描。现在，扫描（2,3），在最坏情况下为O(N*M*S)，实际上是S-1。
-
继续以这种方式扫描，直到我们得到大于0的结果（如果有的话）。
-
统计我们收集的所有剩余链中的下一个词。我们可以使用一个哈希表，每次添加时进行计数，并跟踪添加次数最多的词。最坏情况下的构建复杂度为O(N)，查找最大词的复杂度为O(1)。
-
找到的最大词是最可能的，因此返回它。
每次扫描在最坏情况下需要O(M*N*S)。这是因为有N个链，每个链有M个数字，我们必须检查S个数字以匹配。我们在最坏情况下扫描S次（13,2,3，然后2,3，然后3，总共3次扫描=S）。因此，总体复杂度为O(S^2 * M * N)。
所以，如果我们有100,000个链，平均句子长度为10个词，我们需要1,000,000*S^2来获得最优词。显然，N >> M，因为句子长度通常不会随观察到的句子数量而增加，所以M可以视为一个常数。我们可以将复杂度简化为O(S^2 * N)。然而，O(S^2 * M * N)可能对分析更有帮助，因为M可能是一个相当大的“常数”。
这可能完全不是解决此类问题的方法，但我希望分享我的想法，而不是直接寻求帮助。我这样扫描的原因是我只想扫描必要的部分。如果没有链包含完整的S，就继续修剪S，直到一些链匹配。如果它们永远不匹配，我们就不知道下一个词应该是什么！有什么建议可以减少时间/空间复杂度的解决方案吗？
回答：
这是语言模型的问题。对于基础方法，你只需要一个哈希表，将固定长度的词链（例如长度为k）映射到最可能的后续词。（*）
在训练时，你使用滑动窗口将输入分解为(k+1)-gram。所以如果你遇到
The wrath sing, goddess, of Peleus' son, Achilles对于k=2，你会生成，
START START theSTART the wraththe wrath singwrath sing goddessgoddess of peleusof peleus sonpeleus son achilles这可以在线性时间内完成。对于每个3-gram，在哈希表中统计第三个词在前两个词之后出现的频率。
最后，遍历哈希表，对于每个键（2-gram）只保留最常出现的第三个词。线性时间。
在预测时，只需查看最后的k（2）个词并预测下一个词。这只需要常数时间，因为它只是哈希表查找。
如果你想知道为什么应该只保留短子链而不是完整链，请研究马尔可夫窗口的理论。如果你的模型记住了它在输入中看到的所有词链，那么它会在训练数据上严重过拟合，在预测时只会重现其输入。具体有多严重取决于训练集（更多数据更好），但对于k>4，你真的需要在模型中进行平滑处理。
(*) 或者映射到一个概率分布，但对于你简单的示例用例，这不是必需的。
