C:在字典中搜索字符串

Question

我有一个算法，我创建了一个巨大的字符串集(字典)。现在我有另一个巨大的字符串流连续到达，需要查找是否存在于字典中。到目前为止，我能够实现这种情况。现在我希望如果任何字符串到达​​两次或多次，我需要将其标记为“已存在”而无需再次搜索。我们怎样才能做到这一点？如果不以某种方式存储已解析的字符串，我想不出任何方法。如果我们存储已经解析过的字符串，然后检查每个字符串是否更早出现，那将是一种开销，会扼杀优化的意图。有什么想法吗？

Answer 1

您无需检查每个字符串即可判断您以前是否见过一个字符串。这种问题通常用 hash table 解决。这会让你知道一个元素是否在表中或不在恒定时间内(好吧，它可以，但它取决于实现)。

或者您可以使用 Bloom Filter这将能够快速告诉您是否还没有看到某个项目，尽管它有误报的缺点。 IE。它可靠地告诉您是否有东西不在集合中，但告诉您“可能”否则您必须执行进一步检查。