The tree is empty initially, and children are added to the root node. The children represent all tokens that occur in the first position in the training examples more often than expected by chance. For example, when learning addresses from the examples in Fig. 2, the root will have two child nodes: Alphanum and Number**. The tree is extended** incrementally at each node Q. A new child is added to Q **for every significant specialization**
of the pattern ending at Q**. As explained previously, a child node is judged to be significant** with respect to its parent node if the number of occurrences of the pattern ending at the child node is sufficiently large, given the number of occurrences of the pattern ending at the parent node and the baseline probability of the token type used to extend the pattern. To illustrate on our addresses example, suppose we have already found that a pattern <Number Upper> is significant. There are five ways to extend the tree (see Fig. 4) **given the data:** <Number Upper Alphanum>, <Number Upper Alpha>, <Number Upper Upper>,
<Number Upper **Street**>, <Number Upper Boulevard>**, and** <Number Upper Way>.

All but the last of these patterns are judged to be significant at α = 0.**05. For example,** <Number Upper Upper> **is significant, because** Upper **follows the pattern** <Number Upper> five out of five times,1 **and the probability of observing at least that many longer**
sequences purely by chance is 0.0002.2 Since this probability is less than α**, we judge this**
sequence to be significant.

![0_image_0.png](0_image_0.png)

The next step is to prune the tree. The algorithm examines each pair of sibling nodes, one of which is more general than the other, and eliminates the less significant of the pair. More precisely, the algorithm iterates through the newly created children of Q**, from the**
most to least general, and for every pair of children Ci and Cj , such that Ci**.pattern** ⊂
Cj **.pattern** (*i.e.*, Cj .pattern is strictly more general than Ci.pattern**), the algorithm keeps**
only Cj **if it explains significantly more data; otherwise, it keeps only** Ci.

3