4 ms·
How can it be true that any two words with a given levenstein distance will have the same hash? If we picked the threshold to be one, couldn't you come up with
by schrodinger 12y ago
How can it be true that any two words with a given levenstein distance will have the same hash?
If we picked the threshold to be one, couldn't you come up with two words that are levenstein distance one, and then come up with a third word that's distance one to one of the words and not the other?
In that case, the first two would be in one bucket, where does the third go?
- cbsmith 12y agoThe magic is in the creation of the hash.
- StefanKarpinski 12y agoThere is no such magical hash. Any hash splits the space of words into equivalence classes and unless there's only one equivalence class, there must be words that are edit distance one apart that are in different classes since you can get from any word to any other by a sequence of single edits.
- fchollet 12y agoAny single hash will be suboptimal; the "magic" would be to use a bunch of different hashes to partition your space into suboptimal buckets, and use all of them at once to get very good (though still approximative) query results. This is what Spotify's excellent Annoy library does. [1] [1] https://github.com/spotify/annoy https://github.com/spotify/annoy
- shoo 12y agoi agree. so you have to hash things into multiple buckets, ie each word needs to have multiple coordinates/buckets in hash space. i think this is what is meant by "well-chosen hash size" / "one or several", maybe. it makes sense if you think about the distance matrix / PCA sketch - PCA leaves you with a low-rank approximation of the distance matrix, and the rank would be the number of coordinates for each word in hash space.