FILTER REGULAR EXPRESSION

• US 20140297663A1
• Filed: 05/10/2013
• Published: 10/02/2014
• 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 Development Company, L.P. (HP Inc.)
• Inventors: Urago, Jean Marie
• Granted Patent: US 9,235,639 B2
• Time in Patent Office: Days
• US Class Current: 707/754
• 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 a passing set of strings and a blocked set of other strings;

determining a first regular expression based on the passing set;

comparing the first regular expression with the blocked set of other strings to determine that at least one of the other strings would be passed through the first regular expression;

based on the comparison determination, at at least one processor, dividing the passing set into a first subset of the passing set of strings and a second subset of the passing set of strings based on similarity;

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

ORing the second regular expression and the third regular expression to determine a filter regular expression.

2. The method of claim 1, wherein to determine the first regular expression an approach is used including,

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

and

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

3. The method of claim 2, wherein if a respective cell is reused a same number of times as a number of the strings in the passing set, the respective cell is added to the first regular expression as a string literal.

4. The method of claim 3, wherein if the respective cell is string literal and has multiple children, a wild card is added to the first regular expression after the respective cell.

5. The method of claim 4, wherein the approach is further used to determine the second regular expression and third regular expression based on the respective subsets.

6. The method of claim 5,

comparing the second regular expression with the blocked set of other strings to determine that at least one of the other strings would be passed through the second regular expression;

based on the comparison determination of 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

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

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

8. The method of claim 1, further comprising:

monitoring a plurality of alarms; and

using the fourth regular expression to filter the alarms, wherein if the alarms passing through the fourth regular expression yield a specific condition, a set of rules is implemented.

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:

(a) determine a passing set of strings and a blocked set of other strings;

(b) determine a regular expression based on the passing set;

(c) divide the passing set into two subsets of strings based on similarity if one of the other strings would be passed through the regular expression based on a comparison;

(d) for each of the subsets;

determine respective subset regular expressions based on the respective subset and for any of the subsets for which one of the other strings would be passed through the respective subset regular expression, divide the respective subset into two further subsets and repeat (d) on that respective subset; and

ORing the regular expressions of the subsets that do not pass through any of the other strings to generate a filter regular expression.

10. The non-transitory machine-readable storage medium of claim 9, further comprising instructions that, if executed by the at least one processor, cause the device to:

monitor a plurality of alarms; and

use the filter regular expression to filter the alarms, wherein if the alarms match the filter regular expression, a set of rules is implemented.

11. The non-transitory machine-readable storage medium of claim 9, wherein (b) further comprising instructions that, if executed by the at least one processor, cause the device to:

determine data structures from the passing set of strings; and

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

wherein the data structures are one of;

a character and a word, and

wherein the similarity is based on string distance.

12. The non-transitory machine-readable storage medium of claim 11,

wherein if a respective cell is reused a same number of times as a number of the strings in the passing sets, the respective cell is added to the regular expression as a string literal;

and

wherein if the respective cell is string literal and has multiple children, a wild card is added to the regular expression after the respective cell.

13. A computing device comprising:

a string determination module to determine a passing set of strings and a blocked set of other strings;

a regular expression determination module to determine a regular expression based on the passing set;

a string division module to divide the passing set into a two subsets of strings based on similarity if one of the other strings would be passed through the regular expression based on a comparison,

wherein the regular expression determination module and the string division module are used to recursively act on each of the two subsets of strings until none of the other strings are passed through the respective regular expressions; and

an ORing module to OR the regular expressions generated by the regular expression determination module during the recursive actions to generate a filter regular expression.

14. The computing device of claim 13,

wherein the regular expression determination module is caused to further:

determine data structures from the passing set of strings; and

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

wherein if a respective cell is reused a same number of times as a number of the strings in the passing sets, the respective cell is added to the regular expression as a string literal; and

wherein if the respective cell is string literal and has multiple children, a wild card is added to the regular expression after the respective cell.

15. The computing device of claim 14, further comprising:

an alarm monitoring module to monitor a plurality of alarms; and

an alarm filtering module to use the filter regular expression to filter the alarms; and

a rule module to implement a set of rules if any of the alarms pass through the filter regular expression.