给定连续的单词流,删除重复项

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)空间.

备择方案:

特里

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

这将给出O(wordLength)查找时间并使用O(wordCount * maxWordLength)空间,尽管实际空间使用可能更低,因为重复前缀(例如te在下面的示例中)仅使用空间一次.

二进制搜索树

一个二叉搜索树是树的数据结构,其中在左子根的树的每个节点比其父更小,同样在右边的所有节点都更大.

一个自我平衡的一个给O(wordLength * log wordCount)查找时间和使用O(wordCount * maxWordLength)空间.

布隆过滤器

甲布隆过滤器是由一些数位,并且其中字映射至位几个散列函数的数据结构,设置在加载并检查每个哈希函数的输出,如果任何未在查询中设置.

这比上述解决方案占用的空间更少,但是以误报为代价 - 某些单词将被标记为不重复的单词.

具体来说,它使用每个密钥的比特,其中是误报率,给出空间使用,但具有令人难以置信的低常数因子.1.44 log2(1/e)eO(wordCount)

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

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