Ordering regular expressions

Abstract

In examples, a system adaptively orders a set of regular expressions based on frequencies that respective regular expressions of the set of regular expressions match a set of messages, the adaptive ordering to produce an adaptively ordered set of regular expressions. The system determines, for a first message of the set of messages, whether a plurality of regular expressions of the adaptively ordered set of regular expressions match the first message. The system constructs a bi-directional graph representing the plurality of regular expressions that match the first message, and classifies a second message based on the adaptively ordered set of regular expressions and the bi-directional graph.

The invention claimed is: 
     
       1. A non-transitory machine-readable storage medium comprising instructions that when executed cause a system to:
 compile regular expressions stored in a file into a set of regular expressions having a specified order; 
 adaptively re-order the set of regular expressions into an order of priority based on frequencies that respective regular expressions of the set of regular expressions match a set of messages, the adaptive re-ordering of the set of regular expressions to produce an adaptively ordered set of regular expressions; 
 determine, for a first message of the set of messages, a plurality of regular expressions of the adaptively ordered set of regular expressions that match the first message; 
 create a representation of a graph having connected nodes, wherein the connected nodes correspond to the plurality of regular expressions that match the first message; and 
 classify a second message based on the adaptively ordered set of regular expressions and the graph by traversing the connected nodes in the graph to identify a node corresponding to a particular regular expression that matches the second message and has a highest priority in the adaptively ordered set of regular expressions, and classifying the second message based on the particular regular expression. 
 
     
     
       2. The non-transitory machine-readable storage medium of  claim 1 , wherein, to create the representation of the graph, the instructions when executed cause the system to:
 determine a first regular expression of the adaptively ordered set of regular expressions that matches the first message; 
 add a first node corresponding to the first regular expression to the graph; 
 determine a second regular expression of the adaptively ordered set of regular expressions that matches the first message; 
 add a second node corresponding to the second regular expression to the graph; and 
 add, to the graph, an edge from the first node to the second node to indicate that the first regular expression and the second regular expression match the first message. 
 
     
     
       3. The non-transitory machine-readable storage medium of  claim 1 , wherein the instructions when executed cause the system to:
 determine an acceptable error rate for classifying the second message; and 
 limit traversal of the graph based on the acceptable error rate. 
 
     
     
       4. The non-transitory machine-readable storage medium of  claim 1  wherein the instructions when executed cause the system to:
 determine a first regular expression of the adaptively ordered set of regular expressions that matches the second message; 
 traverse the connected nodes of the graph in an order based on an adaptive order of the adaptively ordered set of regular expressions; and 
 determine that the second message has been misclassified if a second regular expression corresponding to one of the connected nodes in the graph matches the first regular expression and the second regular expression is ordered higher in the adaptive order than the first regular expression. 
 
     
     
       5. The non-transitory machine-readable storage medium of  claim 1 , wherein the instructions when executed cause the system to:
 receive additional message data; and 
 update the graph based on the additional message data. 
 
     
     
       6. The non-transitory machine-readable storage medium of  claim 1 , wherein the instructions when executed cause the system to:
 change an adaptive order of the adaptively ordered set of regular expressions based on at least one of: a time of day, or a day of a week. 
 
     
     
       7. The non-transitory machine-readable storage medium of  claim 1 , wherein the instructions when executed cause the system to:
 determine whether a given regular expression of the set of regular expressions matches each message of the set of messages; and 
 classify a third message using the given regular expression after failing to classify the third message based on the adaptively ordered set of regular expressions. 
 
     
     
       8. The non-transitory machine-readable storage medium of  claim 1 , wherein, to classify the second message, the instructions when executed further cause the system to:
 determine a first regular expression of the adaptively ordered set of regular expressions that matches the second message; 
 traverse the graph from a first node corresponding to the first regular expression to a second node corresponding to a second regular expression of the adaptively ordered set of regular expressions, and determining that the second regular expression corresponding to the second node matches the second message; 
 determine whether the first regular expression or the second regular expression has a higher priority in the adaptively ordered set of regular expressions; and 
 classify the second message with whichever regular expression of the first regular expression or the second regular expression that has the higher priority. 
 
     
     
       9. The non-transitory machine-readable storage medium of  claim 8 , wherein the instructions when executed cause the system to:
 in response to determining that the first regular expression has the higher priority in the adaptively ordered set of regular expressions, classify the second message based on the first regular expression; and 
 in response to determining that the second regular expression has the higher priority in the adaptively ordered set of regular expressions, classify the second message based on the second regular expression. 
 
     
     
       10. The non-transitory machine-readable storage medium of  claim 1 , wherein the instructions when executed cause the system to adaptively order the set of regular expressions based on:
 determining a frequency that each regular expression of the set of regular expressions matches the set of messages; and 
 placing each regular expression of the set of regular expressions into the order of priority to produce the adaptively ordered set of regular expressions based on the determined frequency that the regular expression matches the set of messages. 
 
     
     
       11. The non-transitory machine-readable storage medium of  claim 1 , wherein the regular expressions in the set of regular expressions have an order that is different from the order of priority of the adaptively ordered set of regular expressions. 
     
     
       12. A system comprising:
 a processor; and 
 a non-transitory storage medium storing instructions executable on the processor to:
 compile regular expressions stored in a file into a set of regular expressions having a specified order; 
 adaptively re-order the set of regular expressions into an order of priority based on frequencies that respective regular expressions of the set of regular expressions match a set of messages, the adaptive re-ordering of the set of regular expressions to produce an adaptively ordered set of regular expressions; 
 determine, for a first message of the set of messages, a plurality of regular expressions of the adaptively ordered set of regular expressions that match the first message; 
 create a representation of a graph having connected nodes, wherein the connected nodes correspond to the plurality of regular expressions that match the first message; and 
 classify a second message based on the adaptively ordered set of regular expressions and the graph by traversing the connected nodes in the graph to identify a node corresponding to a particular regular expression that matches the second message and has a highest priority, and classifying the second message based on the particular regular expression. 
 
 
     
     
       13. The system of  claim 12 , wherein, to create the representation of the graph, the instructions are executable on the processor to cause the processor to:
 determine a first regular expression of the adaptively ordered set of regular expressions that matches the first message; 
 add a first node corresponding to the first regular expression to the graph; 
 determine a second regular expression of the adaptively ordered set of regular expressions that matches the first message; 
 add a second node corresponding to the second regular expression to the graph; and 
 add, to the graph, an edge from the first node to the second node to indicate that the first regular expression and the second regular expression match the first message. 
 
     
     
       14. The system of  claim 12 , wherein the instructions are executable on the processor to:
 determine an acceptable error rate for classifying the second message; and 
 limit traversal of the graph based on the acceptable error rate. 
 
     
     
       15. The system of  claim 12 , wherein the instructions are executable on the processor to cause the processor to:
 determine a first regular expression of the adaptively ordered set of regular expressions that matches the second message; 
 traverse the connected nodes of the graph in an order based on an adaptive order of the adaptively ordered set of regular expressions; and 
 determine that the second message has been misclassified if a second regular expression corresponding to one of the connected nodes in the graph matches the second message and the second regular expression is ordered higher in the adaptive order than the first regular expression. 
 
     
     
       16. The system of  claim 12 , wherein the instructions are executable on the processor to:
 receive additional message data; and 
 update the graph based on the additional message data. 
 
     
     
       17. The system of  claim 12 , wherein the instructions are executable on the processor to:
 change an adaptive order of the adaptively ordered set of regular expressions based on at least one of: a time of day, or a day of a week. 
 
     
     
       18. The system of  claim 12 , wherein, to classify the second message, the instructions are executable on the processor to further cause the processor to:
 determine a first regular expression of the adaptively ordered set of regular expressions that matches the second message; 
 traverse the graph from a first node corresponding to the first regular expression to a second node corresponding to a second regular expression of the adaptively ordered set of regular expressions, and determine that the second regular expression corresponding to the second node matches the second message; 
 determine whether the first regular expression or the second regular expression has a higher priority in the adaptively ordered set of regular expressions; and 
 classify the second message with whichever regular expression of the first regular expression or the second regular expression that has the higher priority. 
 
     
     
       19. A method performed by a system comprising a hardware processor, comprising:
 compiling regular expressions stored in a file into a set of regular expressions having a specified order; 
 adaptively re-ordering the set of regular expressions into an order of priority based on frequencies that respective regular expressions of the set of regular expressions match a set of messages, the adaptive re-ordering of the set of regular expressions to produce an adaptively ordered set of regular expressions; 
 determining, for a first message of the set of messages, a plurality of regular expressions of the adaptively ordered set of regular expressions matching the first message; 
 creating a representation of a graph having connected nodes, wherein the connected nodes correspond to the plurality of regular expressions that match the first message; and 
 classifying a second message based on the adaptively ordered set of regular expressions and the graph by traversing the connected nodes in the graph to identify a node corresponding to a particular regular expression that matches the second message and has a highest priority, and classifying the second message based on the particular regular expression.