Using Bloom Filters for Detecting Duplicates

It’s time to turn our attention back to the problem we discussed at the beginning of this chapter. We have an array of strings and want to check whether there are any duplicates. Let’s now solve this problem in a space-efficient way by using a Bloom filter.

The strategy is to iterate over the array of strings, and if a string is deemed not a duplicate, we insert it into a Bloom filter. To determine whether a string is a duplicate, we look it up in the Bloom filter to see if we’ve ever encountered it before.

Here’s the code to implement this approach:

	import bloom_filter


	def find_duplicates(array):
	set = bloom_filter.BloomFilter(len(array), 0.01)

	for item in array:
	if set.read(item):
	return True
	else:
	set.insert(item)

	return False

If this code gives the result of False, we know with certainty that there aren’t any duplicate values. On the other hand, if the code returns True, then it’s likely a duplicate. As to how likely, well, that depends on the false positive rate we set for our Bloom filter. If F is 1 percent (as it is for this code example), then it’s 99 percent likely that there’s a duplicate.

And so, if your application is willing to tolerate errors 1 percent of the time, a Bloom filter is a great way to save space in storing your set while finding duplicates.

Indeed, when I use the sys.getsizeof() method to measure the space of different sets, I find that to contain 100 values, a hash table takes up 4,688 bytes of space, while a Bloom filter takes up 296 bytes. This is true even though I’ve reduced the Bloom filter’s false positive rate down to 1 percent.