Hash that allows for similarity comparison
Disclaimer: This is not for security. It is not for true hashing. It is for a very specific task that has absolutely nothing to do with common hashing tasks.
Is there a one-way function (like a hash) that allows for similarity comparison? Example, I want to hash names. I hash John Lennon and John W. Lennon. I want the result to allow me to identify that those two things are much more similar than a hash of Paul McCartney. So, this function requires two things. 1: It is one-way. I don't want to know the original information. 2: It retains similarity. 128.23.113.249 (talk) 13:24, 21 December 2012 (UTC)
- I think you might need to be a bit more specific about your requirements. What kind of data are you hashing (presumably not names of musicians), and what does "similarity" mean in this context? Do you actually require the hash to be one-way, or is it just that it can be one-way? How much smaller do you want the hash to be than the original data? If you actually are interested in names, then are you aware of soundex and similar algorithms to group words with similar pronounciations together? 130.88.99.231 (talk) 16:01, 21 December 2012 (UTC)
- The data will be names. But, the names cannot be known. Therefore, there must be a one-way hash-like function. So, assume the function spits out 8 digit numbers. I give you 12345678 and 12245678 and you can see that the original names, which you don't know, are about 90% similar. The end goal is to identify similarity of names without having an easy means of knowing the original names. 128.23.113.249 (talk) 18:27, 21 December 2012 (UTC)
- If similar inputs give similar outputs, and if (as you apparently do), you also want to be able to reliably conclude the reverse (given similar hashes, you want to know that the names are similar), then it's hard to see how you can prevent someone from inverting the function, by just searching. What you're looking for seems (almost?) provably nonexistent. --Trovatore (talk) 18:37, 21 December 2012 (UTC)
- Perhaps Soundex would work for your purposes? —Chowbok ☠ 20:20, 21 December 2012 (UTC)
- I suppose I could be a little more explicit about what I mean by "just searching". Suppose I have one of your hashes, and I want to know the input that generated it. I start generating inputs and evaluating the distance between their hashes and the given hash. I change a little bit and see if it improves or degrades the cost function (that's the distance between the hash of my chosen input, and the target hash). Now if I always accept a change that improves that, and always reject one that degrades it, that's called greedy descent, and it might not work because I could get stuck in a local minimum.
- But there are lots of strategies to avoid this fate. A simple one is simulated annealing.
- This might not work all the time, but it's probably going to work a significant fraction of the time, and it's hard to see how any scheme fitting your requirements can be made resistant to it.
- On the other hand, since you say you don't care about "security", maybe you're not interested in preventing someone from recovering the input if he's willing to work that hard; you just don't want it to be trivial. That's probably possible. I'd start with a search on "obfuscation". --Trovatore (talk) 18:58, 21 December 2012 (UTC)
- It sounds like you want fuzzy hashing (context triggered piecewise hashes) (which we don't have an article on?). ssdeep does a version of that, although I'm sure there's something better for text. The soundex is a step in the right direction but I don't think it directly does what you want. Does anyone know if there's some better wiki articles on fuzzy hashing? I don't know the name of any algorithms that implement it, but that's what I'd start to investigate. Shadowjams (talk) 07:53, 22 December 2012 (UTC)
- And, even ignoring the hashing issue, which names are most similar is still difficult to define. I'd assume the family name is most important, but this is sometimes the last name and sometimes the first name, depending on the culture. Then the given name may be next, or perhaps a nickname. Middle names are less important, but there can be any number of those. And what do we do about aliases, nom de plumes, etc. ? StuRat (talk) 08:23, 22 December 2012 (UTC)
- Is a hash of length 27x26 bits ok?
- (OR) If it is, you zero all bits first. Then you process all pairs of letters (JO, OH, HN, LE, etc.) as follows:
- -Treat A as 0, B as 1, ... , Z as 25.
- -Compute N = 26 * (first letter) + (second letter). If there is only one letter (W for example in JOHN W LENNON), make that the second letter and make the first letter 26.
- -Set the Nth bit of the hash.
- That way, the bit pattern will resemble the letter pattern. The XOR of two hashes is the "distance."
- If 27x26 is too large, take the first letter modulo 9 and the second modulo 13. Voilâ, a 9x13-bit hash at the price of some accuracy.
- Close to trivial, and probably inferior to soundex, but maybe my hashing strategy is closer to the thing you had in mind. Hope that helps. - ¡Ouch! (hurt me / more pain) 18:05, 22 December 2012 (UTC)