3 ms·

What information about 'character distributions within strings' would be useful? the idea of Levenshtein Distance as constituting a metric space is something i

What information about 'character distributions within strings' would be useful? the idea of Levenshtein Distance as constituting a metric space is something i've never thought of. I implemented a simple "Did You Mean?" using L.D. in Ruby/C but didn't build this type of structure and now that i've read this it seems obvious. edit: clarification

lpolovets 17y ago
Let's say you plan to keep 2 bytes/16 bits of metadata for each string in the corpus. You can use these 16 bits to store five 3-bit counters for the number of characters in a string whose ascii values are 0, 1, ... 4 mod 5. Each counter can go up to 7 (0x111), at which point further increments are no-ops (so a string with 7 characters that have an ascii value of 0 mod 5 will have the same value in the first counter as a string with 20 characters that have an ascii value of 0 mod 5). When you want to see if the Levenshtein distance between two strings is less than some threshold (say 2), you first compare the two sets of 5 counters. The difference in values for corresponding counters can help you determine a lower bound on the Levenshtein distance. For example, if the first string has six characters that are 1 mod 5, and the second string has 2 characters that are 1 mod 5, then your edit distance will be at least 2, so if you were only looking for strings that are within a distance of 1, you no longer need to bother computing Levenshtein for your two strings. Comparing counters is just a few bit operations, so it's super fast.
- chronomex 17y ago
  That reminds me of the Boyer-Moore string search algorithm. One way to implement B-M is with a bitmap of the characters in the query string, so that regions of the search space that can't possibly match the query will be skipped efficiently.

3 ms·

What information about 'character distributions within strings' would be useful? the idea of Levenshtein Distance as constituting a metric space is something i

by rubyrescue 17y ago

lpolovets 17y ago
Let's say you plan to keep 2 bytes/16 bits of metadata for each string in the corpus. You can use these 16 bits to store five 3-bit counters for the number of characters in a string whose ascii values are 0, 1, ... 4 mod 5. Each counter can go up to 7 (0x111), at which point further increments are no-ops (so a string with 7 characters that have an ascii value of 0 mod 5 will have the same value in the first counter as a string with 20 characters that have an ascii value of 0 mod 5). When you want to see if the Levenshtein distance between two strings is less than some threshold (say 2), you first compare the two sets of 5 counters. The difference in values for corresponding counters can help you determine a lower bound on the Levenshtein distance. For example, if the first string has six characters that are 1 mod 5, and the second string has 2 characters that are 1 mod 5, then your edit distance will be at least 2, so if you were only looking for strings that are within a distance of 1, you no longer need to bother computing Levenshtein for your two strings. Comparing counters is just a few bit operations, so it's super fast.
- chronomex 17y ago
  That reminds me of the Boyer-Moore string search algorithm. One way to implement B-M is with a bitmap of the characters in the query string, so that regions of the search space that can't possibly match the query will be skipped efficiently.