5 ms·
Using https://gist.github.com/rjp/3bbf33911aaf9ed7a07be417adb4b8f1 https://gist.github.com/rjp/3bbf33911aaf9ed7a07be417adb4b8f1 on Arch Linux `words` 2.1-8 (whi
by zimpenfish 2y ago
Using https://gist.github.com/rjp/3bbf33911aaf9ed7a07be417adb4b8f1 https://gist.github.com/rjp/3bbf33911aaf9ed7a07be417adb4b8f1 on Arch Linux `words` 2.1-8 (which defaults to the `usa` word list) gives collisions for the 32 bit hash (but none for the 64 bit or the 128 bit variants.)
> ./target/debug/gxwords | cut -d' ' -f1 | sort | uniq -c | awk '$1>1'
2 28273056
2 8e264f8
2 f7bce777
Which then gives us
> ./target/debug/gxwords | egrep '28273056|8e264f8|f7bce777' | sort
28273056 counterclaiming
28273056 oncogene's
8e264f8 ingrates
8e264f8 toadstool's
f7bce777 Carib's
f7bce777 stemming
- bravura 2y agoStrange that all three collisions include "'s"
- judofyr 2y agoConsidering that 43% of the words (in my dictionary at least) include "s" it's not so strange: $ cat /usr/share/dict/words | wc -l 235976 $ cat /usr/share/dict/words | grep s | wc -l 101882
- filleokus 2y agoGP meant that all collisions contained 's - a possessive apostrophe (if I remember my grammar correctly?). oncogene's, toadstool's, Carib's. The /usr/share/dict/words on my macOS machine doesn't seem to have any 's words in it.
- vlovich123 2y agocounterclaiming Doesn’t have any s and stemming doesn’t have any possessive. I think drawing conclusions from a 32bit hash against a 123k word list is fruitless. You’d expect at least 1 collision due simply to birthday paradox.
- airstrike 2y agooncogene's <> counterclaiming ingrates <> toadstool's Carib's <> stemming all 3 pairs have one word ending in "'s", which I think is what the GGGP (?) was pointing out
- bravura 2y agoYes. But I didn't realize that 43% of the words in that dictionary contain "'s". In that case, the probability that, for 3 collisions, there is at least one element in every collision contains "'s" is 31%. That seems reasonable to me.
- airstrike 2y agobut 43% of the words contain s, not 's
- zimpenfish 2y ago> counterclaiming Doesn’t have any s and stemming doesn’t have any possessive. But "oncogene's" (collides with counterclaiming) and "Carib's" (collides with stemming) do. Also I did point out that the 64 and 128 bit variants have no collisions.
- vlovich123 2y agoYeah, but it's an uninteresting test. As others point out, 32-bit XXH3 has the same issue. It wouldn't surprise me if 32-bit AES did too. It has nothing to do with the quality of the hash algorithm & more to do with the fact that you're not building a perfect hash with such a small hash size.
- zimpenfish 2y ago> Yeah, but it's an uninteresting test. On its own, yes, fair, but it was combined with the 64 and 128 bit variants which aren't uninteresting. > As others point out, 32-bit XXH3 has the same issue. Yes, me. > It has nothing to do with the quality of the hash algorithm The original post asked "I would like to see the collision distribution on /usr/share/dict/words." and that is what they got a demonstration of - some collisions on 32 bit, none on 64 or 128 bit. What else could be done to satisfy their original request in a way that would be interesting to you?
- vlovich123 2y agoWouldn’t that be true for any 32-bit hash? The birthday paradox would suggest you only need 2^16 input values to generate a collision right?
- zimpenfish 2y agoxxhash32 does give a couple of collisions on the same file, yep. 734c8981 abloom 734c8981 sating ef336a7d contravene ef336a7d seducers
- jcelerier 2y agoI thought interesting that all three collision pairs have an 's ending, but looking into this dictionary, no less than 25% of the words finish by it. weird dict.