System and method for bit-map based keyword spotting in communication traffic

• US 9,690,873 B2
• Filed: 01/29/2014
• Issued: 06/27/2017
• Est. Priority Date: 01/31/2013
• Status: Active Grant

• Current Assignee: Cognyte Technologies Israel Ltd. (Cognyte Software Ltd.)
• Original Assignee: Verint Systems Limited (Verint Systems Incorporated)
• Inventors: Yishay, Yitshak
• Primary Examiner(s): Bullock, Joshua
• Application Number:
  US14/167,074
• Publication Number:
  US 20140222852A1
• Time in Patent Office: 1,245 Days
• Field of Search: 707758
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

Methods and systems for locating occurrences of a search pattern in a body of text. A processor searches the text for one or more occurrences of a pattern. Both the text and the pattern comprise symbols of some alphabet. In preparation for the search, the processor defines a respective bit-map for each alphabet symbol. Using the bit-maps, the processor carries out a highly efficient process of searching the text for occurrences of the pattern. The processor then scans the pattern backwards using the bit-maps, symbol by symbol, attempting to match the symbols of the pattern to the corresponding symbols of the text. If a match is not found, the processor calculates the size of the jump to the next position in the text based on the accumulated results of the evaluations up to the current position.

Claims

1. A method for searching a text that comprises a sequence of symbols for occurrences of a pattern of the symbols, using a sequence of evaluations at respective positions in the text, the method comprising:

performing a first evaluation of whether the pattern occurs in a current position in the text, wherein the performing comprises;

positioning the pattern so as to end at the current position in the text,

comparing the symbols of the pattern to the corresponding symbols of the text while progressing from an end to a beginning of the pattern, and

upon finding a mismatch between the pattern and the text, calculating the jump to the subsequent position depending at least on the mismatch;

if the pattern does not occur in the current position, calculating a size of a jump to a subsequent position in the text based on results of the first evaluation; and

performing a second evaluation of whether the pattern occurs in the subsequent position in the text.

2. The method according to claim 1, wherein calculating the size of the jump comprises computing the size of the jump based on the results of the first evaluation and of one or more previous evaluations that precede the first evaluation.

3. The method according to claim 1, wherein the symbols are selected from an alphabet comprising alphabet symbols, and comprising computing for the alphabet symbols respective bit-maps, such that bit values of the bit-map of the alphabet symbol indicate respective symbol positions of the pattern in which the alphabet symbol occurs, and wherein performing the first and second evaluations comprise making the evaluations using the bit-maps.

4. The method according to claim 3, wherein performing the first evaluation comprises evaluating all the offsets from the current position in the text using the bit-maps of the symbols found in the text at the respective offsets.

5. The method according to claim 4, wherein evaluating the offsets comprises accumulating, using the bit-maps, information regarding one or more of the positions in which the pattern cannot occur, and calculating the size of the jump to the subsequent position based on the accumulated information.

6. The method according to claim 3, wherein the pattern comprises a wild-card symbol at a given bit position, and wherein calculating the bit-maps comprises setting the bits at the given bit position in all the bit-maps.

7. The method according to claim 1, wherein performing the first evaluation comprises updating a data structure that indicates the positions in the text in which the pattern cannot occur, and wherein calculating the size of the jump comprises computing the size of the jump based on the updated data structure.

8. The method according to claim 1, wherein performing the first evaluation comprises updating a data structure that indicates, for each symbol in the text, whether that symbol was previously read from the text, and wherein performing the first evaluation comprises reading a given symbol from the text during the second evaluation only if the data structure indicates that the given symbol was not previously read from the text.

9. The method according to claim 1, wherein performing the second evaluation comprises outputting an indication of a match upon successfully matching the pattern to the text at the subsequent position.

10. Apparatus for searching a text that comprises a sequence of symbols for occurrences of a pattern of the symbols, using a sequence of evaluations at respective positions in the text, the apparatus comprising:

a memory, which is configured to store the text; and

a processor, which is configured to;

hold the pattern to be found in the text,

perform a first evaluation of whether the pattern occurs in a current position in the text by positioning the pattern so as to end at the current position in the text and comparing the symbols of the pattern to the corresponding symbols of the text while progressing from an end to a beginning of the pattern, and, upon finding a mismatch between the pattern and the text, to calculate the jump to the subsequent position depending at least on the mismatch,

calculate, if the pattern does not occur in the current position, a size of a jump to a subsequent position in the text based on results of the first evaluation, and

perform a second evaluation of whether the pattern occurs in the subsequent position in the text.

11. The apparatus according to claim 10, wherein the processor is configured to calculate the size of the jump based on the results of the first evaluation and of one or more previous evaluations that precede the first evaluation.

12. The apparatus according to claim 10, wherein the symbols are selected from an alphabet comprising alphabet symbols, and wherein the processor is configured to compute for the alphabet symbols respective bit-maps, such that bit values of the bit-map of the alphabet symbol indicate respective symbol positions of the pattern in which the alphabet symbol occurs, and to perform the first and second evaluations using the bit-maps.

13. The apparatus according to claim 12, wherein the processor is configured to perform the first evaluation by evaluating all the offsets from the current position in the text using the bit-maps of the symbols found in the text at the respective offsets.

14. The apparatus according to claim 13, wherein the processor is configured to accumulate, using the bit-maps, information regarding one or more of the positions in which the pattern cannot occur, and to calculate the size of the jump to the subsequent position based on the accumulated information.

15. The apparatus according to claim 12, wherein the pattern comprises a wild-card symbol at a given bit position, and wherein the processor is configured to set the bits at the given bit position in all the bit-maps.

16. The apparatus according to claim 10, wherein the processor is configured, in performing the first evaluation, to update a data structure that indicates the positions in the text in which the pattern cannot occur, and to calculate the size of the jump using the updated data structure.

17. The apparatus according to claim 10, wherein, in performing the first evaluation, the processor is configured to update a data structure that indicates, for each symbol in the text, whether that symbol was previously read from the text, and to read a given symbol from the text during the second evaluation only if the data structure indicates that the given symbol was not previously read from the text.

18. The apparatus according to claim 10, wherein the processor is configured to output an indication of a match upon successfully matching the pattern to the text at the subsequent position.