| --- Log opened Sat Nov 20 00:00:43 2021 |
| 00:07 | <@macdjord> | Hrm. If it possible to create a hash function such that two nonequal inputs that share some particular property are /less/ likely to have the same hash value? |
| 00:08 | <&McMartin> | All that should be necessary is to not depend solely on that property? |
| 00:09 | <&McMartin> | Kinda the whole point of hashes is that any change mutates the whole thing in hard-to-predict ways |
| 00:10 | <@macdjord> | McMartin: Sorry, I mean, 'so that two inputs which share some property are less likely to collide than two inputs which do not share that property'. |
| 00:11 | <&McMartin> | That starts turning into "more likely to collide if X is not true", which sounds like "a weakness in the hash function" |
| 00:14 | <@macdjord> | The specific thing that inspired this question is that my IRC client, HexChat, assigns every nick a colour, to make it easier to tell who said what. There are only ~16 colours, though, so collisions are frequent. But its a lot more annoying to get collisions between two people whose nicks are the same length or start with the same character than it is to have collisions between nicks that are visually distinct on their own. Could one design a |
| 00:14 | <@macdjord> | hash function which makes this happen less often? |
| 00:16 | <@macdjord> | Intuitively I suspect the answer is 'no', but I can't prove it. |
| 00:19 | < Pi> | I think you can. |
| 00:24 | < Pi> | If you consider the input as a metric space, you'd want to amplify the dimension you want less correlation in. |
| 00:27 | < Pi> | One way of doing that is to imagine enumerating all the values in an order that concentrates the similarity metric in the higher-order bits, and then taking the lower-order bits as the hash. |
| 00:29 | < Pi> | So for example, you could calculate an enumeration for strings based on length and then Gray code, and then take that modulo 16. |
| 00:34 | < Pi> | That would give you a hash function that guarantees a different hash output for any input strings with with a binary edit distance < 16. |
| 00:40 | < Pi> | You could probably tweak and improve that to better represent what you consider similar: for example, there might be some kind of modified Gray code that orders based on Latin character edit distance, rather than just binary edit distance. |
| 00:41 | < Pi> | That would amplify the distance between similar Latin strings even more, at the expense of non-Latin strings, which should make sense for IRC nicknames. |
| 01:14 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has quit [Connection closed] |
| 02:34 | | Degi [Degi@Nightstar-0ruh32.pool.telefonica.de] has quit [Ping timeout: 121 seconds] |
| 02:35 | | Degi [Degi@Nightstar-6ej3as.pool.telefonica.de] has joined #code |
| 03:28 | | catalyst_ is now known as catalyst |
| 05:22 | | Vorntastic [uid293981@Nightstar-phvupn.irccloud.com] has joined #code |
| 05:22 | | mode/#code [+qo Vorntastic Vorntastic] by ChanServ |
| 05:57 | | abudhabi_ [abudhabi@Nightstar-rlu7rq.adsl.tpnet.pl] has joined #code |
| 06:00 | | abudhabi__ [abudhabi@Nightstar-jqlbmo.adsl.tpnet.pl] has quit [Ping timeout: 121 seconds] |
| 06:29 | | SmithKurosaki [uid215460@Nightstar-e2nmdb.irccloud.com] has quit [[NS] Quit: Connection closed for inactivity] |
| 06:57 | | Pi [uid25146@Nightstar-l49s2t.irccloud.com] has quit [[NS] Quit: Connection closed for inactivity] |
| 07:00 | | dataangel [dataangel@Nightstar-s7j.l3h.187.192.IP] has joined #code |
| 07:39 | | dataangel [dataangel@Nightstar-s7j.l3h.187.192.IP] has quit [[NS] Quit: more angels at ircd.chat/6697] |
| 07:55 | | Degi [Degi@Nightstar-6ej3as.pool.telefonica.de] has quit [Ping timeout: 121 seconds] |
| 07:57 | | Degi [Degi@Nightstar-gs383k.pool.telefonica.de] has joined #code |
| 09:28 | | JustBob [justbob@Nightstar.Customer.Dissatisfaction.Administrator] has quit [NickServ (RECOVER command used by JustLurk)] |
| 09:28 | | JustBob [justbob@Nightstar.Customer.Dissatisfaction.Administrator] has joined #code |
| 09:28 | | mode/#code [+o JustBob] by ChanServ |
| 09:45 | | Pi [uid25146@Nightstar-l49s2t.irccloud.com] has joined #code |
| 10:26 | | macdjord [macdjord@Nightstar-re5.7if.45.45.IP] has quit [[NS] Quit: Deep inside, every housecat believes themself to be just a temporarily embarrassed tiger.] |
| 10:28 | | macdjord [macdjord@Nightstar-re5.7if.45.45.IP] has joined #code |
| 10:28 | | mode/#code [+o macdjord] by ChanServ |
| 11:06 | | macdjord [macdjord@Nightstar-re5.7if.45.45.IP] has quit [Connection reset by peer] |
| 11:06 | | macdjord [macdjord@Nightstar-re5.7if.45.45.IP] has joined #code |
| 11:06 | | mode/#code [+o macdjord] by ChanServ |
| 11:48 | | Emmy [Emmy@Nightstar-l49opt.fixed.kpn.net] has joined #code |
| 12:15 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has quit [Connection reset by peer] |
| 12:17 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has joined #code |
| 12:18 | | catalyst_ [catalyst@Nightstar-in5ufb.dab.02.net] has joined #code |
| 12:21 | | catalyst [catalyst@Nightstar-ejd4sd.cable.virginm.net] has quit [Ping timeout: 121 seconds] |
| 13:49 | | catalyst_ is now known as catalyst |
| 14:35 | | catalyst_ [catalyst@Nightstar-ejd4sd.cable.virginm.net] has joined #code |
| 14:38 | | catalyst [catalyst@Nightstar-in5ufb.dab.02.net] has quit [Connection closed] |
| 14:43 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 14:43 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 15:13 | | catalyst [catalyst@Nightstar-in5ufb.dab.02.net] has joined #code |
| 15:15 | | catalyst_ [catalyst@Nightstar-ejd4sd.cable.virginm.net] has quit [Ping timeout: 121 seconds] |
| 15:26 | | catalyst_ [catalyst@Nightstar-058ijn.cable.virginm.net] has joined #code |
| 15:28 | | catalyst [catalyst@Nightstar-in5ufb.dab.02.net] has quit [Ping timeout: 121 seconds] |
| 16:55 | | Kindamoody[zZz] is now known as Kindamoody |
| 17:22 | | Vorntastic [uid293981@Nightstar-phvupn.irccloud.com] has quit [[NS] Quit: Connection closed for inactivity] |
| 17:36 | | SmithKurosaki [uid215460@Nightstar-e2nmdb.irccloud.com] has joined #code |
| 20:59 | | catalyst [catalyst@Nightstar-6qagms.dab.02.net] has joined #code |
| 21:01 | | catalyst_ [catalyst@Nightstar-058ijn.cable.virginm.net] has quit [Ping timeout: 121 seconds] |
| 21:08 | | catalyst_ [catalyst@Nightstar-ejd4sd.cable.virginm.net] has joined #code |
| 21:11 | | catalyst [catalyst@Nightstar-6qagms.dab.02.net] has quit [Ping timeout: 121 seconds] |
| 22:25 | | SmithKurosaki [uid215460@Nightstar-e2nmdb.irccloud.com] has quit [[NS] Quit: Connection closed for inactivity] |
| 22:49 | | Emmy [Emmy@Nightstar-l49opt.fixed.kpn.net] has quit [Ping timeout: 121 seconds] |
| 23:16 | | Kindamoody is now known as Kindamoody[zZz] |
| --- Log closed Sun Nov 21 00:00:44 2021 |