Ordering regular expressions

Patent metadata

Field	Value
Publication number	US-10754894-B2
Application number	US-201615388184-A
Country	US
Kind code	B2
Filing date	Dec 22, 2016
Priority date	Dec 22, 2016
Publication date	Aug 25, 2020
Grant date	Aug 25, 2020

Abstract

In examples, an apparatus comprises: a memory, and a processor coupled to the memory. The processor to: adaptively order an ordered set of regular expressions based on training messages to produce a set of adaptively ordered regular expressions having an adaptive order, determine a first of the adaptively ordered regular expressions that matches an additional message, and determine whether a second of the adaptively ordered regular expressions matches the additional message. Responsive to determining that the second of the other of the adaptively ordered regular expressions matches the additional message, the processor to: classify the additional message with the first regular expression if the first regular expression has a higher priority in the adaptive order; and classify the additional message with the second regular expression if the second regular expression has a higher priority in the adaptive order.

First claim

The invention claimed is:

1. A method performed by a system comprising a hardware processor, the method comprising:
adaptively ordering an ordered set of regular expressions based on training messages to produce a set of adaptively ordered regular expressions having an adaptive order;
creating a representation of a graph, wherein connected nodes of the graph correspond to regular expressions that match a same message of the training messages;
determining a first regular expression of the adaptively ordered regular expressions that matches an additional message;
traversing 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 regular expressions, and determining whether the second regular expression corresponding to the second node matches the additional message;
determining whether the first regular expression or the second regular expression has a higher priority in the ordered set of regular expressions; and
classifying the additional message with whichever regular expression of the first regular expression or the second regular expression has the higher priority.

2. The method of claim 1 , wherein the adaptive ordering of the ordered set of regular expressions comprises:
determining a frequency that each regular expression of the ordered set of regular expressions matches one or more of the training messages; and
reordering the ordered set of regular expressions into the set of adaptively ordered regular expressions based on the frequencies.

3. The method of claim 1 , comprising:
in response to determining that the first regular expression has the higher priority in the ordered set of regular expressions, classifying the additional message based on the first regular expression; and
in response to determining that the second regular expression matches the additional message and that the second regular expression has the higher priority in the ordered set of regular expressions, classifying the additional message based on the second regular expression.

4. The method of claim 1 , wherein each regular expression of the adaptively ordered regular expressions corresponds to a different node of the graph,
wherein an edge from the first node to the second node in the graph indicates that the first regular expression corresponding to the first node matches a same message of the training messages as the second regular expression corresponding to the second node.

5. The method of claim 1 , comprising:
determining an acceptable error rate for classifying a message; and
connecting a number of nodes of the graph based on the acceptable error rate.

6. The method of claim 1 , comprising:
receiving additional messages; and
periodically updating the graph based on the additional messages.

7. The method of claim 1 , wherein the regular expressions in the ordered set of regular expressions have a priority order that is different from a priority order according to the adaptive order of the regular expressions in the adaptively ordered regular expressions.

8. A system comprising:
a processor; and
a non-transitory storage medium storing instructions executable on the processor to:
adaptively order an ordered set of regular expressions based on training messages to produce a set of adaptively ordered regular expressions having an adaptive order;
create a representation of a graph comprising a plurality of nodes corresponding to respective regular expressions of the adaptively ordered regular expressions, wherein a first node in the graph is connected to a second node in the graph, and wherein a first regular expression corresponding to the first node and a second regular expression corresponding to the second node match a same message of the training messages;
determine that the first regular expression of the adaptively ordered regular expressions matches an additional message;
traverse the graph from the first node to the second node, and determine whether the second regular expression corresponding to the second node matches the additional message;
responsive to determining that the second regular expression matches the additional message:
classify the additional message with the first regular expression if the first regular expression has a higher priority than the second regular expression in the ordered set of regular expressions; and
classify the additional message with the second regular expression if the second regular expression has a higher priority than the first regular expression in the ordered set of regular expressions.

9. The system of claim 8 , wherein the instructions are executable on the processor to:
determine a frequency that each regular expression of the ordered set of regular expressions matches one or more of the training messages; and
reorder the ordered set of regular expressions into the set of adaptively ordered regular expressions based on the frequencies.

10. The system of claim 8 , wherein the regular expressions in the ordered set of regular expressions have a priority order that is different from a priority order according to the adaptive order of the regular expressions in the adaptively ordered regular expressions.

11. The system of claim 8 , wherein the graph comprises an edge that connects the first node and the second node.

12. The system of claim 8 , wherein the instructions are executable on the processor to:
determine an acceptable error rate for classifying a message; and
include a number of connected nodes in the graph based on the acceptable error rate.

13. The system of claim 8 , wherein the instructions are executable on the processor to:
determine whether any of the ordered set of regular expressions matches each of the training messages; and
responsive to determining that the ordered set of regular expressions does not match any of the training messages:
classify the additional message with one of the ordered set of regular expressions.

14. A non-transitory machine-readable storage medium comprising instructions that upon execution cause a system to:
adaptively order an ordered set of regular expressions based on training messages to produce a set of adaptively ordered regular expressions having an adaptive order;
construct a representation of a graph that represents regular expressions of the adaptively ordered regular expressions;
determine a first regular expression of the adaptively ordered regular expressions that matches an additional 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 regular expressions, wherein the first node is connected to the second node in the graph based on the first regular expression and the second regular expression matching a same message of the training messages;
determine whether the second regular expression corresponding to the second node matches the additional message; and
responsive to determining that the second regular expression matches the additional message:
classify the additional message with the first regular expression in response to determining that the first regular expression has a higher priority than the second regular expression in the ordered set of regular expressions; and
classify the additional message with the second regular expression in response to determining that the second regular expression has a higher priority than the first regular expression in the ordered set of regular expressions.

15. The non-transitory machine-readable sto

Assignees

• Hewlett Packard Entpr Dev Lp
• Micro Focus Llc

Inventors

• Revach Eli
• Shtossel Amitai Shlomo
• Vizer Fernando

Classifications

• G06N5/022

  Knowledge engineering; Knowledge acquisition · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/35

  Clustering; Classification · CPC title

• G06F16/90348 Primary

  by searching ordered data, e.g. alpha-numerically ordered data · CPC title