Robust wrappers for web extraction
A computer-implemented method to determine a robust wrapper includes developing a model indicative of the temporal history of a document, such as a web document written in a markup language. Based on the developed model, robustness characteristics are determined for a plurality of different wrappers representing associated paths to the data item in a representation of the document. Based on a result of the determining operation, a result wrapper of the plurality of wrappers is provided. The result wrapper has a desired robustness characteristic.
1. A computer-implemented method to determine a robust wrapper representing a data item of a plurality of data items in a document represented by a markup language, comprising:
based on archival data representative of a temporal history of the document, developing a model indicative of the temporal history;
based on the developed model, determining robustness characteristics for a plurality of different wrappers representing associated paths to the data item in a representation of the document, the robustness characteristics for each wrapper representing a likelihood that the corresponding wrapper will continue to be effective for extracting the data item when the document changes; and
based on a result of the determining operation, providing, as a result wrapper, one of the plurality of wrappers that has a desired robustness characteristic;
wherein the representation of the document relates to a tree having a plurality of nodes;
wherein the temporal history of the document relates at least to an original tree and a plurality of changed trees indicative of trees that appeared during the temporal history of the document that are different from the original tree;
wherein the developing operation includes:
obtaining a plurality of pairs, each one of the plurality of pairs including a first element (T) and a second element (T′), wherein T is the original tree and T′ is a different one of the plurality of changed trees;
determining a plurality of different change operations indicative of changes made to change T into T′ for each one of the plurality of pairs; and
associating each one of the plurality of different change operations with a probability value indicative of a probability that the associated change operation is applied to the document.
2. The method of claim 1 , wherein at least one of the nodes represents a markup language tag.
3. The method of claim 1 , wherein the developing operation uses gradient descent.
4. The method of claim 1 , wherein the plurality of different change operations includes at least one of a group consisting of: a) removing a node; b) changing a node; and c) inserting a node.
5. The method of claim 1 , wherein the determining operation comprises:
evaluating the plurality of wrappers to determine whether the path associated with each wrapper leads to the data item in the document when the document is changed in accordance with the plurality of different change operations;
based on a result from the evaluating operation and the probability values associated with the plurality of different change operations, determining a success/failure probability for each one of the wrappers.
6. The method of claim 5 , wherein the providing operation is based on comparing the success/failure probabilities of the plurality of wrappers.
7. The method of claim 1 , wherein the plurality of different wrappers are minimal wrappers.
8. The method of claim 1 , wherein determining includes evaluating the plurality of wrappers to determine whether the path associated with each wrapper leads to the data item in the representation of the document when the document is changed according to various different change operations.
9. The method of claim 8 , wherein each of the various different change operations has associated therewith a probability of application of the associated one of the different change operations to the document.
10. A computing system for determining a robust wrapper representing a data item of a plurality of data items in a document represented by a markup language, the computing system comprising one or more computing devices that include one or more processors and memory operable to:
based on archival data representative of a temporal history of the document, develop a model indicative of the temporal history;
based on the developed model, determine robustness characteristics for a plurality of different wrappers representing associated paths to the data item in a representation of the document, the robustness characteristics for each wrapper representing a likelihood that the corresponding wrapper will continue to be effective for extracting the data item when the document changes; and
based on a result from the determination of the robustness characteristics, provide, as a result wrapper, one of the plurality of wrappers that has a desired robustness characteristic;
wherein the representation of the document relates to a tree having a plurality of nodes;
wherein the temporal history of the document relates at least to an original tree and a plurality of changed trees indicative of trees that appeared during the temporal history of the document that are different from the original tree;
wherein the develop operation includes:
obtain a plurality of pairs, each one of the plurality of pairs including a first element (T) and a second element (T′), wherein T is the original tree and T′ is a different one of the plurality of changed trees;
determine a plurality of different change operations indicative of changes made to change T into T′ for each one of the plurality of pairs; and
associate each one of the plurality of different change operations with a probability value indicative of a probability that the associated change operation is applied to the document.
11. The computing system of claim 10 , wherein at least one of the nodes represents a markup language tag.
12. The computing system of claim 10 , wherein the computing system is further operable to:
evaluate the plurality of wrappers to determine whether the path associated with each wrapper leads to the data item in the document when the document is changed in accordance with the plurality of different change operations; and
based on a result from the evaluation of the plurality of wrappers and the probability values associated with the plurality of different change operations, determine a success/failure probability for each one of the wrappers.
13. The computing system of claim 10 , wherein determining includes evaluating the plurality of wrappers to determine whether the path associated with each wrapper leads to the data item in the representation of the document when the document is changed according to various different change operations.
14. The computing system of claim 13 , wherein each of the various different change operations has associated therewith a probability of application of the associated one of the different change operations to the document.
15. A non-transitory, computer readable medium embodied in a tangible form including executable computer program code operable to determine a robust wrapper representing a data item of a plurality of data items in a document represented by a markup language, wherein the computer readable medium includes:
executable computer code operable to develop, based on archival data representative of a temporal history of the document, a model indicative of the temporal history;
executable computer code operable to determine, based on the developed model, robustness characteristics for a plurality of different wrappers representing associated paths to the data item in a representation of the document, the robustness characteristics for each wrapper representing a likelihood that the corresponding wrapper will continue to be effective for extracting the data item when the document changes, wherein the representation of the document relates to a tree having a plurality of nodes, and wherein the temporal history of the document relates at least to an original tree and a plurality of changed trees indicative of trees that appeared during the temporal history of the document that are different from the original tree; and
executable computer code operable to provide, based on a result of the determining operation, as a result wrapper, one of the plurality of wrappers that has a desired robustness characteristic;
wherein the executable computer code operable to develop the model includes:
executable computer code operable to obtain a plurality of pairs, each one of the plurality of pairs including a first element (T) and a second element (T′), wherein T is the original tree and T′ is a different one of the plurality of changed trees;
executable computer code operable to determine a plurality of different change operations indicative of changes made to change T into T′ for each one of the plurality of pairs; and
executable computer code operable to associate each one of the plurality of different change operations with a probability value indicative of a probability that the associated change operation is applied to the document.
16. The computer readable medium of claim 15 , wherein at least one of the nodes represents a markup language tag.
17. The computer readable medium of claim 15 , wherein the computer readable medium further includes:
executable computer code operable to evaluate the plurality of wrappers to determine whether the path associated with each wrapper leads to the data item in the document when the document is changed in accordance with the plurality of different change operations;
executable computer code operable to determine, based on a result from the evaluation of the plurality of wrappers and the probability values associated with the plurality of different change operations, a success/failure probability for each one of the wrappers.
18. The computer readable medium of claim 15 , wherein determining includes evaluating the plurality of wrappers to determine whether the path associated with each wrapper leads to the data item in the representation of the document when the document is changed according to various different change operations.
19. The computer readable medium of claim 18 , wherein each of the various different change operations has associated therewith a probability of application of the associated one of the different change operations to the document.