3 ms·

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

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 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.

nynx 4y ago
This article’s technique can definitely expand into dynamically allocated bitsets.
- thomasahle 4y ago
  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?
- FartyMcFarter 4y ago
  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.
at_compile_time 4y ago
>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.
- thomasahle 4y ago
  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.
  - twic 4y ago
    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!
    - thomasahle 4y ago
      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 :-)
  - remram 4y ago
    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 https://en.wikipedia.org/wiki/Bloom_filter

nynx 4y ago

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

thomasahle 4y ago
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?
FartyMcFarter 4y ago
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.

at_compile_time 4y ago

>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.

thomasahle 4y ago
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.
- twic 4y ago
  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!
  - thomasahle 4y ago
    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 :-)
- remram 4y ago
  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 https://en.wikipedia.org/wiki/Bloom_filter