Method and apparatus for performing similarity searching on a data stream with respect to a query string

A method for performing similarity searching on a data stream with respect to a query string, the data stream comprising a plurality of data substrings, the query string comprising a plurality of query substrings, the method comprising:

• filtering the data stream using a programmable logic device configured to find a plurality of possible matches between the data substrings and a plurality of the query substrings,
• wherein the data substrings and the query substrings comprise a plurality of characters;
• for each data substring that was found to be a possible match as a result of the filtering step, identifying at least one corresponding query substring for which that data substring is a possible match;
• and
• determining a similarity between the query string and at least a portion of the data stream based on the possible matches found by the filtering step, wherein the determining step comprises (1) comparing the characters of a window of the data stream that encompasses the data substring found to be a possible match with the characters of a window of the query string that encompasses the identified query substring corresponding to the data substring that was found to be a possible match, and (2) assessing whether the data stream portion and the query string qualify as being similar to each other based on the comparing step such that a controlled number of mismatches are permitted between the characters of the data stream window and the characters the query string window.