c - 如何使用 C 在大文本中查找短语？

Question

备注:我知道在SO上有很多类似的问题，但没有一个是针对C语言的，所以我才问这个。

这是我面临的问题:我会得到一个大文本(例如 150,000 个单词)，然后是一系列短语(每个短语有 1 到 10 个单词)。对于其中的每一个短语，我都需要在文本中找到紧跟在该短语之后的单词并将其返回。

到目前为止我唯一的解决办法:创建一个包含以下内容的结构:

• 当前单词
• 该词之前的 3 个词
• 后面的单词

然后我会解析文本，为每个单词创建一个结构，并将所有这些结构存储在哈希表中。当每个短语出现时，我会在哈希表中搜索该短语的最后一个单词，检查前 3 个单词是否匹配，然后返回下一个单词。我相信回到 3 个单词就足以唯一标识短语，但我可以增加这个数字。

你认为这行得通吗？你知道更好的方法吗？

Answer 1

更简单的方法:遍历文本，存储所有 n-grams(n 词的子序列)1 <= n < = 10 在哈希表或 trie 中。这样检索就很简单了，只需在哈希表或 trie 中查找 n-gram。

在哈希表版本中，您只需将 n-gram 存储为单词字符串的串联，中间使用标准化空格。

这种方法的问题在于，对于哈希表，您最多需要 45 * N 个条目，其中 N 是文本中的单词数.不过，查找应该非常快，而且 150.000 个单词的数据集足够小，可以完成这项工作。