Let us illustrate the pruning step with the example pattern tree in Fig. 4. We can eliminate the node AlphaNum**, because all the examples that match the pattern** <Number Upper Alphanum> **also match the pattern** <Number Upper Alpha> **— thus,** Alphanum is not significant given its specialization Alpha**. We can eliminate node** Alpha **for a similar** reason. Next, we check whether <Number Upper Upper> **is significant given the patterns**
<Number Upper Boulevard> and <Number Upper Street>**. There are 2 instances of the** address field that match the pattern <Number Upper Boulevard>**, and 2 addresses that** match <Number Upper Street>**. If** <Number Upper Upper> **matches significantly more** than 4 addresses, it will be retained and the more specific patterns will be pruned from the tree; otherwise, it will be deleted and the more specific ones kept. Because every example is described by at most one pattern of a given length, the pruning step ensures that the size of the tree remains polynomial in the number of tokens, thereby, guaranteeing a reasonable performance of the algorithm.

Once the entire tree has been expanded, the final step is to extract all significant patterns from the tree. Here, the algorithm judges whether the shorter (more general) pattern, *e.g.*, <Number Upper>**, is significant given the longer specializations of it,** *e.g.*, <Number Upper Boulevard> and <Number Upper Street>**. This amounts to testing whether the**
excess number of examples that are explained by the shorter pattern, and not by the longer patterns, is significant. Any pattern that ends at a terminal node of the tree is significant. Note that the set of significant patterns may not cover all the examples in the data set, just a fraction of them that occur more frequently than expected by chance (at some significance level). Tables 2–4 show examples of several data fields from a yellow pages source (**Bigbook**)
and a stock quote source (Y ahoo Quote**), as well as the starting patterns learned for each** field.

## 3. Applications Of Pattern Learning

As we explained in the introduction, wrapper induction systems use information from the layout of Web pages to create data extraction rules and are therefore vulnerable to changes in the layout, which occur frequently when the site is redesigned. In some cases the wrapper continues to extract, but the data is no longer correct. The output of the wrapper may also change because the format of the source data itself has changed: *e.g.***, when "$" is dropped** from the price field ("9.95" instead of "$9.95"), or book availability changes from "Ships immediately" to "In Stock: ships immediately." Because other applications, such as Web agents (Ambite et al., 2002; Chalupsky et al., 2001), rely on **data extracted by wrappers,**
wrapper maintenance is an important research problem. We divide the wrapper maintenance problem into two parts, each described separately in the paper. *Wrapper verification* automatically detects when a wrapper is not extracting data **correctly from a Web source,** while *wrapper reinduction* **automatically fixes broken wrappers. Both applications learn a**
description of data, of which patterns learned by DataProG **are a significant part.**