We present new techniques for supervised wrapper generation and automated web information extraction, and a system called Lixto implementing these techniques [6]. Our system can generate wrappers which translate relevant pieces of HTML pages into XML. Lixto, of which a working prototype has been implemented, assists the user to semi-automatically create wrapper programs by providing a fully visual and interactive user interface. In this convenient user-interface very expressive extraction programs can be created. Internally, this functionality is re ected by the new logic-based declarative language Elog. Users never have to deal with Elog and even familiarity with HTML is not required. Lixto can be used to create an \XML-Companion" for an HTML web page with changing content, containing the continually updated XML translation of the relevant information.
Nowadays web content is mainly formatted in HTML.
This is not expected to change soon, even if more exible
languages such as XML are attracting a lot of attention.
While both HTML and XML are languages for
representing semistructured data, the rst is mainly
presentationoriented and is not really suited for database applications.
XML, on the other hand, separates data structure from
layout and provides a much more suitable data representation
(cf. e.g. [
Imagine you would like to monitor interesting eBay o ers (www.ebay.com) of notebooks, where an interesting o er is, for example, de ned by an auction item which contains the word \notebook", has current value between gbp 1500 and 3000 and which has received at least three bids so far. The eBay site does not o er the possibility to formulate such complex queries. Similar sites do not even give restricted
All new methods and algorithms presented in this paper are covered by a pending patent. Future developments of Lixto will be reported at www.lixto.com. This paper also appeared in the proceedings of VLDB 2001. user
Interactive Pattern Builder work on XML query possibilities and leave you with a large number of result records organised in a huge table split over many web pages. You have to wade through all these records manually, because of no possibility to further restrict the result. Another drawback is that you cannot directly collect information of di erent auction sites (e.g. onetwosold and ebay items together) into a single structured le, a di cult task of web information integration due to very di erent presentation on each site.
The solution is thus to use wrapper technology to extract the relevant information from HTML documents and translate it into XML which can be easily queried or further processed. Based on a new method of identifying and extracting relevant parts of HTML documents and translating them to XML format, we designed and implemented the e cient wrapper generation tool Lixto, which is particularly wellsuited for building HTML/XML wrappers and introduces new ideas and programming language concepts for wrapper generation. Once a wrapper is built, it can be applied automatically to continually extract relevant information from a permanently changing web page.
The Lixto method and system ful lls the requirements
speci ed in a very recent paper on e-commerce tools [
XML Generator / Simple Query
System Transformer
XML cause a fully visual and interactive user interface is provided. Neither manual ne-tuning nor knowledge of the internal language is necessary. Lixto uses straightforward region marking and selection procedures that allow even those users not familiar with HTML to work with the wrapper generator. Lixto lets a wrapper designer work directly and solely on browser-displayed example pages, unlike other tools (see Section 6), that force the designer to work with other document views such as, e.g., table-views of the document or displayed HTML parse trees, or even HTML sources. After selecting example targets in the browser display, Lixto responds with highlighted targets in the same display (see Section 3). With Lixto, very expressive visual wrapper generation is possible: It allows for extraction of target patterns based on surrounding landmarks, on the contents itself, on HTML attributes, on the order of appearance and on semantic and syntactic concepts. Extraction is not limited to tokens of some document object model, but also possible from at strings. Multiple and single targets are treated in a uniform way. Lixto even allows for more advanced features such as disjunctive pattern de nitions, crawling to other pages during extraction, recursive wrapping. Moreover, the extracted data structures do not have to strictly obey the input HTML structure. Preliminary results on representative web pages with using the current Lixto prototype show a good performance (see Section 5).
The above mentioned features are internally re ected by a declarative extraction language called Elog (see Section 4), which uses a datalog-like logical syntax and semantics. Elog is invisible to the user. It is ideally suited for representing and successively incrementing the knowledge about patterns described by users. This knowledge is generated in an interactive process consisting of successive narrowing (logical and ) and broadening (logical or ) steps. An Elog program is a collection of datalog-like rules containing special extraction conditions in their bodies. Elog is exible, intuitive and easily extensible.
This paper is structured as follows. In the next section the system architecture is described, in Section 3 we give an overview of the the interactive pattern generation and visual UI, whereas Section 4 is devoted to the theory of the Elog extraction language. Section 5 presents empirical results of using the Lixto wrapper generator, Section 6 discusses related approaches and Section 7 highlights future research directions.
A working prototype of Lixto already has been
implemented with Java using Swing, OroMatcher [
The Interactive Pattern Builder provides the visual UI that allows a user to specify the desired extraction patterns and the basic algorithm for creating a corresponding Elog wrapper as output.
The Extractor is the Elog program interpreter that performs the actual extraction based on a given Elog program. The extractor, provided with an HTML document and a previously constructed program, generates as its output a pattern instance base, a data structure encoding the extracted instances as hierarchically ordered trees and strings. One program as input of the extractor can be used for continual extraction on changing pages, or to extract from several current example source selected after element current example target HTML pages of similar structure.
With the controller of the XML Generator, the user chooses how to map extracted information to XML. Its transformer module performs the actual translation from the extracted pattern instance base to XML. 3. 3.1
A Lixto wrapper is created interactively by creating patterns in a hierarchical order. For example, one can rst dene a pattern <item> and then de ne a subpattern <price>. The subpattern relationship in this case expresses that each extracted instance of <price> must occur within one instance of <item>. Pattern names act as default XML element names. Each pattern characterises one kind of information. The set of extracted instances of a pattern, which are either HTML elements, list of elements, or strings, depends on the current page. Each pattern is de ned by one or more lters. A lter e.g. allows the system to identify a set of similar nodes of the HTML parse tree, for instance a set of items internally represented as <td>.
A lter is created as follows: First, the user highlights with the mouse a representative instance of the desired target pattern directly on the example page. Internally, the system associates to this instance a generalised tree path in the HTML parse tree identifying similar instances and incorporates this as main goal of a Elog rule representing the lter (see Section 4). Second, the user adds restrictive conditions to the lter. These are re ected by the system as additional goals in the rule body describing this lter. The possible conditions, which will be explained in more detail, include: (a) before/after conditions that express that the target pattern instance must appear before or after some speci c element. (b) notbefore/notafter conditions that express that some speci c element must not be close to the target pattern. (c) internal conditions that express that some speci c element must (not) appear inside the target pattern. (d) range conditions which, in case of multiple matchings, restrict the set of matched instances to a subinterval.
Adding a lter to a pattern extends the set of extracted
targets, whereas imposing a condition to a lter restricts the
set of targets. Alternately imposing conditions and adding
new lters can perfectly characterise the desired
information. The system creates Elog rules based on user-de ned
lters. The user is never concerned with the internal
language Elog. The user interface is extremely simple and the
entire wrapper construction process can be learned by an
average user in very short time. The user is guided through
pattern ∨
a supervised pattern generation, and by simply marking
relevant information items on-screen and visually setting
constraints, lters and patterns are created. In [
The generation of a pattern is described in Fig. 3. The user can hierarchically de ne and re ne patterns. She enters a pattern name, speci es the parent pattern S, selects by mouse clicks one example instance s of the parent pattern and marks (with the mouse) an element (e.g. one price) inside this instance on the sample page.
At the beginning, i.e. when facing a new HTML document (which is loaded into an internal browser; see Fig. 2) and having created a new program, the only pattern is <document> with a unique instance, the current example document. Fig. 3 distinguishes interactive (I) and automatic (A) steps and gives the logical pattern structure in its topleft corner. A pattern may consist of multiple lters. Each lter contains a number of conditions. An extracted instance must satisfy all conditions of at least one lter. Two consecutive mouse clicks on di erent parts of the current parent instance are interpreted in the best possible way to mark an HTML element of the document parse tree (cf. Fig. 7) or if not possible a list of elements.
The system generates a basic lter without conditions, but the user can already state some attribute requirements (the system constructs a suitable element path de nition, see Section 4). Then it highlights all objects on the current example page that match these initial lter criteria (not only in the current pattern instance, but in all pattern instances). Sometimes a user wants a single match within one source, sometimes multiple matches { this makes no di erence in the algorithm { it just depends on the de nition of lters and conditions. E.g., if the user marks a table row, the system recognises the entity <tr> and highlights all table rows occurring at a comparable level in the document. At the same time the system constructs a general Elog rule for extracting table rows.
If the user is satis ed with the elements identi ed by the system, she can con rm the pattern de nition. Satisfaction, in this context, means that only desired targets are matched. Otherwise, if the concept is too general, then she can add restricting conditions (which are re ected by Elog condition predicates); cf. Fig. 4. For each such restriction, the system adds the corresponding condition atom to the C o n d i t i o n B u i l d e r adds one condition to a filter Select a range by indicating the first and last relevant target instance to be extracted (I)
Characterise element that is not allowed to appear before/ after target. (I/A) range notbf notaf
Select an element Select type(Io)f condition. abfetfeorre bpineasfrotearnent/caienftseatrnatdnhceweei;txhuaisnmetrphliees guided by wizards. (I)
Set the distance tolerance in percent to left/right. (I) internal
Select an element inside the instance and within the parent instance; user is guided by wizards. (I)
Choose attributes of selected element
to be considered (e.g. content, font-type
etc.). A wizard automatically proposes
particularly relevant attributes. (I/A).
Elog rule de ning the lter at hand. Each lter is intended
to extract a subset of the desired target set. If the current
pattern is less general than intended by the user, another
lter can be added, internally re ected by an additional Elog
rule for the same pattern (several rules for the same pattern
are interpreted disjunctively, as usual in Datalog). Di erent
lters may be created based on labelling in di erent
example parent pattern instances. By iterating restricting and
generalising steps, it is usually possible to describe a desired
pattern perfectly. Once a pattern is de ned, the user may
use this pattern as parent for a new pattern. A detailed
creation of a simple example wrapper is given in [
The current implementation includes visual tree pattern construction and the use of string patterns. All lter conditions discussed in this paper are supported. Moreover, the visual interface is assisted by an XML visualisation tool which at each instant shows the user the so far extracted XML code. A concept atom generator to create prede ned concepts (such as \isCity", \isDate") based both on regular expressions and on reading some database tables is currently being added. Such concepts are especially useful to allow users to create string patterns without knowledge of regular expressions. Fig. 5 shows the main menu of Lixto (left-hand side). There, a new program can be created or an existing one loaded, new patterns can be added, the document for labelling can be chosen, etc. The same gure shows on its right hand side the source selection dialogue which enables the user to select at which node to create a new pattern. Fig. 2 shows the internal Lixto browser when selecting an after element. For each condition, an own interface is provided which uses the user-labelled information.
The output by the extractor is well-suited for translation into XML. The interactive XML generator exploits the hierarchical structure of the pattern instance base and uses pattern names as default XML element names. The user can interactively choose the HTML attributes that appear in the XML output. Even more important is the possibility to decide which patterns are written to XML, possibly using auxiliary patterns. Fig. 9 displays the result of applying a (not illustrated) wrapper program onto the web page of Fig. 6. currently constructed pattern pattern and filter deletion option menu current status current program name or “new program” if program current document which is is not yet saved (hidden) used for program creation
Select parent pattern open an url used for creating create a new pattern (naming; patterns enables adding of filters) test and save the current patterns (all its filters)
hierarchy of patterns
pattern instead A leaf node of the pattern tree navigate through pattern instances to select example parent instance
Elog is the system-internal datalog-like rule based language speci cally designed for hierarchical and modular data extraction. A user of Lixto does not have to learn Elog and never sees the Elog program. Elog rules are the implementations of the visually de ned lters and de ne elements to be extracted from web pages. Before we discuss the features of the language in detail, have a look at Fig. 8, in particular at the rule with head predicate record(S; X). Observe that we use as in Prolog the same variables for each rule, and denote with \ " a variable in whose instantiations we are not interested. This predicate identi es records on an eBay page (each one is an own table). The rst atom in the rule body speci es that the context S of the extraction, i.e. the so-called parent pattern, is an instance of <tableseq>. The second atom in the rule body looks for subelements that qualify as tables inside the unique <tableseq> instance and instantiates X with them. Given that the same Elog program can be applied to di erent web pages, the actual elements that an Elog program de nes and extracts depend on the current web page. For this reason, we refer to the head predicates de ned by an Elog program as patterns. Moreover, we denote a set of rules with the same head as pattern, too. The syntax and semantics of Elog and its predicates is explained below (only informally due to space constraints). 4.2
Consider the example web page lixto.html of Fig. 6 and its parse tree as displayed in Fig. 7 based on the Java Swing parser. The values in brackets are the start and end-o sets (in characters) of the corresponding elements in the actual document. Additionally, we number nodes in a depth- rst left-to-right fashion. Nodes of the HTML tree refer to elements which are represented as sets. The set contains pairs describing the association between attribute names and corresponding attribute values. E.g., the <body> element node of Fig. 7 is associated with f(name,body), (bgcolor,FFFFFF), (elementtext,Items for : : : : : : 137)g (whole document text). Fig. 7 highlights two other such attribute http://www.dbai.tuwien.ac.at/lixto.html sets.
Observe that in our chosen document object model, several leaf elements are <content> elements { this parser treats tags such as <b> (bold-face) as attributes of an imaginary <content> element. We introduced a special attribute called \elementtext" for each element. This attribute re ects the contents of the element, which is in case of an internal node the left-to-right concatenation of the leaf elements below the internal node. In the following, we distinguish tree regions and subtrees of the HTML tree. A tree region is a region rooted at an internal node of the HTML tree where only the i-th up to the j-th child and their descendants are considered. Observe that a tree region is contiguous. A subtree is the tree rooted at one node of the HTML tree, i.e. all descendants are considered. 4.3
Lixto o ers two basic mechanisms of data extraction { tree and string extraction. For tree extraction, we identify elements with their corresponding tree paths and possibly some properties of the elements themselves. This does not necessarily identify a single element. As an example, ?:table: ? :tr is a valid tree path. In the sample page page of Fig. 6, three elements are matched. The star acts as wildcard. The expression : ? :x matches all paths to x which contain x as last element only. A plain tree path is a sequence of consecutive nodes in a subtree of an HTML tree. In an incompletely speci ed tree path stars may be used instead of element names. For simplicity, incompletely speci ed tree 2 h4 5 p-implied 3 content 4 content 6 hr
content (name, content) (a, href = "mailto:steven@...") (href, "mailto:steven@...") (elementtext, Steven) (257,263) content
content tr body (6,277)
(75,276) (name, table) (border,1) (elementtext,56 K Modem....)
(width,75%) center (23,276) p td td paths are referred to as tree paths. The semantics of a tree path applied to a tree region of an HTML page is de ned as the set of matched elements.
Attribute Conditions are constraints reducing the number of matched elements. They pose requirements on occurring attributes and their values. An attribute condition is a triple specifying a required name, a required value (a string, or in case the third parameter is regvar, a regular expression possibly containing some variables indicated by nvar), and a special parameter exact, substr or regvar, indicating that the attribute value is exactly the required string, is a superstring of it, or matches the given regular expression, respectively. Instead of giving a formal de nition, we illustrate this with an example: (?:hr; [(size; [3 4] ; regvar ); (width; %; substr )]) identi es horizontal rules of size 3 or 4 with a width speci ed in percent. Each output variable, which is included in the second parameter must be used as input for a concept of the same rule (cf. Section 4.4).
An element path de nition epd consists of a tree path and a set of attribute conditions. It is called simple if it consists of one element name only. The semantics of applying an element path de nition to a tree region of an HTML tree is given as the set of matched elements of the corresponding tree path which moreover satisfy all of the attribute conditions. Instead of element path de nitions, equivalently, XPath expressions can be used (with some extensions, such as the possibility to express that an attribute value is a concept). To simplify presentation, however, we stick to our introduced notation.
The second extraction method relies on strings. In the
HTML parse tree, strings are represented by the text of
content leaves. However, we associate a string to every node
of the parse tree available as the value of the attribute
elementtext. For instance when extracting access codes of the
phone-numbers of lixto.html, string extraction has to be
used. A substring of the elementtext of an HTML tree is
denoted as string source. One can express that a string source
must match a given regular expression. A string path de
nition spd is a regular expression possibly containing some
variables (variable Y indicated by nvar[Y ]) which appear in
some concept predicate of the corresponding rule. Regular
expressions are powerful tools for text processing and
matching. Refer to [
Elog atoms correspond to special predicates with a wellde ned semantics. They operate on source objects (tree regions and string sources), path de nition objects and numerical arguments and obey binding conventions. In a dataloglike language, the function mapping a given source S to a set of elements matching an epd is treated as relation subelem(S; epd; X). subelem(s; epd; x) evaluates to true i s is a tree region, epd is an element path de nition and x is a tree region contained in s where the root of x matches epd. Note that the tree path speci ed in a tree extraction de nition predicate is always relative to the parent-pattern instance.
Extraction de nition predicates specify a set of extraction instances. One of these is subelem. As far as string extraction is concerned, the predicate subtext(S; spd; X) is used. There, S is either a tree region or a string source, and X a string source. Two more extraction de nition predicates are built-in. (1) subsq(S; epd; fpd ; lpd ; X): If s and x are tree regions, epd is an element path de nition, and fpd and lpd are simple element path de nitions, subsq(s; epd; fpd ; lpd ; x) evaluates to true i the root of x satis es epd, its rst child satis es fpd and its last one lpd . (2) subatt(S; apd; X): If s is a tree region, x a string source and att is an attribute path de nition of the root element of s, then subatt(s; apd; x) evaluates to true i x is the value of apd. subatt gives the possibility to extract the values of attributes.
Context condition predicates specify that some other subtree or text must (not) appear before or after the desired extraction target. For example, on a page with several tables, the nal table could be identi ed by an external condition stating that no table appears after the desired table.
Before predicates are explained here, after predicates work analogously. (1) before(S; X; epd; b; e; Y; P ): If s and x are tree regions, then before(s; x; epd; b; e; y; p) evaluates to true i y is a subtree whose root node is matched by epd and the end o set of y precedes the start o set of x within relative distance p where b p e. (2) notbefore(S; X; epd; d): If s and x are tree regions, then notbefore(s; x; epd; d) evaluates to true i no element satisfying epd precedes x within relative distance d. The same predicates are de ned for string extraction: There, S is an arbitrary source, X is required to be a string source, spd is used instead of epd and instead of the root node simply the string itself is used. The percentual distance values b and e de ne the tolerance interval where the element is allowed to occur inside the current parentpattern instance. Additionally, a condition predicate may contain new variables Y and P , which can be referred by other conditions. To express that an element occurs anywhere within the parent instance and before the target (or a condition output), the distance values are set to 0 and 100, respectively.
Internal conditions predicates impose conditions on the internal structure. Imagine, for instance, one wants to extract all tables containing somewhere a word typeset in tablesq(S; X) record(S; X) itemnum(S; X) itemdes(S; X) price(S; X) bids(S; X) currency(S; X) pricewc(S; X) document(\www:ebay:com="; S); subsq(S; (:body; []); (:table; []); (:table; []); X); before(S; X; (:table; [(elementtext; item; substr]); 0; 0; ; ); after(S; X; :hr; 0; 0; ; ) tableseq( ; S); subelem(S; :table; X) record( ; S); subelem(S; ?:td; X); notbefore(S; X; :td; 100) record( ; S); subelem(S; (?:td: ? :content; [(a; ; substr)]; X) record( ; S); subelem(S; (?:td; [(elementtext; nvar[Y]: ; regvar)]); X); isCurrency(Y) record( ; S); subelem(S; ?:td; X); before(S; X; :td; 0; 30; Y; ); price( ; Y) price( ; S); subtext(S; nvar[Y]; X); isCurrency(Y) price( ; S); subtext(S; [0 9]+n:[0 9]+; X) italics. This can be obtained by adding a contains condition. contains(X; epd; Y ): contains(x; epd; y) evaluates to true i x is a tree region (string source) containing a subtree (string source) y where the root element of y matches epd (where y matches spd). The rstsubtree condition is a kind of \startswith" condition that states that the rst subtree of a tree region should contain a particular element.
rstsubtree(X; Y ): rstsubtree(x; y) evaluates to true i y is the subtree rooted at the rst child of the tree region x. lastsubtree is de ned analogously.
Concept condition predicates are semantic concepts like isCountry(X) or isCurrency(X) (see Fig. 8) or syntactic ones like isDate(X) (or isDate(X; Y ) where the output Y returns a standard date format), stating that a string X represents a date, a country, or a currency, respectively.
Some predicates are built-in to enrich the system, however
more concepts can be interactively added with assistance
of the Lixto concept editors. Syntactic predicates are
created as regular expressions, whereas semantic ones refer to
a database of ontologies (e.g. using ThoughtTreasure [
Pattern predicates indicate that a source belongs to a particular pattern and refers to a particular parent patterninstance. They are used in the head, and in the rule body for referring to a parent pattern and for further pattern references. As an example, the <price> pattern can be constructed by using the element path de nition : ? :td, and imposing the constraint that immediately before, a target of pattern <item> needs to occur:
before(S; X; : ? :td; 0; 1; Y; ); item( ; Y ):
Range conditions restrict the matched targets
depending on their order of appearance. To any rule, a range
condition such as \[
A standard extraction rule looks as follows: N ew(S; X) P ar( ; S); Ex(S; X); Co(S; X; : : : )[a; b], where S is the parent instance variable, X is the pattern instance variable, Ex (S; X) is an extraction de nition atom, and the optional Co(S; X) are further imposed conditions. A tree (string) extraction rule uses a tree (string) extraction de nition atom and possibly some tree (string) conditions and general conditions. The numbers a and b are optional and serve as range parameters. New and Par are pattern predicates referring to the parent pattern and de ning the new pattern, respectively. The above standard rule re ects the principle of aggregation. In an extended environment, we moreover allow specialisation rules such as: greentable(S; X) table(S; X); contains(X; (:td; [color; green; exact]); ). Additionally, an extended environment contains document lters, using a getDocument(S,X) atom, where S is a string source representing an URL, and X the web page the URL points to. With such lters, one can crawl to further documents. If document lters are used, each program has an initial lter using the getDocument atom with user-speci ed input.
The semantics of a rule is given as the set of matched targets x: A substitution s, x for S and X evaluates New (s; x) to true if all atoms of the body are true for this substitution. Only those targets are extracted for which the head of the rule resolves to true. Moreover, if the extraction definition predicate is a subsequence predicate, only minimal rule outputs are matched (i.e. instances that do not contain any other instances). Observe that range criteria are applied after non-minimal targets have been sorted out.
A pattern is a set of extraction rules de ning the same head and referring to the same parent pattern. In the visual pattern generation the user rst enters a pattern name and to which parent pattern the pattern belongs. All rules created inside the pattern use this information. We distinguish tree and string patterns. To the rst, only tree extraction rules can be asserted, to the second one only string extraction rules. The root pattern <document> is a special pattern without lters. If using document lters to crawl to further web pages, document patterns are used as third pattern type (and an initial document lter is used). Parents of tree patterns are either tree or document patterns, parent of string patterns are tree or string patterns, and parent of document patterns are string patterns. A pattern acts like a disjunction of rule bodies: To be an extracted instance of a pattern, a target needs to be in the solution set of at least one rule. The pattern output additionally obeys a minimality criterion. In patterns, even in those consisting of a single rule, overlapping targets may occur.
An extraction program P is a set of patterns. Elog program evaluation di ers from Datalog evaluation in the following three aspects: built-in predicates, various kinds of minimisation, and use of range conditions. Moreover, the atoms are not evaluated over an extensional database of facts representing a web page, but directly over the parse tree of the web page. Applying a program to an HTML <?xml version="1.0" encoding="UTF-8"?> <document> <heading>Items for Sale</heading> <description>3 items found for "Notebooks".
Showing Item 1 to 3.</description> <entry> <article>56 K Modem PCMCIA Card for
Notebooks</article> <price>$ 20</price> <person href="mailto:itsme@bestseller.org">
Angie</person> <phone>(01)-314 159</phone> <picture/> </entry> [...] page creates a set of hierarchically ordered tree regions and string sources (called a pattern instance base) by applying all patterns of the program in their hierarchical order to this HTML document (and possibly to further HTML documents if document lters are used). Each pattern produces a set of instances. Each pattern instance contains a reference to its parent instance. As patterns are ordered in a strictly hierarchical way, the program is hierarchically strati ed. In the nal section we will relax the de nition of patterns to create recursive programs.
As example program consider a wrapper for eBay pages (Fig. 8). On eBay pages, every o ered item is stored in its own table extracted by <record>; further patterns are all de ned within such a record. The pattern <price> uses a concept attribute, namely isCurrency { which matches strings like $, DM, Euro, etc. The <bids> pattern uses a reference to the <price> pattern. The nal two patterns are string patterns.
We chose twelve example sites (Table 1), some of which were already used for testing purposes by other wrapper generators. Several users of whom not all are familiar with details of HTML contributed to our test results. Initially, we asked them to create a wrapper based on a single example page. Table 2 summarises answers to the following questions: (1) Is it possible to wrap this page with Lixto? (2) How \complex" is the constructed program for this site? (ratio of required predicates to used output patterns) (3) What is the percentage of correctly wrapped pattern instances of a number of randomly chosen similarly structured testpages with a wrapper written on one example page only. (4) How many example pages are necessary (due to structural deviations) to get 100 percent of correctly matched pattern instances? (5) Moreover, we specify the time needed for constructing the initial wrapper based on one example page. Additionally, the time for constructing one output pattern is computed to gain a measure how much \thinking time" was required for each output pattern. (6) In the last row the depth of the pattern tree is speci ed.
Let us describe some more details: On eBay, the initial wrapper worked well on almost all test pages like queries on cars, football, etc. However, one lter rule of <date> required that dates must contain a colon and a dash. This matched one item description, too, which used both. Hence, the pattern had to be re ned based upon the knowledge of this second page to match 100% of the patterns of all example pages. For the CIA Factbook, the user chose a bad example page with only one bordering country. Even after improving the wrapper to deal with comma-separated countries, Albania had to be treated in a special way. The wrapper for DBLP relies on a number of intermediate auxiliary patterns, indicated by the high nesting depth of the document. For the CNN pages of the US election results per state, a wrapper just extracting names of president candidates and the received votes was written in a few minutes; due to a very homogeneous structure, one example page was su cient to extract these data for all states. The Jobs Jobs Jobs site is the only example where the number of needed sample pages depends on the number of testpages due to a wide variety of structures for job o ers. For the Perl Module List we are merely interested in writing a wrapper for a single web page. This list uses mainly preformatted text, hence the program heavily relies on string extraction. In the current implementation some auxiliary patterns are needed, and some clever constructions to obtain a 100% match for the ve chosen patterns (module group, leaf patterns name, DSLI, description, info). We conclude that almost all web pages can be visually wrapped with Lixto. Observe, that although we chose a rather structured le for illustrating Lixto throughout the paper, our approach also works on pages with less structure such as e.g. the CIA Factbook. For none of the test pages the user had to modify the Elog program manually. Wrapper construction is usually very fast. The program length measured in used predicates is never unreasonably large compared to the output patterns (ranging from 1.78 to 4.4). The user never had to consider more than three example pages to get a 100% match for all testpages. 6.
First, we give an overview of approaches less related to
Lixto because they do not provide visual support.
Standalone wrapper programming languages include Florid [
Machine learning approaches rely on learning from
examples and counterexamples of a large number of web pages.
Stalker [
Supervised interactive wrapper generation tools include
W4F [
It is currently already possible to write and execute Elog
programs that can crawl to other pages, i.e. follow links
during extraction, and can recursively wrap linked sequences of
web pages. For such applications, the pattern structure does
no longer form a tree because lters of one pattern de nition
may refer to di erent parent patterns (in a similar fashion
as recursive data types). For example, recursive Elog
programs may follow a \next" button and navigate to further
pages during extracting, while extracting instances of the
same patterns. See Fig. 10 for extending the eBay
example of Fig. 8 to follow a \next" button, and extract for
each page the same kind of information. In this example,
the pattern <document> has an initial lter which uses the
user-provided page ($1), and an additional lter, which uses
<nexturl> as parent pattern (whose instances are strings
representing URLs). Web crawling and recursion in Lixto
is described in more detail in [
Furthermore, a server-based Lixto version is currently being implemented { it uses simple web interfaces and works in the user's favourite browser. Future work focuses on automation heuristics for optional use, including to work on multiple example targets at once. Additionally, Lixto wrappers will be embedded into a personalisable information channel system. document( ; S); subelem(S; (?:content; [(a; ; substr); (elementtext; Next; exact)]); X) next( ; S); subatt(S; href; X) getDocument($1; X) nexturl( ; S); getDocument(S; X)