Fuzzy Searching
To perform fuzzy string searching using the bitap algorithm, it is necessary to extend the bit array R into a second dimension. Instead of having a single array R that changes over the length of the text, we now have k distinct arrays R1..k. Array Ri holds a representation of the prefixes of pattern that match any suffix of the current string with i or fewer errors. In this context, an "error" may be an insertion, deletion, or substitution; see Levenshtein distance for more information on these operations.
The implementation below performs fuzzy matching (returning the first match with up to k errors) using the fuzzy bitap algorithm. However, it only pays attention to substitutions, not to insertions or deletions — in other words, a Hamming distance of k. As before, the semantics of 0 and 1 are reversed from their intuitive meanings.
#includeRead more about this topic: Bitap Algorithm
Famous quotes containing the words fuzzy and/or searching:
“Even their song is not a sure thing.
It is not a language;
it is a kind of breathing.
They are two asthmatics
whose breath sobs in and out
through a small fuzzy pipe.”
—Anne Sexton (19281974)
“And I cannot find the place
Where his paw is the snare!
Little One! Oh, Little One!
I am searching everywhere!”
—James Kenneth Stephens (18821950)