Method and system for processing a group of resource identifiers

• US 8,738,656 B2
• Filed: 08/23/2010
• Issued: 05/27/2014
• Est. Priority Date: 08/23/2010
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kirshenbaum, Evan R.
• Primary Examiner(s): VU, BAI DUC
• Application Number:
  US12/861,736
• Publication Number:
  US 20120047180A1
• Time in Patent Office: 1,373 Days
• Field of Search: None
• US Class Current: 707/797
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data

Abstract

The present disclosure provides a computer-implemented method of processing a group of resource identifiers. The method includes generating a node candidate based on a resource identifier, wherein the node candidate includes a component corresponding to a portion of the resource identifier according to a dimension of specificity. The method also includes adding the lattice node candidate to a corpus lattice based on whether a matching corpus node corresponding to the node candidate is already included in the corpus lattice. The corpus lattice includes corpus nodes corresponding to a plurality of resource identifiers. The method also includes generating a pruned corpus lattice by a process that includes determining that a child node in the corpus lattice is compatible with a parent node of the child node and removing the child node from the corpus lattice. The method also includes generating an output file corresponding to the pruned URL lattice.

Claims

1. A method, comprising:

generating a node candidate in a system memory based on a resource identifier, wherein the node candidate includes a component corresponding to a portion of the resource identifier according to a dimension of specificity;

adding the node candidate to a corpus lattice in the system memory based, at least in part, on whether a matching corpus node corresponding to the node candidate is already included in the corpus lattice;

wherein the corpus lattice includes corpus nodes corresponding to a plurality of resource identifiers;

generating a pruned corpus lattice by a process comprising determining that a child corpus node in the corpus lattice is compatible with a parent corpus node of the child corpus node and removing the child corpus node from the corpus lattice, wherein the child corpus node is compatible with the parent corpus node if a first data set associated with the child corpus node and a second data set associated with the parent corpus node do not conflict; and

generating an output data structure corresponding to the pruned corpus lattice.

2. The method of claim 1, wherein the first and second data sets each include a data field name and a field state corresponding to the data field name, wherein the field state indicates a probability that the data field name is of a target class with respect to the corresponding corpus node.

3. The method of claim 2, wherein the first and second data sets are determined to be compatible if no data field name corresponds to a field state of “

strong positive”

in one of the first and second data sets and to “

strong negative”

in the other of the first and second data sets.

4. The method of claim 1, wherein the first and second data sets include a plurality of data field names and an occurrence count for each of the plurality of data field names;

wherein the occurrence count corresponds to a number of times that the corresponding data field name appears in a group of URLs corresponding to a respective corpus node; and

wherein the occurrence count is used to determine an importance level for the data field with respect to the respective corpus node.

5. The method of claim 4, wherein the first and second data sets are determined to be compatible based on a comparison of the importance levels determined for the data fields of the child corpus node and the importance levels determined for the data fields of the parent corpus node.

6. The method of claim 1, wherein:

the resource identifier comprises a Uniform Resource Locator (URL);

the node candidate includes a second component corresponding to a second portion of the resource identifier according to a second dimension of specificity; and

the dimension of specificity comprises a host of the URL and the second dimension of specificity comprises a path of the URL.

7. The method of claim 1, wherein adding the node candidate comprises:

identifying a first, unexpanded, corpus node as a parent of a second corpus node corresponding with the node candidate;

adding as a child node of the first corpus node a node corresponding to an extension of the first corpus node along a dimension of specificity; and

marking the first corpus node as an expanded node.

8. The method of claim 1, wherein generating the output data structure comprises generating an information table usable by a URL recognizer to identify a search term in a query field of a newly encountered URL.

9. The method of claim 1, wherein generating the output data structure comprises generating a case usable by a training system to develop a classifier, wherein the case includes a plurality URLs.

10. The method of claim 1, further comprising:

receiving a first resource identifier matching a pattern corresponding to a first corpus node in the pruned corpus lattice;

identifying, based on the output data structure, a rule applicable to the first resource identifier;

receiving a second resource identifier matching a pattern corresponding to the first corpus node; and

identifying, based on the output data structure, the rule as being applicable to the second resource identifier.

11. The method of claim 1, wherein the child corpus node is compatible with the parent corpus node if a state of a first data field in the first data set does not conflict with a state of a first data field in the second data set.

12. A computer system, comprising:

a processor that is configured to execute machine-readable instructions; and

a memory device that stores instruction modules that are executable by the processor, the instruction modules comprising;

a node candidate generator, configured to generate a node candidate based on a resource identifier, wherein the node candidate includes a component corresponding to a portion of the resource identifier according to a dimension of specificity;

a lattice generator configured to add the node candidate to a corpus lattice based, at least in part, on whether a matching corpus node corresponding to the node candidate is already included in the corpus lattice;

wherein the corpus lattice includes corpus nodes corresponding to a plurality of resource identifiers;

a lattice pruner configured to generate a pruned corpus lattice by a process comprising determining that a child corpus node in the corpus lattice is compatible with a parent corpus node of the child corpus node and removing the child corpus node from the corpus lattice, wherein the child corpus node is compatible with the parent corpus node if a first data set associated with the child corpus node and a second data set associated with the parent corpus node do not conflict; and

an output generator configured to generate an output data structure corresponding to the pruned corpus lattice.

13. The computer system of claim 12, wherein the first and second data sets each include a data field name and a field state corresponding to the data field name, wherein the field state indicates a probability that the data field name is of a target class with respect to the corresponding corpus node.

14. The computer system of claim 12, wherein:

the resource identifier comprises a Uniform Resource Locator (URL);

the node candidate includes a second component corresponding to a second portion of the resource identifier according to a second dimension of specificity; and

the dimension of specificity comprises a host of the URL and the second dimension of specificity comprises a path of the URL.

15. The computer system of claim 12, wherein the lattice generator is configured to add the node candidate to the corpus lattice by a process comprising:

identifying a first, unexpanded, corpus node as a parent of a second corpus node corresponding with the node candidate;

adding as a child node of the first corpus node a node corresponding to an extension of the first corpus node along a dimension of specificity; and

marking the first corpus node as an expanded node.

16. The computer system of claim 12, wherein the child corpus node is compatible with the parent corpus node if a state of a first data field in the first data set does not conflict with a state of a first data field in the second data set.

17. A non-transitory computer readable medium, comprising code configured to direct a processor to:

generate a node candidate based on a resource identifier, wherein the node candidate includes a component corresponding to a portion of the resource identifier according to a dimension of specificity;

add the node candidate to a corpus lattice based, at least in part, on whether a matching corpus node corresponding to the node candidate is already included in the corpus lattice;

wherein the corpus lattice includes corpus nodes corresponding to a plurality of resource identifiers;

generate a pruned corpus lattice by a process comprising determining that a child corpus node in the corpus lattice is compatible with a parent corpus node of the child corpus node and removing the child corpus node from the corpus lattice, wherein the child corpus node is compatible with the parent corpus node if a first data set associated with the child corpus node and a second data set associated with the parent corpus node do not conflict; and

generate an output data structure corresponding to the pruned corpus lattice.

18. The non-transitory computer readable medium of claim 17, wherein:

the resource identifier comprises a Uniform Resource Locator (URL);

the node candidate includes a second component corresponding to a second portion of the resource identifier according to a second dimension of specificity; and

the dimension of specificity comprises a host of the URL and the second dimension of specificity comprises a path of the URL.

19. The non-transitory computer readable medium of claim 17, comprising code configured to direct a processor to:

identify a first, unexpanded, corpus node as a parent of a second corpus node corresponding with the node candidate;

add as a child node of the first corpus node a node corresponding to an extension of the first corpus node along a dimension of specificity; and

mark the first corpus node as an expanded node.

20. The non-transitory computer readable medium of claim 17, wherein the child corpus node is compatible with the parent corpus node if a state of a first data field in the first data set does not conflict with a state of a first data field in the second data set.