
## 3.2.4 Lists

We have also applied the reinduction algorithm to extract data from pages containing lists of tuples, and, in many cases, have successfully extracted at least several examples of each field from several pages. However, in order to learn the correct extraction rules for sources returning lists of data, Stalker **requires that the first, last and at least two consecutive** list elements be correctly specified. The methods presented here cannot guarantee that the required list elements are extracted, unless all the list elements are extracted. We are currently working on new approaches to data extraction from **lists (Lerman, Knoblock, &** Minton, 2001) that will enable us to use Stalker **to learn the correct data extraction rules.**

## 4. Previous Work

There has been a significant amount of research activity in the **area of pattern learning. In**
the section below we discuss two approaches, grammar induction and relational learning, and compare their performance to DataProG **on tasks in the Web wrapper application**
domain. In Section 4.2 we review previous work on topics related to wrapper maintenance, and in Section 4.3 we discuss related work in information extraction and wrapper induction.

## 4.1 Pattern Learning 4.1.1 Grammar Induction

Several researchers have addressed the problem of learning **the structure, or patterns, describing text data. In particular, grammar induction algorithms have been used in the past** to learn the common structure of a set of strings. Carrasco and Oncina proposed ALERGIA (Carrasco & Oncina, 1994), a stochastic grammar induction algorithm that learns a regular language from positive examples of the language. ALERGIA starts with a finite state automaton (FSA) that is initialized to be a prefix tree that represents all the strings of the language. ALERGIA uses a state-merging approach (Angluin, 1982; Stolcke & Omohundro, 1994) in which the FSA is generalized by merging pairs of statistically similar (at some significance level) subtrees. Similarity is based purely on the relative frequencies of substrings encoded in the subtrees. The end result is a minimum FSA that is consistent with the grammar.

Goan et al. (Goan et al., 1996) found that when applied to data **domains commonly**
found on the Web, such as addresses, phone numbers, *etc.***, ALERGIA tended to merge**
too many states, resulting in an over-general grammar. They proposed modifications to ALERGIA, resulting in algorithm WIL, aimed at reducing the number of faulty merges. The modifications were motivated by the observation that each symbol in a string belong to one of the following syntactic categories: NUMBER, LOWER, UPPER and DELIM**. When**
viewed on the syntactic level, data strings contain additional structural information that can be effectively exploited to reduce the number of faulty merges. WIL merges two subtrees if they are similar (in the ALERGIA sense) and also if, at every level, they contain nodes that are of the same syntactic type. WIL also adds a wildcard generalization step in which the transitions corresponding to symbols of the same category that are approximately evenly distributed over the range of that syntactic type (*e.g.***, 0–9 for numerals) are replaced with** a single transition corresponding to the type (*e.g.*, NUMBER**). Goan** *et al.* **demonstrated**