3 ms·

Why not generate an index containing all strings + all strings off by Levenshtein distance 1 (or N)? This is what I assumed google would do, but I don't know t

Why not generate an index containing all strings + all strings off by Levenshtein distance 1 (or N)? This is what I assumed google would do, but I don't know the index size.

TheLoneWolfling 11y ago
Because that is absurdly large, and gets larger as the character set grows.
- jhallenworld 11y ago
  Yeah, realized this later. Maybe the trie (or whatever) index can have a concept of "any single character" built in to it. This should be easier than making into a full automata.
  - TheLoneWolfling 11y ago
    The simple way to do this is to have a default child in the trie. But even then, it can get absurdly large. Look at something like "aaaa"(4), for instance.
  - DannyBee 11y ago
    http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht... See the part about how you would intersect a trie and a levenshtein automata and find the ones that must be in both. It's not as hard as one would think (Tries are already DFA) You can also do it for other types of indexes.
  - jules 11y ago
    That's basically what this is, except you do it for the query rather than for the index, and you build the structure more intelligently than just inserting all possible insertions/deletions/substitutions. If you wanted to make an index like that you could build a Levenshtein DFA for each term in the index, and then union all those together.
lorenzhs 11y ago
It's already been answered why this isn't a good idea, but there is a working approach that works similarly: instead of all words within Levenshtein distance N, you store all words with exactly N characters deleted from them. So for each word in your dictionary, store all words that can appear when you delete N characters. That's a much more reasonable number, and there are tricks to make it manageable for long words. Then when you do queries, do the same with your query word and check if it's in the index. This is actually a very fast technique, it's described here in more detail: http://arxiv.org/pdf/1008.1191v2.pdf http://arxiv.org/pdf/1008.1191v2.pdf

Why not generate an index containing all strings + all strings off by Levenshtein distance 1 (or N)? This is what I assumed google would do, but I don't know the index size.

TheLoneWolfling 11y ago

Because that is absurdly large, and gets larger as the character set grows.

jhallenworld 11y ago
Yeah, realized this later. Maybe the trie (or whatever) index can have a concept of "any single character" built in to it. This should be easier than making into a full automata.
- TheLoneWolfling 11y ago
  The simple way to do this is to have a default child in the trie. But even then, it can get absurdly large. Look at something like "aaaa"(4), for instance.
- DannyBee 11y ago
  http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht... See the part about how you would intersect a trie and a levenshtein automata and find the ones that must be in both. It's not as hard as one would think (Tries are already DFA) You can also do it for other types of indexes.
- jules 11y ago
  That's basically what this is, except you do it for the query rather than for the index, and you build the structure more intelligently than just inserting all possible insertions/deletions/substitutions. If you wanted to make an index like that you could build a Levenshtein DFA for each term in the index, and then union all those together.

lorenzhs 11y ago

It's already been answered why this isn't a good idea, but there is a working approach that works similarly: instead of all words within Levenshtein distance N, you store all words with exactly N characters deleted from them. So for each word in your dictionary, store all words that can appear when you delete N characters. That's a much more reasonable number, and there are tricks to make it manageable for long words. Then when you do queries, do the same with your query word and check if it's in the index. This is actually a very fast technique, it's described here in more detail: http://arxiv.org/pdf/1008.1191v2.pdf http://arxiv.org/pdf/1008.1191v2.pdf