System and method for keyword searching using both static and dynamic dictionaries
An apparatus and techniques for constructing and utilizing a “dynamic dictionary” that is not a compiled dictionary, and therefore does not need to be recompiled in order to be updated. The dynamic dictionary includes respective data structures that represent (i) a management automaton that includes a plurality of management nodes, and (ii) a runtime automaton that is derived from the management automaton and includes a plurality of runtime nodes. The runtime automaton may be used to search input data, such as communication traffic over a network, for keywords of interest, while the management automaton manages the addition of keywords to the dynamic dictionary. Typically, at least two (e.g., exactly two) such dynamic dictionaries are used in combination with a static dictionary.
1. A method of analyzing communication traffic in a network to determine if keywords occur in the communication traffic, comprising:
adding one or more newly-arrived keywords to a static dictionary, which is represented by a data structure stored in computer memory and needs to be recompiled in order to be updated, by recompiling the static dictionary;
during the recompilation of the static dictionary:
receiving one or more additional keywords during the recompilation;
adding the one or more additional keywords to both a first dynamic dictionary and a second dynamic dictionary, each of which is represented by a respective data structure stored in computer memory and does not need to be recompiled in order to be updated, and
searching input data using both the first dynamic dictionary and the static dictionary but not using the second dynamic dictionary; and
following the recompilation, searching input data using both the second dynamic dictionary and the static dictionary but not using the first dynamic dictionary.
2. The method according to claim 1 , further comprising storing the respective data structures that represent the first and second dynamic dictionaries at least partly within a cache memory of a processor.
3. The method according to claim 2 , wherein storing the respective data structures at least partly within the cache memory of the processor comprises:
during the recompilation of the static dictionary, storing the first dynamic dictionary at least partly within the cache memory while storing the second dynamic dictionary in computer memory; and
following the recompilation, storing the second dynamic dictionary at least partly within the cache memory while storing the first dynamic dictionary in computer memory.
4. The method according to claim 1 , further comprising, following the recompilation, rebuilding the first dynamic dictionary, such that the first dynamic dictionary includes fewer keywords than the first dynamic dictionary previously included.
5. The method according to claim 1 , wherein the recompilation is a first recompilation, and wherein the method further comprises, following the first recompilation, adding the one or more additional keywords that were received during the first recompilation to the static dictionary, by performing a second recompilation of the static dictionary.
6. The method according to claim 5 , further comprising, during the second recompilation of the static dictionary:
adding any keywords that arrive during the second recompilation to both the first dynamic dictionary and the second dynamic dictionary, and
searching input data using both the second dynamic dictionary and the static dictionary.
7. The method according to claim 1 , further comprising adding the received one or more additional keywords to a keyword collection, wherein recompiling the static dictionary comprises recompiling the static dictionary such that the static dictionary includes all keywords contained in the keyword collection at a start of the recompilation.
8. The method according to claim 1 , further comprising adding to the second dynamic dictionary, but not to the first dynamic dictionary, any keywords that arrive following the recompilation and prior to a subsequent recompilation.
9. The method according to claim 1 , further comprising repeatedly adding at least one respective newly-arrived keyword to the static dictionary, by repeatedly recompiling the static dictionary.
10. Apparatus, comprising:
a network interface; and
one or more processors, configured to analyze communication traffic in a network to determine if keywords occur in the communication traffic and to:
add one or more newly-arrived keywords to a static dictionary, which is represented by a data structure stored in computer memory and needs to be recompiled in order to be updated, by recompiling the static dictionary,
during the recompilation of the static dictionary:
receive one or more additional keywords during the recompilation;
add the one or more additional keywords to both a first dynamic dictionary and a second dynamic dictionary, each of which is represented by a respective data structure stored in computer memory and does not need to be recompiled in order to be updated, and
search input data received via the network interface using both the first dynamic dictionary and the static dictionary but not using the second dynamic dictionary, and
following the recompilation, search input data received via the network interface using both the second dynamic dictionary and the static dictionary but not using the first dynamic dictionary.
11. The apparatus according to claim 10 , wherein the processors are further configured to store the respective data structures that represent the first and second dynamic dictionaries at least partly within a cache memory of one of the processors.
12. The apparatus according to claim 11 , wherein the processors are configured to:
during the recompilation of the static dictionary, store the first dynamic dictionary at least partly within the cache memory while storing the second dynamic dictionary in computer memory, and
following the recompilation, store the second dynamic dictionary at least partly within the cache memory while storing the first dynamic dictionary in computer memory.
13. The apparatus according to claim 10 , wherein the processors are further configured to, following the recompilation, rebuild the first dynamic dictionary, such that the first dynamic dictionary includes fewer keywords than the first dynamic dictionary previously included.
14. The apparatus according to claim 10 , wherein the recompilation is a first recompilation, and wherein the processors are further configured to, following the first recompilation, add the one or more additional keywords that were received during the first recompilation to the static dictionary, by performing a second recompilation of the static dictionary.
15. The apparatus according to claim 14 , wherein the processors are further configured to, during the second recompilation of the static dictionary:
add any keywords that arrive during the second recompilation to the first dynamic dictionary and to the second dynamic dictionary, and
search input data received via the network interface using both the second dynamic dictionary and the static dictionary.
16. The apparatus according to claim 10 , wherein the processors are configured to add the received one or more additional keywords to a keyword collection, and to recompile the static dictionary such that the static dictionary includes all keywords contained in the keyword collection at a start of the recompilation.
17. The apparatus according to claim 10 , wherein the processors are further configured to add to the second dynamic dictionary, but not to the first dynamic dictionary, any keywords that arrive following the recompilation and prior to a subsequent recompilation.
18. The apparatus according to claim 10 , wherein the processors are configured to repeatedly add at least one respective newly-arrived keyword to the static dictionary, by repeatedly recompiling the static dictionary.
19. A computer software product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by one or more processors, cause the processors to analyze communication traffic in a network to determine if keywords occur in the communication traffic and to:
add one or more newly-arrived keywords to a static dictionary, which is represented by a data structure stored in computer memory and needs to be recompiled in order to be updated, by recompiling the static dictionary,
during the recompilation of the static dictionary:
receive one or more additional keywords during the recompilation;
add the one or more additional keywords to both a first dynamic dictionary and a second dynamic dictionary, each of which is represented by a respective data structure stored in computer memory and does not need to be recompiled in order to be updated, and
search input data using both the first dynamic dictionary and the static dictionary but not using the second dynamic dictionary, and
following the recompilation, search input data from the network using both the second dynamic dictionary and the static dictionary but not using the first dynamic dictionary.
20. The computer software product according to claim 19 , wherein the first dynamic dictionary comprises a management automaton and a runtime automaton.