鉴于连续不断的单词流，删除重复内容

Question

最近我被问到这个问题。

如果连续出现单词流，请在读取输入时删除重复项。

例子：

输入：This is next stream of question see it is a question

输出：This next stream of see it is a question

从年底开始，question以及is已经出现过一次，所以第二次它忽略。

我的解决办法：

1. 使用在这种情况下每个字过的流来散列。

2. 如果发生碰撞，则忽略该单词。

这绝对不是一个好的解决方案。我被要求优化它。

解决此问题的最佳方法是什么？

Answer 1

散列并不是特别糟糕的解决方案。

它给出预期的O(wordLength)查找时间，但O(wordLength * wordCount)在最坏的情况下，并使用O(maxWordLength * wordCount)空间。

备选方案：

特里

甲trie是树形数据结构，其中每个边缘对应于一个字母，从根的路径限定的节点的值。

这会给O(wordLength)查找时间并使用O(wordCount * maxWordLength)空间，虽然实际空间使用可能（在下面的示例中例如te）是作为重复前缀下只使用空间一次。

二叉搜索树

一个binary search tree是树数据结构，其中在左子根的树的每个节点比其父更小，同样在右边的所有节点都更大。

A self-balancing one给出O(wordLength * log wordCount)查找时间并使用O(wordCount * maxWordLength)空间。

布隆过滤

甲bloom filter是由一些数位，并且其中字映射至位几个散列函数的数据结构，设置每个哈希函数的输出上的附加和检查是否有任何未设置的查询。

这比上述解决方案使用更少的空间，但是以误报为代价 - 有些词语将被标记为不重复。

具体而言，它使用1.44 log2(1/e)位每个密钥，其中e是假阳性率，O(wordCount)空间使用率，但具有令人难以置信的低常数因子。

这会给O(wordLength)查找时间。

布隆过滤器的一个例子，表示所设置的{x, y, z}。彩色箭头显示每个集合元素映射到的位阵列中的位置。元素w不在集合{x, y, z}中，因为它散列到一个包含0的位数组位置。对于此数字，m=18和k=3。