algorithm - 给定连续的单词流，删除重复项

Question

最近有人问我这个问题。

Given a continuous stream of words, remove the duplicates while reading the input.

示例:

输入:这是下一个问题流，看这是一个问题

输出:下一个流是一个问题

从end开始，question和is已经出现过一次，所以第二次忽略。

我的解决方案:

1. 在此场景中对流中的每个单词使用哈希。

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

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

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

Answer 1

哈希并不是一个特别糟糕的解决方案。

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

备选方案:

树

A trie是一种树状数据结构，其中每条边对应一个字母，从根开始的路径定义了节点的值。

这将给出 O(wordLength)查找时间和使用 O(wordCount * maxWordLength)空间，尽管实际空间使用量可能较低，因为重复的前缀(例如下例中的 te)仅使用一次空间。

二叉搜索树

A binary search tree是一种树数据结构，其中以左 child 为根的子树中的每个节点都小于其父节点，类似地，右侧的所有节点都更大。

A self-balancing一个给O(wordLength * log wordCount)查找时间和使用 O(wordCount * maxWordLength)空间。

布隆过滤器

A bloom filter是一种数据结构，由一些位和一些哈希函数组成，它将一个词映射到一个位，在添加时设置每个哈希函数的输出，并检查是否有任何未在查询时设置。

与上述解决方案相比，这使用的空间更少，但代价是误报 - 一些单词将被标记为重复项，而实际上并非如此。

具体来说，它使用1.44 log<sub>2</sub>(1/e)每个 key 的位数，其中 e是误报率，给出 O(wordCount)空间使用，但常数因子非常低。

这将给出 O(wordLength)查找时间。

An example of a Bloom filter, representing the set {x, y, z}. The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure, m=18 and k=3.