3 ms·

Here's an alternative that is more efficient at large scales (eg. if you have one order of magnitude more entries than just an English dictionary): performing A

Here's an alternative that is more efficient at large scales (eg. if you have one order of magnitude more entries than just an English dictionary): performing Approximate Nearest Neighbor search [1] over a pre-computed Levenshtein space. - hash all your dictionary entries through a Levenshtein-locality-sensitive hash function [2] with a well-chosen hash size. Any two words within a Levenshtein distance D of each other will have the same hash (you pick D). - store the hashes into an efficient DB for quick lookup. Each hash will map to one or several (levenshtein-similar) dictionary entries. - when presented with a new input, compute its hash, retrieve the entry for the hash in your DB (if it exists). - finish by sorting the retrieved dictionary entries by Levenshtein distance to your input... you just recovered all dictionary entries closer than distance D to your input (approximately). Pretty much unbeatable, and works over spaces that have hundreds of millions of dictionary entries. [1] https://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor https://en.wikipedia.org/wiki/Nearest_neighbor_search#Approx... [2] Can't find one? Build your own by computing the pairwise distance matrix of your entries, then reducing this matrix through PCA to an appropriate number of components (the length of your hash). The coordinates of each entry in this new space is the entry's hash.

pacala 12y ago
A kingdom for a layman exposition on how [2] is to be computed.
- danieltillett 12y ago
  Exactly. I think we are going to need a pretty wide margin.
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 ago
  The magic is in the creation of the hash.
  - StefanKarpinski 12y ago
    There 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 ago
      Any 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 ago
  i 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.
srean 12y ago
> Build your own by computing the pairwise distance matrix of your entries, then reducing this matrix through PCA to an appropriate number of components (the length of your hash). You are kidding right ? I cant imagine anyone seriously suggesting PCA on a half a million by half a million matrix, or evaluating this matrix in the first place. This actually a fairly actively researched topic: whether edit distance can be embedded, even if approximately in a vector space. It has been surprisingly resistant to such efforts. Yes there are some results but nothing very satisfactory. Edit distance is a metric, so it was believed it would easy to map individual strings to vectors, such that the distance between two vectors was same as, or close to the edit distance between the corresponding strings. What we want, then, is an (approximate) isomorphism between these two metric spaces. In addition, in the interest of size we would like these vectors to be of small dimension. If the required dimension is high it would defeat the purpose if the string to vector map needs to be stored. Unfortunately it seems edit distance is resistant to isomorphism to a low-dimensional vector space. There is also this question which metric do we use in the vector space, Euclidean, Manhattan...? there are some results on the L1, i.e. embedding on a vector space with Manhattan distances. Fun story: was an intern in Google's spelling correction team once upon a time long ago. So I was explaining what I was doing, the person I was explaining it to was thoroughly unimpressed: "So whats the big deal, you know/hear the word and write down the spelling". It made me realize how difficult spelling in English is compared to some of the other languages. The variability in the map from phonemes to spelling is quite high in English. This person was Italian, he told me Italian has a lot less variability in this regard.
- danieltillett 12y ago
  Pity nobody here seem to be interested in doing anything about English spelling. Propose a practicable solution [1] and it is ignored :( [1] https://news.ycombinator.com/item?id=8158579 https://news.ycombinator.com/item?id=8158579
  - beagle3 12y ago
    The scope of this project is beyond huge. And similar things are being proposed for the last 250 years (some in jest, some seriously [1]). But the benefits do not seem sufficient given the costs. [1] http://grammar.ccc.commnet.edu/grammar/twain.htm http://grammar.ccc.commnet.edu/grammar/twain.htm
GeneralMayhem 12y ago
> Any two words within a Levenshtein distance D of each other will have the same hash (you pick D). Wait, what? Doesn't this transitively result in the whole dictionary hashing to the same value?
fchollet 12y ago
I can't edit anymore, so I'll reply to my own post: People are pointing out there is no known hash function that will map every word within a same distance D to the same hash. That is correct, and I was just meaning to explain the process at a high level. Levenshtein-locality sensitive hashing is not a solved problem in CS. And you know what else in the algorithm I described is not a solved problem? Efficient nearest neighbor search. In a space with more than a few dimensions, we actually don't know any better way to perform exact NNS than brute forcing the search space. And you know what? None of that matter, since we have inexact yet statistically excellent processes to perform both of these tasks. That's the really cool thing about engineering as opposed to math or computer science: it doesn't have to be exact to be useful. A trivial way to build an inexact, yet useful levenshtein hash function is to pick a random sample of words from your dictionary, define them as hash values, and assign to any input the closest word from your sample. Now work with a large family (100+) of such grossly approximate hashes and you can build a statistically excellent algorithm. (and of course this is just an example, there are countless better ways to do the same thing).

pacala 12y ago

A kingdom for a layman exposition on how [2] is to be computed.

danieltillett 12y ago
Exactly. I think we are going to need a pretty wide margin.

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 ago
The magic is in the creation of the hash.
- StefanKarpinski 12y ago
  There 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 ago
    Any 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 ago
i 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.

srean 12y ago

> Build your own by computing the pairwise distance matrix of your entries, then reducing this matrix through PCA to an appropriate number of components (the length of your hash). You are kidding right ? I cant imagine anyone seriously suggesting PCA on a half a million by half a million matrix, or evaluating this matrix in the first place. This actually a fairly actively researched topic: whether edit distance can be embedded, even if approximately in a vector space. It has been surprisingly resistant to such efforts. Yes there are some results but nothing very satisfactory. Edit distance is a metric, so it was believed it would easy to map individual strings to vectors, such that the distance between two vectors was same as, or close to the edit distance between the corresponding strings. What we want, then, is an (approximate) isomorphism between these two metric spaces. In addition, in the interest of size we would like these vectors to be of small dimension. If the required dimension is high it would defeat the purpose if the string to vector map needs to be stored. Unfortunately it seems edit distance is resistant to isomorphism to a low-dimensional vector space. There is also this question which metric do we use in the vector space, Euclidean, Manhattan...? there are some results on the L1, i.e. embedding on a vector space with Manhattan distances. Fun story: was an intern in Google's spelling correction team once upon a time long ago. So I was explaining what I was doing, the person I was explaining it to was thoroughly unimpressed: "So whats the big deal, you know/hear the word and write down the spelling". It made me realize how difficult spelling in English is compared to some of the other languages. The variability in the map from phonemes to spelling is quite high in English. This person was Italian, he told me Italian has a lot less variability in this regard.

danieltillett 12y ago
Pity nobody here seem to be interested in doing anything about English spelling. Propose a practicable solution [1] and it is ignored :( [1] https://news.ycombinator.com/item?id=8158579 https://news.ycombinator.com/item?id=8158579
- beagle3 12y ago
  The scope of this project is beyond huge. And similar things are being proposed for the last 250 years (some in jest, some seriously [1]). But the benefits do not seem sufficient given the costs. [1] http://grammar.ccc.commnet.edu/grammar/twain.htm http://grammar.ccc.commnet.edu/grammar/twain.htm

GeneralMayhem 12y ago

> Any two words within a Levenshtein distance D of each other will have the same hash (you pick D). Wait, what? Doesn't this transitively result in the whole dictionary hashing to the same value?

fchollet 12y ago

I can't edit anymore, so I'll reply to my own post: People are pointing out there is no known hash function that will map every word within a same distance D to the same hash. That is correct, and I was just meaning to explain the process at a high level. Levenshtein-locality sensitive hashing is not a solved problem in CS. And you know what else in the algorithm I described is not a solved problem? Efficient nearest neighbor search. In a space with more than a few dimensions, we actually don't know any better way to perform exact NNS than brute forcing the search space. And you know what? None of that matter, since we have inexact yet statistically excellent processes to perform both of these tasks. That's the really cool thing about engineering as opposed to math or computer science: it doesn't have to be exact to be useful. A trivial way to build an inexact, yet useful levenshtein hash function is to pick a random sample of words from your dictionary, define them as hash values, and assign to any input the closest word from your sample. Now work with a large family (100+) of such grossly approximate hashes and you can build a statistically excellent algorithm. (and of course this is just an example, there are countless better ways to do the same thing).