System and method for keyword spotting using representative dictionary
Methods and systems for keyword spotting, i.e., for identifying textual phrases of interest in input data. In the embodiments described herein, the input data comprises communication packets exchanged in a communication network. The disclosed keyword spotting techniques can be used, for example, in applications such as Data Leakage Prevention (DLP), Intrusion Detection Systems (IDS) or Intrusion Prevention Systems (IPS), and spam e-mail detection. A keyword spotting system holds a dictionary of textual phrases for searching input data. In a communication analytics system, for example, the dictionary defines textual phrases to be located in communication packets—such as e-mail addresses or Uniform Resource Locators (URLs).
1. A method for representing a first dictionary for faster searching, the method comprising:
retrieving the first dictionary from an external memory, the first dictionary comprising first textual phrases;
deriving from the first dictionary a second dictionary comprising second textual phrases, wherein the second dictionary has a smaller data size than the first dictionary, and wherein each first textual phrase in the first dictionary corresponds to at least one of the second textual phrases in the second dictionary; and
storing the second dictionary in a cache memory to represent the first dictionary stored in the external memory, wherein the cache memory has a faster access speed than the external memory.
2. The method according to claim 1 , wherein the first textual phrases are strings of characters and the second textual phrases are sub-strings of the first textual phrases.
3. The method according to claim 2 , wherein the characters in the first textual phrases include wildcard characters.
4. The method according to claim 2 , wherein each string of characters corresponds to a particular data communication packet and wherein each sub-string of characters is a subset of the characters in the particular data communication packet.
5. The method according to claim 4 , wherein the second dictionary comprises rectangles, wherein each rectangle comprises a list of sub-strings from a group of data communication packets.
6. The method according to claim 5 , wherein each sub-string in a rectangle has the same number of characters and begins at the same character position in a different communication packet.
7. The method according to claim 1 , wherein a plurality of first textual phrases in the first dictionary correspond to a single second textual phrase in the second dictionary.
8. The method according to claim 1 , wherein the first textual phrases include commonly found sub-strings that are common to a majority of the first textual phrases, and wherein the second textual phrases do not include the commonly found sub-strings.
9. A system for representing a first dictionary for faster searching, the system comprising:
an external memory, storing the first dictionary, wherein the first dictionary comprises first textual phrases;
a cache memory having a faster access speed than the external memory; and
a processor, which is configured to:
derive from the first dictionary a second dictionary comprising second textual phrases, wherein the second dictionary has a smaller data size than the first dictionary, and wherein each first textual phrase in the first dictionary corresponds to at least one of the second textual phrases in the second dictionary, and
store the second dictionary in the cache memory to represent the first dictionary stored in the external memory.
10. The system according to claim 9 , wherein the first textual phrases are strings of characters and the second textual phrases are sub-strings of the first textual phrases.
11. The method according to claim 10 , wherein the characters in the first textual phrases include wildcard characters.
12. The method according to claim 10 , wherein each string of characters corresponds to a particular data communication packet and wherein each sub-string of characters is a subset of the characters in the particular data communication packet.
13. The method according to claim 12 , wherein the second dictionary comprises rectangles, wherein each rectangle comprises a list of sub-strings from a group of data communication packets.
14. The method according to claim 13 , wherein each sub-string in a rectangle has the same number of characters and begins at the same character position in a different communication packet.
15. The method according to claim 9 , wherein a plurality of first textual phrases in the first dictionary correspond to a single second textual phrase in the second dictionary.
16. The method according to claim 9 , wherein the first textual phrases include commonly found sub-strings that are common to a majority of the first textual phrases, and wherein the second textual phrases do not include the commonly found sub-strings.