3 ms·

'e' ^ 'f' ^ 'g' == 0x40. Uh-oh. Edit: I misread the post; my bad. The post effectively uses a bit vector to store the last N chars in a window, and the bit vec

'e' ^ 'f' ^ 'g' == 0x40. Uh-oh. Edit: I misread the post; my bad. The post effectively uses a bit vector to store the last N chars in a window, and the bit vector happens to fit in a single machine word. Also, XOR happens to be a good way to update the bit vector, because it turns out it's sufficient to store how many times each character appears in the window mod 2. So to be clear, my "demonstration" above only works because the ASCII representations of e, f, and g are not linearly independent with respect to xor. However in the article, the representations of all of the characters are chosen to be a linearly independent set.

jandrese 4y ago
The example code in the article left out the lookup table to convert each character into a single bit representation. All the tricky xor and popcount stuff could have been a 26 byte array just as easily and been O(n).
- robinhouston 4y ago
  There's no lookup table. The example code in the article does the conversion using this expression: 1 << (s[i + j] as u32 - 'a' as u32)
  - WorldMaker 4y ago
    Yes, for some additional explanation for those that might use it, that's "ASCII math": it assumes all lowercase ASCII Latin letters (which most Unicode encodings including UTF-8 and UTF-32 inherit). ASCII was intentionally designed so that the lowercase letters a-z are in English alphabet order and so subtracting 'a' from the letter gives you an alphabet position number from 0-25. (The same applies in ASCII for the upper case range A-Z and the numerical range 0-9, though doing math between ranges is less fun.) Then you've just got a standard single 1 left shifted 0-25 positions. (So 'a' is 1 and 'z' is 1*2^25.)
quietbritishjim 4y ago
Ah OK, the article is actually suggesting making a list of Booleans whose length equals the number of possible characters. It just happens that it's assuming 26 allowed characters which fit in the bits of a 64 bit number. The running time is does not depend on the window length, but does depend on the number of possible characters. If it's all of Unicode for example you'd be stuffed: you could fix the vector of values in memory (currently there are approx. 150,000 unicode code points), even if you used a byte per value, but counting number of true values will require iterating over the whole vector. Even just going from 26 Latin letters to 256 byte values makes this trick quite messy unless your language has a really nice bit vector type (admittedly many do). This comment was helpful for me to understand what was going on, even though it's a mistake followed by a correction.

jandrese 4y ago

The example code in the article left out the lookup table to convert each character into a single bit representation. All the tricky xor and popcount stuff could have been a 26 byte array just as easily and been O(n).

robinhouston 4y ago
There's no lookup table. The example code in the article does the conversion using this expression: 1 << (s[i + j] as u32 - 'a' as u32)
- WorldMaker 4y ago
  Yes, for some additional explanation for those that might use it, that's "ASCII math": it assumes all lowercase ASCII Latin letters (which most Unicode encodings including UTF-8 and UTF-32 inherit). ASCII was intentionally designed so that the lowercase letters a-z are in English alphabet order and so subtracting 'a' from the letter gives you an alphabet position number from 0-25. (The same applies in ASCII for the upper case range A-Z and the numerical range 0-9, though doing math between ranges is less fun.) Then you've just got a standard single 1 left shifted 0-25 positions. (So 'a' is 1 and 'z' is 1*2^25.)

quietbritishjim 4y ago

Ah OK, the article is actually suggesting making a list of Booleans whose length equals the number of possible characters. It just happens that it's assuming 26 allowed characters which fit in the bits of a 64 bit number. The running time is does not depend on the window length, but does depend on the number of possible characters. If it's all of Unicode for example you'd be stuffed: you could fix the vector of values in memory (currently there are approx. 150,000 unicode code points), even if you used a byte per value, but counting number of true values will require iterating over the whole vector. Even just going from 26 Latin letters to 256 byte values makes this trick quite messy unless your language has a really nice bit vector type (admittedly many do). This comment was helpful for me to understand what was going on, even though it's a mistake followed by a correction.