Filter regular expression

• US 9,235,639 B2
• Filed: 05/10/2013
• Issued: 01/12/2016
• Est. Priority Date: 03/28/2013
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Urago, Jean Marie
• Primary Examiner(s): Fan, Shiow-Jy
• Application Number:
  US13/891,689
• Publication Number:
  US 20140297663A1
• Time in Patent Office: 977 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

Example embodiments disclosed herein relate to determining a regular expression from a passing set of strings and a blocked set of strings. A regular expression is determined based on the passing set. The regular expression is compared to the blocked set. The passing set is divided into subsets based on the comparison. Regular expressions are determined for the subsets and are ORed together to determine a filter regular expression.

Claims

1. A method comprising:

determining, by a system comprising a processor, a first regular expression based on a passing set of first strings corresponding to alarms that are to pass through a filter;

comparing, by the system, the first regular expression with a blocked set of second strings to determine that at least a second string of the second strings would be passed through the first regular expression, the blocked set of second strings corresponding to alarms that are to be blocked from passing through the filter;

based on the determining that the at least one second string would be passed through the first regular expression, dividing, by the system, the passing set into a first subset of the first strings and a second subset of the first strings based on similarity;

determining, by the system, a second regular expression based on the first subset, and a third regular expression based on the second subset;

in response to determining that none of the blocked set of second strings would pass through each of the second regular expression and the third regular expression,

combining, by the system, the second regular expression and the third regular expression to determine a filter regular expression that represents the filter,

filtering, by the system using the filter regular expression, an alarm received from a device; and

in response to the received alarm passing through the filter regular expression, performing, by the system, an action to address an issue corresponding to the received alarm.

2. The method of claim 1, wherein determining the first regular expression comprises:

determining data structures from the first strings; and

starting with the data structure of a first of the first strings, iteratively adding the data structures into a graph using an algorithm that, based on a priority, maximizes a number of re-used cells in the graph, and maximizes a number of consecutive matching cells.

3. The method of claim 2, further comprising:

in response to determining that a given cell is re-used a same number of times as a number of the first strings in the passing set, adding the given cell to the first regular expression as a string literal.

4. The method of claim 3, further comprising:

in response to determining that the given cell is the string literal and has multiple children, adding a wild card to the first regular expression after the given cell.

5. The method of claim 1, further comprising:

comparing the second regular expression with the blocked set of second strings to determine that a given second string of the second strings would be passed through the second regular expression;

in response to determining that the given second string would pass through the second regular expression,

dividing the first subset into a third subset and a fourth subset based on similarity;

determining a fifth regular expression based on the third subset, and a sixth regular expression based on the fourth subset; and

combining the fifth regular expression and the sixth regular expression to update the second regular expression.

6. The method of claim 2, wherein each data structure of the data structures is a character or a word.

7. The method of claim 1, further comprising:

in response to determining that a second string of the blocked set of second strings would pass through the second regular expression,

dividing the first subset into a third subset of the first strings and a fourth subset of the first strings,

determining a fourth regular expression based on the third subset, and a fifth regular expression based on the fourth subset,

combining the fourth regular expression, the fifth regular expression, and the third regular expression to generate a further filter regular expression that represents the filter,

filter, using the further filter regular expression, the received alarm; and

in response to the received alarm passing through the further filter regular expression, perform an action to address an issue corresponding to the received alarm.

8. The method of claim 1, wherein combining the second regular expression and the third regular expression comprises ORing the second regular expression and the third regular expression.

9. A non-transitory machine-readable storage medium storing instructions that, if executed by at least one processor of a device, cause the device to:

determine a regular expression based on a passing set of first strings corresponding to alarms that are to pass through a filter;

divide the passing set into subsets of the first strings based on similarity in response to determining that a second string of a blocked set of second strings would be passed through the regular expression, the blocked set of second strings corresponding to alarms that are to be blocked from passing through the filter;

perform a process comprising;

determining respective subset regular expressions based on the subsets,

for any given subset of the subsets for which a second string of the blocked set of second strings would be passed through the respective subset regular expression, dividing the given subset into further subsets, and re-iterating the performing of the process for the further subsets;

ORing the subset regular expressions of the subsets that do not pass through any of the second strings to generate a filter regular expression representing the filter;

filter, using the filter regular expression, an alarm received from a device; and

in response to the received alarm passing through the filter regular expression, perform an action to address an issue corresponding to the received alarm in response to the received alarm matching a rule.

10. The non-transitory machine-readable storage medium of claim 9, wherein determining the regular expression comprises:

determine data structures from the passing set of first strings; and

starting with the data structure for a first of the first strings, iteratively add the data structures into a graph using an algorithm that, based on a priority, maximizes a number of re-used cells in the graph, and maximizes a number of consecutive matching cells,

wherein each data structure of the data structures is one of;

a character and a word, and

wherein the similarity is based on string distance.

11. The non-transitory machine-readable storage medium of claim 10, wherein the instructions if executed cause the device to:

in response to determining that a given cell is re-used a same number of times as a number of the first strings in the passing set, add the given cell to the regular expression as a string literal; and

in response to determining that the given cell is the string literal and has multiple children, add a wild card to the regular expression after the given cell.

12. A computing device comprising:

at least one processor; and

a non-transitory machine-readable storage medium storing instructions executable on the at least one processor to;

determine a first regular expression based on a passing set of first strings corresponding to alarms that are to pass through a filter;

divide the passing set into first and second subsets of the first strings based on similarity in response to determining that a second string of a blocked set of second strings would be passed through the regular expression, the blocked set of second strings corresponding to alarms that are to be blocked from passing through the filter,

determine a second regular expression based on the first subset, and a third regular expression based on the second subset;

in response to determining that none of the blocked set of second strings would pass through each of the second regular expression and the third regular expression,

OR the second and third regular expressions to generate a filter regular expression representing the filter, and

filter, using the filter regular expression, an alarm received from a device; and

in response to the received alarm passing through the filter regular expression, perform an action to address an issue corresponding to the received alarm.

13. The computing device of claim 12, wherein the determining of the first regular expression comprises:

determining data structures from the passing set of first strings; and

starting with the data structure for a first of the first strings, iteratively add the data structures into a graph using an algorithm that, based on a priority, maximizes a number of re-used cells in the graph, and maximizes a number of consecutive matching cells.