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)
“It is the essence of truth that it is never excessive. Why should it exaggerate? There is that which should be destroyed and that which should be simply illuminated and studied. How great is the force of benevolent and searching examination! We must not resort to the flame where only light is required.”
—Victor Hugo (18021885)