Basically, I love hashes and I use them all the time, but for many purposes I am only accidentally using the cryptographic features and in fact I would sometimes find it nice if similar inputs had similar outputs.
Said differently: I'd like a hashing algorithm where the Levenshtein distance between any given two outputs correlates with the Levenshtein distance between the corresponding inputs.
I can imagine lots of uses for such a tool. ...But I can't imagine how it could be possible to make one: files (or strings) vary in length, for one thing, but a good hash does not! Of course, I couldn't imagine md5 before I saw it in action, either.
Perhaps I'm missing the point, but I came up with a naive and sloppy part solution: https://gist.github.com/peterc/737d9178f02118f8e315 .. there are some weaknesses to this solution but it does perform similarly to your examples.
Thanks, Peter. I don't speak Ruby. Uh, line 5 contains a small function definition, which is applied to each ...slice of the input string, is that right?
Do you (or anyone else) have time to describe this code in English or pseudocode?
I'll start.
Let there be a function called hash which takes a
string named str and an integer named
length_of_hash (which defaults to 20).
Slice the string (str) into length_of_hash equally-sized
pieces?
Take numeric value of each character (of each slice??)
and do.. something to it, something involving
modulo 256, unless it's zero. Save all the
results.
Express each numeric result as hexidecimal and append
all those together. Return it, probably.
In short, convert the input string into an array of its character values, group those values into sub-arrays of length 'x', add together the aligned values in each sub-array and modulo each by 256, output the resulting values in hex pairs joined together in a big string.
Example, with a hash length of 4: "helloworld" => [104, 101, 108, 108, 111, 119, 111, 114, 108, 100] => [[104, 101, 108, 108], [111,119,111,114], [108, 100]] => [67, 64, 219, 222] => "4340dbde"
So if one character is different in the string, only one hex value in the output will vary too. However, a flaw of the plan is that changes spaced out at an interval that matches your hash "length" will only affect one hex value in the output, but you run into the pigeonhole principle if you want a hash of limited size to have the same or similar Levenshtein distance as the potential inputs, but I suspect there are far smarter solutions :-)
I'll provide some examples of input and output. These examples happen to contain no linefeeds.
Suppose:
Then I want something like: ...Rather than what md5 currently provides: Basically, I love hashes and I use them all the time, but for many purposes I am only accidentally using the cryptographic features and in fact I would sometimes find it nice if similar inputs had similar outputs.Said differently: I'd like a hashing algorithm where the Levenshtein distance between any given two outputs correlates with the Levenshtein distance between the corresponding inputs.
I can imagine lots of uses for such a tool. ...But I can't imagine how it could be possible to make one: files (or strings) vary in length, for one thing, but a good hash does not! Of course, I couldn't imagine md5 before I saw it in action, either.