Re:Damn Cool Algoritms: BK-Trees
by lpolovets on Wednesday March 03, 2010 @07:51AM
(#1163956)
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.
Re:Damn Cool Algoritms: BK-Trees
by chronomex on Wednesday March 03, 2010 @04:59PM
(#1165325)
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.
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.