如何选择仅查找已知单词的句子的数据结构

Question

我正在研究语言学习计划。该程序跟踪它认为用户知道的单词，并且我想添加一个功能，向用户显示他们应该能够阅读的句子。

我有大量带标记词的数据集，但我一直在努力提出正确的数据结构以使此列表的过滤速度足够快。我的第一遍只是在用户每次学习一个新单词时都对其进行遍历，但是事实证明这太慢了，特别是因为用户在会话中经常学习多个单词。此外，随着用户添加自己的句子或我的全局句子数据库已添加/删除/更新了句子，句子列表会随着时间而变化。

在支持数据动态特性的同时，可以使这种快速搜索成为一个好的数据结构？也就是说，给定用户知道的单词集以及大量的标记化和可能进一步预处理的句子，我想快速找到用户应该能够阅读所有单词的句子。

Answer 1

对于这种问题，最好的方法是使用树。我建议您看一下Tries或Radix trees。它们允许将搜索减少到对数时间。

Answer 2

您可以使用字母树。一个节点将由以下成员组成：

• 字母
• 是否是单词的结尾

例如，在根级别，您将拥有一个节点'a'，这是它自己的一个词。它的一个子代是“ s”，这也是它自己的意思，因为与父代一起阅读它会得到“ as”，依此类推。在这棵树中找到一个词最多需要26 +词长-1。