System and method for maintaining a dynamic dictionary
AssigneeCognyte Technologies Israel Ltd.
InventorYitshak Yishay
Life of this patent
Estimating the term…
Abstract
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.
Claims18
A method, comprising:
- storing, in computer memory, data structures that collectively represent at least one dynamic dictionary of keywords that does not need to be recompiled in order to be updated, the data structures including (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;
- searching input data, using the runtime automaton;
- and
- upon receiving a new keyword that is not included in the at least one dynamic dictionary:
- (i) updating the management automaton to include the new keyword, and (ii) storing, in one or more other management nodes, respective shortcut pointers that point to the new management node, indicating that the parent node corresponds to a largest suffix of respective sequences corresponded to by the other management nodes;
- and
- based on the update to the management automaton, updating the runtime automaton to include the new keyword.
A method, comprising:
- storing, in computer memory, data structures that collectively represent at least one dynamic dictionary of keywords that does not need to be recompiled in order to be updated, the data structures including (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;
- searching input data, using the runtime automaton;
- and
- upon receiving a new keyword that is not included in the at least one dynamic dictionary:
- updating the management automaton to include the new keyword, and
- based on the update to the management automaton, updating the runtime automaton to include the new keyword, wherein updating the runtime automaton to include the new keyword comprises adding one or more new runtime nodes to the runtime automaton, each of the new runtime nodes corresponding to at least a portion of the new keyword, wherein the runtime automaton uses an alphabet of symbols and for each of the new runtime nodes:
- (i) storing, in the new runtime node, a plurality of pointers to one or more of the new runtime nodes, the pointers including a respective pointer corresponding to each one of the symbols in the alphabet and (ii) storing, in one or more of the new runtime nodes, respective pointers to the new runtime node.
A method, comprising:
- storing, in computer memory, data structures that collectively represent at least one dynamic dictionary of keywords that does not need to be recompiled in order to be updated, the data structures including (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;
- searching input data, using the runtime automaton;
- and
- upon receiving a new keyword that is not included in the at least one dynamic dictionary:
- updating the management automaton to include the new keyword,
- wherein searching the input data comprises:
- traversing the runtime automaton, until a reporting runtime node is reached;
- and
- upon reaching the reporting runtime node, ascertaining that the new keyword is present in the input data, by ascertaining that at least two pointers stored in the reporting runtime node are equivalent to one another and do not point to a root node of the runtime automaton.
Dependencies are inferred from the claim text.