Visual and interactive wrapper generation, automated information extraction from web pages, and translation into xml

• US 20050022115A1
• Filed: 05/28/2002
• Published: 01/27/2005
• Est. Priority Date: 05/31/2001
• Status: Active Grant

• Current Assignee: Lixto Software GmbH (Mckinsey & Company Incorporated)
• Original Assignee: Lixto Software GmbH (Mckinsey & Company Incorporated)
• Inventors: Gottlob, Georg, Baumgartner, Roberts, I'Lesca, Sergio, Herzoo, Marcus
• Granted Patent: US 7,581,170 B2
• Time in Patent Office: Days
• US Class Current: 715/205
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

A method and a system for information extraction from Web pages formatted with markup languages such as HTML [8]. A method and system for interactively and visually describing information patterns of interest based on visualized sample Web pages [5,6,16-29]. A method and data structure for representing and storing these patterns [1]. A method and system for extracting information corresponding to a set of previously defined patterns from Web pages [2], and a method for transforming the extracted data into XML is described. Each pattern is defined via the (interactive) specification of one or more filters. Two or more filters for the same pattern contribute disjunctively to the pattern definition [3], that is, an actual pattern describes the set of all targets specified by any of its filters. A method and for extracting relevant elements from Web pages by interpreting and executing a previously defined wrapper program of the above form on an input Web page [9-14] and producing as output the extracted elements represented in a suitable data structure. A method and system for automatically translating said output into XML format by exploiting the hierarchical structure of the patterns and by using pattern names as XML tags is described.

Claims

1. A wrapper generation system comprising:

a network including at least one example document and at least one production document; and

a visual builder that is adapted to interactively generate a wrapper program by letting a user visually and interactively declare at least one desired property of example-elements to be extracted from the example document thereby creating user declarations;

a program evaluator adapted to execute a wrapper program over the production document and to extract desired production elements from the production document and to translate the production elements into XML yielding an XML companion of the production document.

2. The wrapper generation system of claim 1, wherein the visual builder further includes:

an extraction pattern builder adapted to provide a visual interface for a user to specify at least one desired pattern whose instances are to be extracted from the document.

3. The wrapper generation system of claim 2, wherein the visual builder further includes:

an XML translation builder adapted to interactively generate an XML translation scheme based on user specifications that specifies how to translate at least one pattern into XML using XML translation rules.

4. The wrapper generation system of claim 1, wherein the program evaluator further includes:

an extractor that extracts data from the production document and provides an XML document.

5. The wrapper generation system of claim 2, further including:

an XML translator that performs actual mapping from a set of pattern instances to an XML document.

6. The wrapper generation system of claim 1, wherein the example document is received in a browser window.

7. The wrapper generation system of claim 1, wherein a user controls wrapper generation, selects examples from the example document and adds further user specifications.

8. The wrapper generation system of claim 7, wherein the pattern is generated from conditions that are obtained from the examples and the user specification.

9. The wrapper generation system of claim 2 wherein the specification of a pattern is organized according to a logical combination of conditions.

10. The wrapper generation system of claim 9, wherein on applying the wrapper to the production document a data structure representing all elements that match the pattern is produced.

11. The wrapper generation system of claim 10 wherein the wrapper is applied to a plurality of production documents.

12. The wrapper generation system of claim 10, wherein the data structure is further translated to at least one output data structure.

13. The wrapper generation system of claim 9 wherein at least one of said conditions is a location condition that is obtained by generalizing a location descriptor of a selected example-element.

14. The wrapper generation system of claim 9 wherein at least one of said conditions is a refinement condition that refines a set of instances of the pattern based on explicit user commands.

15. The wrapper generation system of claim 14 wherein the refinement condition is an internal condition expressing properties which the instances of the pattern must fulfill regardless of their context.

16. The wrapper generation system of claim 14 wherein the refinement condition is a contextual condition that expresses restrictions on the context in which instances of the pattern are allowed to appear.

17. The wrapper generation system of claim 14 wherein the refinement conditions is a range condition that expresses that among the pattern instances which satisfy all other imposed conditions of a given filter, only those of each context are to be considered valid, which occur in that context within specified position ranges with respect to document order, and

18. The wrapper generation system of claim 14 wherein the refinement condition is an auxiliary condition which further refines the set of instances.

19. The wrapper generation system of claim 1 wherein the example document is a Web page.

20. The wrapper generation system of claim 1 wherein at least one production document is a Web page.

21. The wrapper generation system of claim 1 wherein the example document is formatted in HTML and where at least one of said example-elements corresponds to a node or to a sequence of nodes of an HTML parsing-tree of the example-document in which said example-element occurs.

22. The wrapper generation system of claim 1 wherein the production documents are formatted in HTML and where at least one of said production-elements corresponds to a node or to a sequence of nodes of an HTML parsing-tree of the production document in which said example-element occurs.

23. The wrapper generation system of claim 1 wherein the example-documents is formatted in HTML and where at least one of said example-elements corresponds to an HTML element whose type is selected from a group consisting of:

html, table, tr, th, tfoot, thead, col, colgroup, caption, td, p, br, div, blockquote, body, head, h1, h2, h3, h4, h5, h6, dl, dd, dt, ol, ul, li, dir, menu, form, input, select, option, address, center, pre, xmp, nobr, wbr, hr, img, b, i, font-size, font-color, underline, blink, a (anchors), href, tt, big, sup, sub, cite, code, strong, em, samp, area, map, script, and CSS styles applied to the content and structure.

24. The wrapper generation system of claim 1 wherein the production document is formatted in HTML and where at least one of said production-elements corresponds to an HTML element whose type is selected from a group consisting of:

html, table, tr, th, tfoot, thead, col, colgroup, caption, td, p, br, div, blockquote, body, head, h1, h2, h3, h4, h5, h6, dl, dd, dt, ol, ul, li, dir, menu, form, input, select, option, address, center, pre, xmp, nobr, wbr, hr, img, b, i, font-size, font-color, underline, blink, a (anchors), href, tt, big, sup, sub, cite, code, strong, em, samp, area, map, script, and CSS styles applied to the content and structure.

25. The wrapper generation system of claim 13, wherein said generalized location descriptor is obtained from a corresponding location descriptor by syntactic generalization operations.

26. The wrapper generation system of claim 25, wherein said generalized location descriptor is obtained by inserting zero or more wildcards, by substituting wildcards for zero or more elements and by eliminating zero or more elements from said location descriptor.

27. The wrapper generation system of claim 13, wherein the example-document is tree-structured and wherein each location descriptor, called plain tree path, created for an example-element occurring in an example-document corresponds to the sequence of element-types on the path in the parsing tree of said example-document from the root to said example-element, and where the corresponding generalized location descriptor, called incompletely specified tree path, is obtained from said location descriptor by inserting zero or more wildcards, by substituting wildcards for zero or more elements and by eliminating zero or more elements from said location descriptor.

28. The wrapper generation system of claim 13, wherein at least one production-document is tree-structured and wherein each location descriptor, called plain tree path, created for an example-element occurring in an example-document corresponds to the sequence of element-types on the path in the parsing tree of said example-document from the root to said example-element, and where the corresponding generalized location descriptor, called incompletely specified tree path, is obtained from said location descriptor by inserting zero or more wildcards, by substituting wildcards for zero or more elements and by eliminating zero or more elements from said location descriptor.

29. The wrapper generation system of claim 13, wherein at least one production-document is in HTML format and wherein each location descriptor, called plain tree path, created for an example-element occurring in an example-document corresponds to the sequence of HTML tags on the path in the parsing tree of said example-document from the root to said example-element, and where the corresponding generalized location descriptor, called incompletely specified tree path, is obtained from said location descriptor by inserting zero or more wildcards, by substituting wildcards for zero or more HTML tags and by eliminating zero or more elements from said location descriptor.

30. The wrapper generation system of claim 13, wherein said generalized location descriptor is set to a default value that is obtained from said location descriptor by prefixing each element in the location descriptor with a wildcard.

31. The wrapper generation system of claim 29 wherein a wildcard prefixing an element occurring within the generalized location descriptor is interpreted as an arbitrary chain of elements whose type differs from a type corresponding to said element.

32. The wrapper generation system of claim 29 wherein a user is given a possibility to change and overwrite said default value.

33. The wrapper generation system of claim 2, wherein each of the pattern is selected from a set consisting of tree patterns, string patterns and document patterns, wherein instances of said tree patterns are subtrees of document parse-trees, instances of said string patterns are substrings of text strings occurring on some documents and instances of said document patterns are documents.

34. The wrapper generation system of claim 2, wherein the pattern description generated for the pattern contains a Boolean combination of all conditions that contribute to the definition of said pattern.

35. The wrapper generation system of claim 2, wherein the pattern description generated for the pattern consists of a set of rules formulated in a logic programming language.

36. The wrapper generation system of claim 2, wherein the pattern description generated for the pattern consists of a set of rules formulated in a logic programming language and where said wrapper consists of a logic program containing said rules.

37. The wrapper generation system of claim 36 wherein the variables and terms of said logic program range over elements occurring in the documents to which said wrapper is applied.

38. The wrapper generation system of claim 36 wherein the variables and terms of said logic program range over elements and strings occurring in the documents to which said wrapper is applied.

39. The wrapper generation system of claim 36 wherein the variables and terms of said logic program range over elements, element-lists, and strings occurring in the documents to which said wrapper is applied.

40. The wrapper generation system of claim 36 wherein said example document and production document are tree-structured and where the variables of said logic program range over nodes of the parsing trees of documents to which said wrapper is applied.

41. The wrapper generation system of claim 36 wherein said example document and production document are tree-structured and where the variables of said logic program range over nodes of the parsing trees and over strings occurring in the documents to which said wrapper is applied.

42. The wrapper generation system of claim 36 wherein said production document and example document are tree-structured and where the variables of said logic program range over nodes and sequences of nodes of the parsing trees of documents to which said wrapper is applied.

43. The wrapper generation system of claim 36 wherein said production document and example document are tree-structured and where the variables of said logic program range over nodes of the parsing tree of documents to which said wrapper is applied, over sequences of such nodes, and over strings occurring in documents to which said wrapper is applied.

44. The wrapper generation system of claim 36 wherein each condition that contributes to the definition of a pattern is represented by at least one atom in the body of a rule of said logic program which contributes to the definition of said pattern.

45. The wrapper generation system of claim 36 wherein each of said logic programming rules represents a filter consisting of a rule body that represents all conditions contributing to said filter in form of a conjunction of atoms and of a rule head whose predicate corresponds to the pattern said filter is associated with.

46. The wrapper generation system of claim 36 wherein said logic program is a datalog program making use of special predefined predicates for expressing conditions.

47. The wrapper generation system of claim 15 wherein the internal condition belongs to a set consisting of contains conditions and noncontains conditions

wherein the contains conditions impose one or more restrictions on some subelement of the pattern to be defined and

the notcontains conditions require that instances of the pattern to be defined do not contain any subelement that satisfies specified restrictions.

48. The wrapper generation system of claim 15 wherein an element of a production document or example document is either an ordinary element or a sequence of contiguous elements, and

wherein each of said internal conditions belongs to a set consisting contains conditions, notcontains conditions, firstsubtree conditions and lastsubtree conditions;

wherein contains conditions impose one or more restrictions on some subelement of the pattern to be defined,

notcontains conditions require that instances of the pattern to be defined do not contain subelements satisfying specified restrictions,

firstsubtree conditions require that some element with specified properties be the first element of a sequence of elements to be defined; and

lastsubtree conditions requires that some element with specified properties be the last element of a sequence of elements to be defined.

49. The wrapper generation system of claim 48 where said restrictions are selected from a set consisting of restrictions on font type,

restrictions on font size,

restrictions on font color,

restrictions on the text contained in said subelement,

restrictions on hyperlinks and other anchors,

restrictions on explicit positional parameters,

restrictions on element types, and

restrictions on the value of a hidden attribute.

50. The wrapper generation system of claim 16 where said contextual conditions are selected from a group consisting of before conditions, after conditions, notbefore conditions, notafter conditions and vertical positional conditions,

wherein before conditions require that some element with specified properties must occur before a pattern instance,

after conditions require that some element with specified properties must occur after a pattern instance,

notbefore conditions require that some element with specified properties must not occur before a pattern instance,

notafter conditions require that some element with specified properties must not occur after a pattern instance;

and

vertical positional conditions require that a pattern instance must occur in some vertical position relative to a specified element, where said vertical position is in a set comprising;

below, above, not below, and not above.

51. The wrapper generation system of claim 1 wherein said example documents and said production documents are XML documents.

52. The wrapper generation system of claim 1 wherein said example documents and said production documents consist of unformatted text.

53. The wrapper generation system of claim 1 wherein said example documents and said production documents consist of text structured by structuring features from a set containing headlines, and titles, and spaces, and paragraphs, and indentations, and lists.

54. The wrapper generation system of claim 1 wherein said example documents and said production documents are formatted according to some document processing standard.

55. The wrapper generation system of claim 18 wherein said auxiliary conditions are selected from a group consisting of concept conditions, comparison conditions, pattern reference conditions, and conditions on documents,

where concept conditions require that some part of a pattern to be defined matches an ontological concept definition,

comparison conditions impose restrictions on the values of concept items,

pattern reference conditions require that a pattern to be defined, or some element used within a pattern definition, be an instance of a pattern defined within the same wrapper;

and

conditions on document filters express restrictions on further documents to be loaded.

56. A method for visual and interactive generation of a wrapper for documents and for automated information extraction comprising:

letting a user visually and interactively declare at least one desired property of elements to be extracted from the document thereby creating user declarations;

translating the user declarations into a wrapper;

executing a wrapper over the document; and

extracting elements from said documents that match said user declarations.

57. A method for visual and interactive generation of wrappers for documents, and for automated information extraction comprising:

defining extraction patterns on at least one example page, by visually and interactively selecting example-elements occurring on the example-page;

visually and interactively declaring properties of the extraction patterns;

generating a wrapper;

applying the wrapper to at least one production document; and

automatically extracting matching instances of the extraction patterns from the production documents.

58. The method of claim 57, wherein the example document is received in a browser window.

59. The method of claim 57, wherein a user controls wrapper generation, selects examples from the example document and adds further user specification.

60. The method of claim 59, wherein at least one pattern is generated from conditions that are obtained from the examples and the user specification.

61. The method of claim 57 wherein at least one extraction pattern is organized according to a logical combination of conditions.

62. The method of claim 57, wherein on applying to the document the wrapper produces a data structure representing all elements that match said pattern descriptions.

63. The method of claim 62 wherein the wrapper is applied to a plurality of production documents.

64. The method of claim 62, wherein the data structure produced by the application of the wrapper to the document is further translated to at least one output data structure.

65. The method of claim 61 wherein at least one of said conditions is a location condition that is obtained by generalizing a location descriptor of a selected example-element, and

66. The method of claim 61 wherein at least one of said conditions is a refinement condition that refines the set of instances of a pattern based on explicit user commands.

67. The method of claim 57 in wherein the processes of generation of a pattern further comprises:

a) receiving from a user a pattern name and storing said name;

b) creating and storing a filter for the pattern;

c) visualizing the set of instances of the filter on at least one example document by evaluating the filter over the document and visualizing all data elements of the document that are matching instances, whereby a user can test the filter;

d) modifying a previously created filter by adding to it refinement conditions that the instances of the filter must fulfill, where the refinement conditions are obtained from a user by receiving interactive commands from the user and where the refinement conditions are combined with those conditions for the filter that were added earlier;

e) visualizing simultaneously all instances of all filters of the given pattern on at least one document by evaluating its corresponding pattern description against the document, whereby a user can test the pattern description constructed so far.

68. The method of claim 67, wherein the creation and storing of a filter comprises:

b.1;

selecting an example-element occurring in at least one example document by receiving selection commands from a user acting on the example document while the example document is displayed in a browser, and creating a location descriptor for said example-element with respect to said example-document;

b.2;

generalizing said location descriptor by replacing it with a generalized location descriptor that matches at least said example-element, and storing said generalized location descriptor in form of a location condition that can be evaluated over data elements;

b.3;

representing and storing the association between said pattern name and said generalized location descriptor, which together constitute a filter for said pattern and where data elements matching said generalized location descriptor are called instances of said filter;

69. The method of claim 67, wherein the steps are executed one or more times and the order of execution and number of repetitions is determined by interactive user actions.

70. The method of claim 67 wherein one of said refinement conditions is an internal condition expressing properties which the instances of a pattern must fulfill regardless of their context.

71. The method of claim 67 wherein one of said refinement conditions is a contextual condition that expresses restrictions on the context in which instances of a pattern are allowed to appear, and

72. The method of claim 67 wherein one of said refinement conditions is a range condition that expresses that among the pattern instances which satisfy all other imposed conditions of a given filter, only those of each context are to be considered valid, which occur in that context within specified position ranges with respect to document order, and

73. The method of claim 67 wherein one of said refinement conditions is an auxiliary condition which further refine the set of instances.

74. The method of claim 57 wherein at least one of said example-documents is a Web page.

75. The method of claim 57 wherein at least one of said production documents is a Web page.

76. The method of claim 57 wherein at least on of said example documents is formatted in HTML and where each of said example-elements corresponds to a node or to a sequence of nodes of an HTML parsing-tree of the example-document in which said example-element occurs.

77. The method of claim 57 wherein at least on of said production documents is formatted in HTML and where at least one of said example-elements corresponds to a node or to a sequence of nodes of an HTML parsing-tree of the production document in which said example-element occurs.

78. The method of claim 57 wherein at least one of said example-documents is formatted in HTML and where at least one of said example-elements corresponds to an HTML element whose type is selected from a group consisting of:

html, table, tr, th, tfoot, thead, col, colgroup, caption, td, p, br, div, blockquote, body, head, h1, h2, h3, h4, h5, h6, dl, dd, dt, ol, ul, li, dir, menu, form, input, select, option, address, center, pre, xmp, nobr, wbr, hr, img, b, i, font-size, font-color, underline, blink, a (anchors), href, tt, big, sup, sub, cite, code, strong, em, samp, area, map, script, and CSS styles applied to the content and structure.

79. The method of claim 57 wherein at least one of said production documents are formatted in HTML and where at least one of said example-elements corresponds to an HTML element whose type is selected from a group consisting of:

html, table, tr, th, tfoot, thead, col, colgroup, caption, td, p, br, div, blockquote, body, head, h1, h2, h3, h4, h5, h6, dl, dd, dt, ol, ul, li, dir, menu, form, input, select, option, address, center, pre, xmp, nobr, wbr, hr, img b, i, font-size, font-color, underline, blink, a (anchors), href, tt, big, sup, sub, cite, code, strong, em, samp, area, map, script, and CSS styles applied to the content and structure.

80. The method of claim 69, wherein said generalized location descriptor is obtained from a corresponding location descriptor by syntactic generalization operations.

81. The method of claim 80, wherein said generalized location descriptor is obtained by inserting zero or more wildcards, by substituting wildcards for zero or more elements and by eliminating zero or more elements from said location descriptor.

82. The method of claim 69, wherein at least one example-document is tree-structured and wherein each location descriptor, called plain tree path, created for an example-element occurring in an example-document corresponds to the sequence of element-types on the path in the parsing tree of said example-document from the root to said example-element, and where the corresponding generalized location descriptor, called incompletely specified tree path, is obtained from said location descriptor by inserting zero or more wildcards, by substituting wildcards for zero or more elements and by eliminating zero or more elements from said location descriptor.

83. The method of claim 69, wherein at least one production-document is tree-structured and wherein each location descriptor, called plain tree path, created for an example-element occurring in an example-document corresponds to the sequence of element-types on the path in the parsing tree of said example-document from the root to said example-element, and where the corresponding generalized location descriptor, called incompletely specified tree path, is obtained from said location descriptor by inserting zero or more wildcards, by substituting wildcards for zero or more elements and by eliminating zero or more elements from said location descriptor.

84. The method of claim 69, wherein at least one production-document is in HTML format and wherein each location descriptor, called plain tree path, created for an example-element occurring in an example-document corresponds to the sequence of HTML tags on the path in the parsing tree of said example-document from the root to said example-element, and where the corresponding generalized location descriptor, called incompletely specified tree path, is obtained from said location descriptor by inserting zero or more wildcards, by substituting wildcards for zero or more HTML tags and by eliminating zero or more elements from said location descriptor.

85. The method of claim 82, wherein said generalized location descriptor is set to a default value that is obtained from said location descriptor by prefixing each element in the location descriptor with a wildcard.

86. The method of claim 82 wherein a wildcard prefixing an element occurring within a generalized location descriptor is interpreted as an arbitrary chain of elements whose type differs from a type corresponding to said element.

87. The method of claim 85 wherein a user is given a possibility to change and overwrite said default value.

88. The method of claim 57, wherein commands related to said visual and interactively selecting said example-elements are given by a user acting directly on said example-documents, said acting is performed by means of one or more of a set of graphical user interface actions, said set including mouse-clicking and region marking.

89. The method of claim 57, wherein commands related to said visual and interactive declarations are given by a user acting by means of one or more of a set of user interface actions, said set including mouse-clicking, region marking on said example-documents, button selection, and insertion of data into dialog boxes.

90. The method of claim 57, wherein each of said patterns is selected from a set consisting of tree patterns, string patterns and document patterns, wherein instances of said tree patterns are subtrees of document parse-trees, instances of said string patterns are substrings of text strings occurring on some documents and instances of said document patterns are documents.

91. The method of claim 67, wherein said visualization of said instances of a filter and said simultaneous visualization of all instances of a pattern on selected documents is done by means at least one visual highlighting method, said visualizing method selected from a group consisting font color change, background color change, font type change, font size change, blinking, and underlining.

92. The method of claim 57, wherein the pattern description generated for each of said patterns contains a Boolean combination of all conditions that contribute to the definition of said pattern.

93. The method of claim 57, wherein the pattern description generated for each of said patterns consists of a set of rules formulated in a logic programming language.

94. The method of claim 57, wherein the pattern description generated for each of said patterns consists of a set of rules formulated in a logic programming language and where said wrapper consists of a logic program containing said rules.

95. The method of claim 94 wherein the variables and terms of said logic program range over elements occurring in the documents to which said wrapper is applied.

96. The method of claim 94 wherein the variables and terms of said logic program range over elements and strings occurring in the documents to which said wrapper is applied.

97. The method of claim 94 wherein the variables and terms of said logic program range over elements, element-lists, and strings occurring in the documents to which said wrapper is applied.

98. The method of claim 94 wherein the variables and terms of said logic program range over elements, element-lists, strings and attribute values occurring in the documents to which said wrapper is applied.

99. The method of claim 94 wherein said documents are tree-structured and where the variables of said logic program range over nodes of the parsing trees of documents to which said wrapper is applied.

100. The method of claim 94 wherein said documents are tree-structured and where the variables of said logic program range over nodes of the parsing trees and over strings occurring in the documents to which said wrapper is applied.

101. The method of claim 94 wherein said documents are tree-structured and where the variables of said logic program range over nodes and sequences of nodes of the parsing trees of documents to which said wrapper is applied.

102. The method of claim 94 wherein said documents are tree-structured and where the variables of said logic program range over nodes of the parsing tree of documents to which said wrapper is applied, over sequences of such nodes, and over strings occurring in documents to which said wrapper is applied.

103. The method of claim 94 wherein each condition that contributes to the definition of a pattern is represented by at least one atom in the body of a rule of said logic program which contributes to the definition of said pattern.

104. The method of claim 67 wherein the representation of each of said filters is organized according to a logical conjunction of all conditions contributing to said filter, and where the representation of each of said patterns is organized according to the logical disjunction of all filters contributing to said pattern, whereby a pattern can be defined via successive narrowing and broadening steps corresponding to the addition of a new condition to a filter of said pattern, and to the addition of a new filter for said pattern, respectively.

105. The method of claim 104 wherein the representation of each of said filters is organized as an explicit Boolean conjunction of all conditions contributing to said filter, and where the representation of each of said patterns is organized as an explicit logical disjunction of all filters contributing to said pattern, whereby a pattern can be defined via successive narrowing and broadening steps corresponding to the addition of a new condition to a filter of said pattern, and to the addition of a new filter for said pattern, respectively.

106. The method of claim 67 wherein each of said filters is represented as a logic programming rule and wherein each pattern is represented by a set of rules representing filters defining said pattern, and wherein said wrapper is a logic program consisting of all rules representing said filters.

107. The method of claim 104 wherein each of said logic programming rules representing a filter consists of a rule body that represents all conditions contributing to said filter in form of a conjunction of atoms and of a rule head whose predicate corresponds to the pattern said filter is associated with.

108. The method of claim 107 wherein said logic program is a datalog program making use of special predefined predicates for expressing conditions.

109. The method of claim 70 wherein each of said internal conditions belongs to a set consisting of contains conditions and noncontains conditions

wherein the contains conditions impose one or more restrictions on some subelement of the pattern to be defined and

the notcontains conditions require that instances of the pattern to be defined do not contain any subelement that satisfies specified restrictions.

110. The method of claim 70 wherein an element of a document is either an ordinary element or a sequence of contiguous elements, and wherein each of said internal conditions belongs to a set consisting contains conditions, notcontains conditions, firstsubtree conditions and lastsubtree conditions;

wherein contains conditions impose one or more restrictions on some subelement of the pattern to be defined,

notcontains conditions require that instances of the pattern to be defined do not contain subelements satisfying specified restrictions,

firstsubtree conditions require that some element with specified properties be the first element of a sequence of elements to be defined; and

lastsubtree conditions requires that some element with specified properties be the last element of a sequence of elements to be defined.

111. The method of claim 110 where said restrictions are selected from a set consisting of

restrictions on font type,

restrictions on font size,

restrictions on font color,

restrictions on the text contained in said subelement,

restrictions on hyperlinks and other anchors,

restriction on explicit positional parameters,

restriction on element types, and

restrictions on the value of a hidden attribute.

112. The method of claim 111 where at least one of said restrictions specifies that the target object must contain some given substring.

113. The method of claim 111 where at least one of said restrictions specifies that the target object must coincide with some given value.

114. The method of claim 111 where at least one of said restrictions is specified in form of a regular expression.

115. The method of claim 111 where at least one of said restrictions is expressed in terms of a predefined ontological concept.

116. The method of claim 70 where said contextual conditions are selected from a group consisting of before conditions, after conditions, notbefore conditions, notafter conditions and vertical positional conditions,

wherein before conditions require that some element with specified properties must occur before a pattern instance,

after conditions require that some element with specified properties must occur after a pattern instance,

notbefore conditions require that some element with specified properties should not occur before a pattern instance,

notafter conditions require that some element with specified properties should not occur after a pattern instance;

and

vertical positional conditions require that a pattern instance must occur in some vertical position relative to a specified element, where said vertical position is in a set comprising;

below, above, not below, and not above.

117. The method of claim 57 wherein said example documents and said production documents are XML documents.

118. The method of claim 57 wherein said example documents and said production documents consist of unformatted text.

119. The method of claim 57 wherein said example documents and said production documents consist of text structured by structuring features from a set containing headlines, and titles, and spaces, and paragraphs, and indentations, and lists.

120. The method of claim 57 wherein said example documents and said production documents are formatted according to some document processing standard.

121. The method of claim 70 wherein said auxiliary conditions are selected from a group consisting of concept conditions, comparison conditions, pattern reference conditions, and conditions on documents,

where concept conditions require that some part of a pattern to be defined matches an ontological concept definition,

comparison conditions impose restrictions on the values of concept items,

pattern reference conditions require that a pattern to be defined, or some element used within a pattern definition, be an instance of a pattern defined within the same wrapper;

and

conditions on document filters express restrictions on further documents to be loaded.

122. A method for interpreting an extended logic program over Web pages, comprising:

setting variables and terms of said logic program so that they form a range over nodes parsing trees of said Web pages,

setting an identification of each Web page to an extensional database whose data elements are nodes of the parsing tree of said Web page; and

establishing parent-child relationship between the nodes of said parsing tree to be a binary relation, and whose data elements are ordered according to document order.

123. The method of claim 122, wherein said extended logic program contains special atoms corresponding to conditions from a plurality of conditions selected from a group consisting location conditions, internal conditions and contextual conditions,

wherein location conditions impose restrictions on the location of nodes of said parsing-tree

internal conditions impose restrictions on nodes of said parsing trees, relying on properties of the subtrees rooted in said nodes, and

contextual conditions, imposing restrictions on the context in which nodes may appear within said parsing tree;

wherein, in addition to classical inference procedures of logic programming, specific procedures are provided for evaluating said special atoms.

124. The method of claim 123, wherein, said extended logic program consists of a datalog program in which by said special atoms are treated as atoms of built-in predicates.

125. The method of claim 123, wherein range intervals can be specified with each rule of said extended logic program, and wherein only those facts are computed by a rule that match the ranges of said intervals in the ordering induced by document order.