On 5/4/2011 5:39 PM, Raymond Hettinger wrote:
The 512 bits in h are progressively eaten-up between iterations. So each pass yields a different (array index, bit_mask) pair.
Yeh, obvious now that I see it.
It's easy to use the interactive prompt to show that different probes are produced on each pass:bf = BloomFilter(num_bits=1000, num_probes=8) pprint(list(bf.get_probes('Alabama')))[(19, 1073741824), (11, 64), (9, 134217728), (25, 1024), (24, 33554432), (6, 16), (7, 16777216), (22, 1048576)]
Should have tried that.
The 512 bits are uncorrelated -- otherwise sha512 wouldn't be much of a cryptographic hash ;)
The fifty state example in the recipe is a reasonable demonstration that the recipe works as advertised. It successfully finds all fifty states (the true positives) and it tries 100,000 negatives resulting in only a handful of false negatives.
I presume you mean 'false positives', as in the program comment and Wikipedia.
The test would be more convincing to many with 100000 other geographic names (hard to come by, I know), or other english names or words or even with longer random strings that matched the lengths of the state names. But an average of 5/100000 false positives in 5 runs is good.
-- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
