Hacker News Reader

Comment by thomasahle | Hacker News Reader

One issue with this technique is when the set of characters grow above 64, so you can no longer give each one a unique bit.

This could happen if we are instead interested in a window of unique words in a long document.

Amazingly there is still a solution based on XOR!

It is a variant of Bloom Filters, which I know everyone loves, but it uses XOR instead of OR to combine things.

Basically each word is hashed to three locations and you flip those bits. Then you have to do some probabilistic analysis.

https://arxiv.org/abs/2211.03683

Edit: Actually the technique in this paper would take linear time to determine uniqueness. I wonder if there's a way to do it in constant time...

I guess you could just implement linear probing or cuckoo hashing in bits. But then update time would be amortized constant only.

View on HN

>One issue with this technique is when the set of characters grow above 64, so you can no longer give each one a unique bit.

You can xor arrays of integers.

Right, but if the universe of possible characters grow much larger than the window size (as it does in many applications), we want a method that only pays in terms of window size, not universe size.

So you use a sparse bitmap, ie a hash set. The size of the hash set is bounded to the size of the window, so this should be pretty efficient.

If you have a huge string, a huge alphabet, and also a huge window, then probabilistic techniques start to make sense. But let's not run while we can successfully walk!

Sure. We can always use a hash set, but then you need to use chaining or some other collision resolution policy. The whole of this whole exercise is to avoid that and get something really fast and truly constant time :-)

In that case, you might still want to use a similar trick as a first pass (like a bloom filter), and go over the window that is potentially unique again with the HashSet. This should still be faster than using the HashSet for all windows.

https://en.wikipedia.org/wiki/Bloom_filter

This article’s technique can definitely expand into dynamically allocated bitsets.

Say we don't want to allocate memory dynamically though. We just want to allocate O(W) bits at the start of the program. Can you still do it?

In that case the complexity becomes O(N * A) where A is the size of the alphabet, since at every step you have to go through the whole bitset in order to count how many bits are set.

Edit - actually it should be possible to update the count incrementally, so it should still be O(N) I think.

Reply on news.ycombinator.com