Trinity: On Using Trinary Trees for Unsupervised Web Data Extraction

Trinity: On Using Trinary Trees for Unsupervised Web Data Extraction Hassan A. Sleiman and Rafael Corchuelo Abstract—Web data extractors are used to extract data from web documents in order to feed automated processes. In this article, we propose a technique that works on two or more web documents generated by the same server-side template and learns a regular expression that models it and can later be used to extract data from similar documents. The technique builds on the hypothesis that the template introduces some shared patterns that do not provide any relevant data and can thus be ignored. We have evaluated and compared our technique to others in the literature on a large collection of web documents; our results demonstrate that our proposal performs better than the others and that input errors do not have a negative impact on its effectiveness; furthermore, its efficiency can be easily boosted by means of a couple of parameters, without sacrificing its effectiveness. Index Terms—Web data extraction, automatic wrapper generation, wrappers, unsupervised learning 1INTRODUCTION THE Web is a huge repository in which data are usually presented using friendly formats, which makes it difficult for automated processes to use them. The literature provides many proposals to create socalled web data extractors, which are tools that facilitate extracting relevant data from typical web documents [9], [35]. Many web data extractors rely on extraction rules, which can be classified into ad-hoc or built-in rules. The costs involved in handcrafting ad-hoc rules motivated many researchers to work on proposals to learn them automatically using supervised techniques, i.e., techniques that require the user to provide samples of the data to be extracted, aka annotations [4]–[7], [10], [15]–[17], [20], [23], [24], [27], [29], [37], [38], or using unsupervised techniques, i.e., techniques that learn rules that extract as much prospective data as they can, and the user then gathers the relevant data from the results [2], [8], [11], [19], [21], [25], [26], [38]–[40]. Web data extractors that rely on built-in rules are based on a collection of heuristic rules that have proven to work well on many typical web documents [1], [14], [18], [32], [36]. Since such documents are growing in complexity, some authors are also working on techniques whose goal is to identify the region within a web document where the relevant data is most likely to reside [35]. Some authors have also paid attention to the problem of structuring the data extracted [3], [30]. In this article, we introduce a technique called Trinity, which is an unsupervised proposal that learns extraction rules from a set of web documents that were generated by •The authors are with the University of Sevilla, ETSI Informática, Sevilla E-41012, Spain. E-mail: {hassansleiman, corchu}@us.es. the same server-side template. It builds on the hypothesis that shared patterns are not likely to provide any relevant data and are, thus, part of the template. Whenever it finds a shared pattern, it partitions the input documents into the prefixes, separators and suffixes that they induce and analyses the results recursively, until no more shared patterns are found. Prefixes, separators, and suffixes are organised into a trinary tree that is later traversed to build a regular expression with capturing groups that represents the template that was used to generate the input documents. Thanks to the capturing groups, the expression can be used to extract data from similar documents. Note that our technique does not require the user to provide any annotations; instead, he or she must interpret the resulting regular expression and map the capturing groups that represent the information of interest onto the appropriate structures. The three most closely-related proposals are Road- Runner [11]–[13], ExAlg [2], and FiVaTech [21], which differ significantly from Trinity: RoadRunner is a parsing-based approach that uses a partial rule (which is initialised to any of the input documents) to parse another document and applies a number of generalisation strategies to correct the partial rule when mismatches are found; ExAlg finds maximal classes of tokens that occur in every input document, which are thus very likely to belong to the template, and then refines them using a token differentiation and a nesting criteria in order to construct the extraction rule; FiVaTech first identifies nodes in the input DOM trees that have a similar structure and then aligns their children and mines repetitive and optional patterns to create the extraction rule. We analysed the complexity of our proposal and proved that it is polynomial in both space and time. We also conducted a series of experiments with 55 real-world web sites and our results confirm that our proposal can achieve a mean precision as high as 0.96 ±0.07, a mean recall as high as 0.95±0.11, with a mean learning time of 0.13±0.16 Fig. 1. General view of our proposal. CPU seconds and a mean extraction time of 0.02 ±0.03 CPU seconds. We conducted the same experiments using two of the most closely-related techniques available and two well-known supervised proposals in the literature, and we then analysed the results using sound statistical techniques. Our conclusion was that our proposal performs better than the others and that its effectiveness does not depend at all on whether the input web documents are well- or malformed. Other techniques require the input to be correct XHTML, which requires to repair the source documents beforehand; experimentally, we found out that this has a negative impact on their effectiveness. Our proposal relies on two simple parameters that may introduce a bias in order to boost its performance, without sacrificing its effectiveness. Other techniques have parameters that need to be fined-tuned so that they work well. The rest of the article is organised as follows: Section 2 presents the algorithms that lie at the heart of Trinity; Section 3analyses both their space and time complexity; Section 4reports on our experimental results; Section 5 compares it to the most closely-related proposals from a conceptual point of view; Section 6concludes our work. A short paper on Trinity was presented elsewhere [34]. 2DESCRIPTION OF OUR ALGORITHMS In this section, we first provide an intuitive introduction to our proposal, then report on its limitations, and finally provide an algorithmic description. 2.1 Overview Fig. 1sketches our proposal, which takes a collection of web documents and a natural range [min ..max] as input. The web documents need to be tokenised, but they do not need to be correct XHTML documents; the range indicates the minimum and maximum size of the shared patterns for which the algorithm searches. Our proposal relies on the following data types: a sequence of tokens is called Text and represents either a whole input document or a fragment; a trinary tree is a collection of Nodes, each of which is a tuple of the form (T,a,p,e,s), where Tis a collection of Text,ais of type Text and contains a shared pattern in T,pis a Node called prefixes, eis a Node called separators, and sis a Node called suffixes. The algorithm first creates a root node with the input web documents and sets a variable called sto max. Starting with this node, the algorithm loops and searches for a shared pattern of size s. If such a pattern is found in the current node, then it is used to create three new child nodes with the prefixes, the separators, and the suffixes that this pattern induces; the prefixes are the fragments from the beginning of a Text up to the first occurrence of a shared pattern, the separators are the fragments in between successive occurrences, and the suffixes are the fragments from the last occurrence until the end of a Text. These nodes are analysed recursively in order to find new shared patterns that induce new nodes. If no shared pattern is found, that is, the tree is not expanded, but variable sis greater or equal to the minimum pattern size, then sis decreased and the procedure is repeated again until a node in which no shared pattern of size greater or equal to min is found. Fig. 2shows a sample trinary tree. Node N1 represents three sample input documents; the algorithm searches for the longest shared pattern, which is underlined, and then creates three new nodes with the prefixes, the separators, and the suffixes that it induces. Note that the shared pattern is found at the beginning of the input documents, so the prefixes are empty strings that we represent using symbol ε; note that the shared pattern occurs only once, which implies that there are not actually any separators, which we represent with symbol nil. The processing continues recursively on the new nodes. Note that leaf nodes that have variability, that is, contain different fragments, have data that is not likely at all to belong to the template. Once the trinary tree is built, we need to use an additional algorithm to learn the regular expression that represents the template used to generate the input web documents. This algorithm traverses the trinary tree in preorder; every time it reaches a leaf node that has variability, it outputs a fresh capturing group to extract the data that corresponds to that node; otherwise, it outputs the shared pattern that corresponds to the node being analysed and a closure or an optional operator depending on whether that node is repeatable (there can be multiple occurrences of the shared pattern) or optional (if some of the Textsit has are empty, but not all of them). Fig. 3(a) shows the regular expression that Trinity learns for the sample trinary tree in Fig. 2; capturing groups are represented as {A},{B}, ..., {F}. 2.2 Limitations Note that when the input documents have listings of records of different lengths, Trinity tends to deal with the first few attributes of the first record and the last few attributes of the last record differently from the attributes of the remaining records. For instance, in our illustrating example, the algorithm works on a collection of three web documents that have lists of book records, each of which has three attributes: title, authors, and price. Note, however, Fig. 2. Sample trinary tree. (Shared patterns are underlined in each node.) that the regular expression that Trinity learns has six capturing groups: Acorresponds to the title of the first record, E and Fcorrespond to the authors and price of the last record; B,C,andDcorrespond to the remaining authors, prices, and titles, respectively. This limitation is not so uncommon in other proposals; fortunately, some authors have worked on techniques that allow to map the data returned by extraction rules onto more appropriate data structures [3], [30]. We have, however, found quite a simpler approach to overcome this limitation: Trinity is an unsupervised technique, which means that it is the user who has to assign a semantic label to each capturing group; after that, several computergenerated labels may be assigned to the same semantic label, which results in a regular expression that can be very easily simplified as follows: transform it into a deterministic finite automata, then minimise the automata, and transform the results back into a regular expression. This results in the regular expression in Fig. 3(b), which represents faithfully the structure of the records in the input documents. Trinity learns union-free regular expressions. On a first reading, this might seem to prevent our proposal from working well with templates that have alternating formattings for the same data. Although this is true, we did not find this a serious limitation in practice Fig. 3. Regular expression learnt from our sample tree: (a) Before simplification. (b) After simplification. because typical web documents that use alternating formattings rely on CSS classes. For instance, a special price is typically output as follows: <span class="special">$99.95</span>; and a normal price is output as follows: <span class="normal">$125.00</span>.Thatis, the internal structure is almost identical although the rendering seems to suggest that it is not. There are cases in which the alternating formatting relies on tags like strong,emph,orstrike, which are output or not depending on whether a piece of data is going to be highlighted or not. Since we do not rely on a fixed tokenisation scheme, we may easily deal with such tags as if they were regular text. This is the same approach that was used in the implementation of RoadRunner and it has proved to work quitewellinpractice. An additional limitation occurs when the same sequence of tokens is used to separate different attributes in a data record. For instance, assume that data attributes are separated only by tag <br/>; in such cases, Trinity is likely to find that the data record includes multiple instances of the same attribute. This limitation was not usual at all in the datasets we used to evaluate our proposal; we only had trouble with the Major League and the IAF datasets, in which data were rendered in a simple table and we achieved an F1measureof0.70 and 0.52, respectively. In the rest of datasets, different formattings are used inside the data records to render different attributes, and this helps our technique extract them independently. This limitation was also detected in ExAlg [2]; the authors suggested that human effort and more HTML knowledge are necessary in this case. 2.3 Creating a Trinary Tree We present Algorithm createTrinaryTree in Fig. 4. It takes a node and a range of naturals as input and expands the node to create a trinary tree. The loop at lines 4-7 iterates over every possible size from max down to min as long as Algorithm expand cannot expand the current node, Fig. 4. Algorithm createTrinaryTree. which happens if it can find a shared pattern of the indicated size. If the loop finishes and the current node was expanded, then the algorithm is executed recursively on the new leaves that have been added to the current node. We present Algorithm expand in Fig. 5. Line 3 checks if node contains more than one Text; if so, it searches for a shared pattern by invoking Algorithm findPattern at line 4, which is described below; the algorithm checks if findPattern has found a shared pattern at line 5 and invokes Algorithm createChildren at line 7. Algorithm createChildren, which is described below, partitions the Text collection inside the input Node, and creates its child nodes; if no shared pattern is found, then the input Node remains unchanged. The previous algorithms were relatively intuitive. The key to their performance is the algorithm to find shared patterns, which we present in Fig. 6.First,itsearchesfor the shortest non-empty Text inside node at line 3 and stores it in base. The main loop at lines 5-16 allows to implement a sliding window over base: index iiterates from 0 until size(base)−sas long as no shared pattern is found. The actual search is performed in the inner loop at lines 8-12: in this loop, the algorithm iterates over every Text in the input Node, and finds all of the matches of the subsequence of base that starts at position iand has size s. Algorithm findMatches is implemented using the well-known Knuth-Pratt-Morris pattern search algorithm [22]. This algorithm returns a list of naturals that indicate the non-overlapping positions at which the previous subsequence of base matches text;if there is at least one match, we record it in variable result and go ahead to examine the next Text in node; otherwise, the inner loop finishes and the outer loop slides the window on base and resets map, if possible. If the algorithm returns an empty map, this means that no shared pattern Fig. 5. Algorithm expand. Fig. 6. Algorithm findPattern. has been found; otherwise, the map indicates the positions at which the shared pattern is found in each Text in the node being analysed. When a shared pattern is found in a Node, Algorithm createChildren creates the new child nodes: prefixes, separators, and suffixes. We present Algorithm createChildren in Fig. 7. This algorithm works on a Node, a map, and a pattern. Lines 3-5 create three empty Nodes, namely prefixes, separators,andsuffixes. Line 6 sets the node’s shared pattern to pattern. Then, the loop at lines 7-12 iterates over the Texts in map: for each Text text in the map, lines 9-11 get the matches where the shared pattern occurs, computes the prefix, separators, and suffix of the pattern in text, and adds them to the prefixes,separators,andsuffixes Nodesrespectively. If pattern is found at the beginning of text, the prefix is then an empty Text;ifpattern is found at the end of text, the suffix is then an empty Text; if two occurrences of pattern are consecutive in text, their separator is an empty Text,but if text contains only one occurrence of pattern,wethenadd the special value nil to separators. We do not provide a pseudocode to the algorithms to compute prefixes, separators, and suffixes since they are quite straightforward. Fig. 7. Algorithm createChildren. Fig. 8. Algorithm learnTemplate. 2.4 Algorithm learnTemplate Algorithm learnTemplate works on a trinary tree whose root is node, constructs a regular expression that represents a template, and returns it, cf. Fig. 8. It relies on two ancillary algorithms, namely: isOptional and isRepeatable.ANode is optional if one or more of its Texts, but not all, are empty. ANode is repeatable if one or more of its non-empty Texts have more than one occurrence of the shared pattern. The algorithm proceeds as follows: it works on a node and a regular expression that is expected to be empty initially; the algorithm constructs its result by adding text to this parameter on each recursive invocation. The core is the if-then-else sentence at lines 3-31, which distinguishes between leaf and non-leaf nodes. If node is a leaf and has variability, i.e., not all of its Texts are the same, this means that it contains variable data. In such cases, line 5 creates a new capturing group that represents a piece of text to be extracted. If node is not a leaf, then line 8 builds the regular expression that corresponds to the prefixes, which is performed recursively. The shared pattern is added to result at line 9 and the regular expression that corresponds to the separators is built at lines 10-18: if the node is repeatable, then the regular expression of the separators Node is built at line 12, the shared pattern is added to result at line 13, and the plus or star closures are added at lines 14-18. If the separators node contains the special value nil, this means that the shared pattern has appeared only once in at least one of the Textsinnode, thus a star closure must be used; contrarily, if the shared pattern has two or more occurrences in each Text in node, then a plus closure must be added. The algorithm builds now the regular expression that corresponds to the suffixes at line 20, which is performed recursively. Lines 2 and 22 check if the node being processed is optional, in which case parenthesis and an optional operator are added to the resulting regular expression. 3COMPLEXITY ANALYSIS In this section, we first present the results of our complexity analysis and then prove the lemmata that support them regarding space and time requirements. 3.1 Complexity Results Let ndenote the number of documents that Trinity has to analyse and let mdenote the size in tokens of the longest such document. From Lemmata 1and 2, which we present below, we conclude that nm 2is an upper bound to the maximum size of a node and that 3mis an upper bound to the maximum number of nodes the algorithm creates; as a conclusion, O(nm 23m)⊆O(nm2) is an upper bound to the space required to execute our proposal. Furthermore, according to Lemmata 6and 7, which we present below, Algorithms createTrinary- Tree and learnTemplate require no more than O(nm5) and O(nm2)time to complete, respectively. This implies that O(nm5+nm2)⊆O(nm5)is an upper bound to the worst-case time required to execute our proposal. In our experiments, it was common that nmsince the average value of nwas 37.89±41.67 and the average value of mwas 1842.40±1445.31; in such cases, we can conclude that O(m2)and O(m5)are upper bounds to the worst-case space and time complexity of Trinity. That is: our proposal is computationally tractable. 3.2 Space Requirements Lemma 1 (Maximum size of a Node). nm 2is an upper bound to maximum size of a Node createdbyAlgorithm createTrinaryTree. Proof. Algorithm expand is the only algorithm that creates new Nodes, which correspond to the prefixes, separators, and suffixes that a shared pattern pinduces. Regarding the prefix and suffix Nodes, note that there cannot be more than nsuch prefixes or suffixes since a document may not have more than one prefix or one suffix; that is, nis an upper bound to the maximum size of a Node that contains prefixes or suffixes. Regarding separators Nodes the worst-case happens when pis a one-token pattern that occurs every two tokens; that is, m 2is an upper bound to the number of separators in this case, that is, nm 2is an upper bound to the maximum size of a Node that contains separators. As a conclusion, nm 2is an upper bound to the maximum size of a Node created by createTrinaryTree. Lemma 2 (Maximum number of Nodes). 3m is an upper bound to the number of Nodes created by Algorithm createTrinaryTree. Proof. Algorithm expand creates three new Nodes when a shared pattern pis found in a given Node. The new Nodes correspond to the prefixes, separators, and suffixes to which pleads. We know that mis an upper bound to the number of partitions of a Text of size m, which means that mis an upper bound to the number of levels of the trinary tree in the worst-case. Since each level has three nodes, then 3mis an upper bound to the number of Nodes created by createTrinaryTree. 3.3 Time Requirements Lemma 3 (Algorithm createChildren). Let a be a Node,ra map from the Texts in a onto lists of indices that denote where a shared pattern occurs, and p the shared pattern. O(nm2) is an upper bound to the worst-case time required to execute createChildren(a,r,p). Proof. The algorithm iterates through every Text in a. According to Lemma 1,nm 2is an upper bound to the maximum size of a Node, which means that the nm is an upper bound to the number of iterations of this loop. Inside this loop, accessing the map and calculating the prefix and suffix of the shared pattern can be performed in O(1)time, whereas computing the separators requires variable time. According to Lemma 1,the maximum number of separators in a given Text is m 2, which is less than m. Then, O(m)is an upper bound to the time required to compute the separators. The instructions to create new nodes at lines 3-5 and the instructions to link them to the input Node at lines 13-15 require O(1)time. As a conclusion, O(nmm)=O(nm2)is an upper bound to the worst-case time required to execute createChildren(a,r,p). Lemma 4 (Algorithm findPattern). Let a be a Node and s the size of the pattern for which the algorithm searches. O(nm3)is an upper bound to the worst-case time required to execute findPattern(a,s). Proof. The algorithm first searches for the shortest Text in a. According to Lemma 1,nm 2is an upper bound to the maximum size of a Node, which implies that nm 2is an upper bound to the maximum time required to find the shortest Text in a Node. The main loop iterates through base until finding a pattern of stokens that occurs in every other Text in a. In the worst-case, base has the maximum size mand the shared pattern is found at the end of base, which means that the main loop iterates m−s times, i.e., O(m)times. In each iteration of the main loop, the inner loop iterates through the Textsina. According to Lemma 1,nm 2is an upper bound to the maximum size of a Node, which implies that the inner loop does not iterate more than nm 2times. In each iteration, it invokes Algorithm findMatches, whose worst-time complexity is O(k), where kdenotes the size of the text in which a pattern is searched [22]. This implies that O(m) is an upper bound to the worst-case time complexity of the instructions inside the inner loop. As a conclusion, O(nm 2+mnm 2m)⊆O(nm3)is an upper bound to the worst-case time required to execute findPattern(a,s). Lemma 5 (Algorithm expand). Let a be a Node,andsbea pattern size. O(nm3)is an upper bound to the worst-case time required to execute expand(a,s). Proof. In the worst-case, the invocation to Algorithm expand requires to invoke Algorithms findPattern and createChildren in sequence, which according to Lemmata 4and 3 require no more than O(nm3)and O(nm2)time in the worst-case. As a conclusion, O(nm3+nm2)⊆O(nm3) is an upper bound to the worst-case time required to execute expand(a,s). Lemma 6 (Algorithm createTrinaryTree). Let a be a Node, min and max be the minimum and maximum sizes of the shared patterns for which the algorithm searches, respectively. O(nm5)is an upper bound to the worst-case time required to execute createTrinaryTree(a,min,max). Proof. The algorithm first iterates through every possible size between min and max, which amounts to mtimes in the worst-case. In each iteration, the algorithm executes Algorithm expand, which according to Lemma 5requires no more than O(nm3)time. Then, O(nm4)is an upper bound to the first loop. If ais expanded, then another loop iterates through its leaves and executes Algorithm createTrinaryTree recursively. According to Lemma 2,3m is an upper bound to the number of Nodes created by createTrinaryTree. As a conclusion, O(nm43m)⊆O(nm5) is an upper bound to the worst-case time required to execute createTrinaryTree(a,min,max). Lemma 7 (Algorithm learnTemplate). Let a be a Node. O(nm2)is an upper bound to the worst-case time required to execute learnTemplate(a,“”). Proof. The algorithm works on a maximum of 3mNodes according to Lemma 2.IfaNode is a leaf, the algorithm iterates on its Texts no more than m 2times according to Lemma 1. Otherwise, the algorithm is invoked recursively on the children of this node, namely: prefixes, separators, and suffixes. In the case of the separators, whose number is limited by the upper bound nm 2,the algorithm iterates on them twice to check for repeatability and searching for nil values. As a conclusion, O(3m2nm 2)⊆O(nm2)is an upper bound to the worst-case time required to execute learnTemplate(a,“”). 4EXPERIMENTAL EVALUATION In this section, we first describe our experimentation environment, then report on our experimental results, and finally analyse them statistically. 4.1 Experimentation Environment We have developed a Java 1.7 prototype of our proposal using the CEDAR framework [33]1. We performed a series of experiments on a cloud computer that was equipped with a four-threaded Intel Core i7 processor that ran at 2.93 GHz, had 4 GiB of RAM, Windows 7 Pro 64-bit, Oracle’s Java Development Kit 1.7.0_02, and GNU Regex 1.1.4. We performed our experiments on a collection 2084 web documents from 55 datasets; 41 datasets were collected from real-world web sites and the remaining were downloaded from the RoadRunner and the RISE public repositories. The first group contains datasets on books, cars, conferences, doctors, jobs, movies, real estates, and sports. These categories were randomly sampled from The Open Directory sub-categories, and the web sites inside each category were randomly selected from the 100 best ranked web sites between December 2010 and March 2011 according to Google’s search engine. We downloaded 30 web documents from each web site and handcrafted a set of annotations with the data that we would like to extract from each document. The second group contains all of 1. http://www.tdg-seville.info/Download.ashx?id=341 the datasets available at the RoadRunner repository [11] and the datasets from the RISE repository that provide semi-structured web documents [28]. The most closely-related proposals are RoadRunner [11]–[13], ExAlg [2], and FiVaTech [21]. Unfortunately, we could not find a public implementation of ExAlg or get it from the authors. To complete the collection of baseline proposals, we selected two supervised classical proposals that rank amongst the most cited in the literature, namely: SoftMealy [20] and WIEN [24]. Our goal was to prove that Trinity improves on the most closely-related proposals for which we have found an implementation and that the fact that it is unsupervised does not actually have a negative impact on its effectiveness. 4.2 Experimental Results We ran Trinity, the latest version of RoadRunner [12], FiVaTech, SoftMealy, and WIEN on our datasets in order to learn extraction rules. Regarding Trinity, we set min =1 and max =0.05m, where mdenotes the size in tokens of the shortest input document. We measured the standard effectiveness measures (precision, recall, and the F1mea- sure) and two efficiency measures (learning and extraction time). In the case of SoftMealy and WIEN, it was easy to compute the precision and recall since both techniques are supervised, i.e., they require the user to provide annotations with the data to be extracted so that an extraction rule can be learnt and evaluated. Contrarily, Trinity, RoadRunner, and FiVaTech are unsupervised, i.e., they learn a rule that extracts as much data as possible, give each capturing group a computer-generated label, and it is the responsibility of the user to assign a meaning to these labels. Since we handcrafted annotations for every web document in our datasets, we could find which extracted data group was the closest to each annotation. To do so, we compared each piece of text extracted to every annotation, and computed the number of true positives (tp), false negatives (fn), and false positives (fp), since this allowed us to compute precision as P=tp tp+fp,recallasR=tp tp+fn, and the F1mea- sure as F1=2PR P+R. Given a group of annotations, we can consider that the precision and recall to extract them corresponds to the extracted data group with the highest F1measure. Table 1presents the results of our experiments. The columns report on the number of web documents in each dataset (N), their average size in KiB (S), average number of errors reported by JTidy (E), precision (P), recall (R), the F1measure(F1), learning time in CPU seconds (LT), and extraction time in CPU seconds (ET); in the case of Trinity, we also report on the CPU time in seconds to learn a rule without introducing any biases (LT), that is setting min to one and max to the size in tokens of the shortest input document. Since the results are rounded to two decimal digits, times that were smaller than 0.005 seconds are reported as 0.00 in the table, but at least four decimal digits were internally taken into account to compute the means and the standard deviations. A dash in a cell means that the corresponding technique was not able to learn an extraction rule in 15 CPU minutes or that it threw an exception. The first two rows provide a summary of these measures in terms of mean values and standard deviations. Our first conclusion is that the bias that Trinity allows to introduce, indeed helps boost its efficiency since the average learning time is 0.13 ±0.16 CPU seconds if the bias is introduced, whereas it is 10.82 ±33.85 CPU seconds without the bias. Finding a good bias is always a difficult task, since it requires to fine-tune the parameters on which a proposal relies so as to find an appropriate trade-off between efficiency and effectiveness; this, in turn, requires to have a good training set on which precision and recall can be computed. We experimentally found that setting min =1andmax =0.05m, where mdenotes the size in tokens of the shortest input document, was the maximum allowable bias, that is, a bias that boosts efficiency, but does not have a negative impact on the efficiency. In practice, our results suggest that Trinity can be used without introducing any biases since the learning times are quite competitive regarding the other proposal. To draw more conclusions from our experimental results, we summarised the F1 measures, the learning times, and extraction times in Figs. 9,10,and11, respectively. The summaries are presented as box plots, since they help intuitively compare these measures taking into account the whole range of values. Note that all of the techniques can achieve the maximum F1, which means that they can extract information with perfect precision and recall in some cases; what differentiates Trinity from the others is that its interquartile range is the smallest one and the highest one, which indicates that it can achieve high effectiveness in the majority of cases. These results suggest that the other techniques perform more irregularly and worst than Trinity regarding effectiveness. The results are similar regarding efficiency: note that the range from the first to the third quartile is smaller for Trinity than for the other techniques regarding the learning time and similar to RoadRunner’s regarding the extraction time, but clearly smaller than for the other techniques; the dispersion from the minimum values to the first quartile and from the third quartile to the maximum are also a clear indication that our technique performs more homogeneously than the others regarding learning and extraction time, with the only exception of RoadRunner regarding the extraction time. These results suggest that the other techniques perform worst than Trinity regarding efficiency, except for RoadRunner. Table 1also reports on the average number of errors JTidy found in each dataset. Our goal was to check that Trinity is not affected by the fact that typical web documents are malformed XHTML documents. To draw a conclusion, we plotted the F1measures we gathered for every pair of datasets and techniques and the number of errors in a radial chart, cf. Fig. 12. Unfortunately, it is difficult to discern whether variations to the number of errors hasanimpactontheF1 measure. Therefore, we defer drawing a conclusion on this topic to the statistical analysis in the following section. TABLE 1 Experimental Results 4.3 Statistical Analysis To confirm that the conclusions we have drawn from our empirical evaluation are valid, we need to perform a statistical analysis [31]. This consists in performing a statistical ranking regarding our performance measures and determining if there is a significant correlation from the number of errors to the effectiveness of the techniques we have evaluated. We have conducted a Shapiro-Wilk test at the standard significance level α=0.05 on every measure and we have found out that none of them behaves normally. As a conclusion, we have used non-parametric analysis techniques. The steps were the following: a) compute the rank of each technique from the evaluation results; b) determine if the differences in ranks are significant or not using Iman- Davenport’s test; c) if the differences are significant, then compute the statistical ranking using Bergmann-Hommel’s test on every pair of techniques. Table 2presents the results of the analysis. (Due to space limitations, we only report on the adjusted p-values, not on the exact values of the statistics.) Note that the p-value of Iman-Davenport’s statistic is nearly zero in every case, which is a strong indication that there are statistically significant differences in the ranks we have computed from Fig. 9. Comparison of F1 measures. our experiments. It then proceeds to rank the techniques pairwise using Bergmann-Hommel’s test. For the sake of readability, we also provide an explicit ranking in the last column. Note that our proposal ranks the first regarding every effectiveness and efficiency measures; the only tie is regarding extraction time, in which case the difference with respect to RoadRunner does not seem to be statistically significant. As a conclusion, our experiments prove that there is enough statistical evidence to conclude that our proposal outperform the others. Recall from the previous section that we could not draw an intuitive conclusion on whether the errors in the input web documents have an impact on the effectiveness of the techniques we have compared. To discern if there is such an impact from an statistical point of view, we need to calculate the correlation from the number of errors to the F1 measure using Kendall’s τprocedure. Table 3presents the results of this procedure. Note that the p-value of the correlation coefficients is smaller than the standard significance level α=0.05 except for the case of RoadRunner and FiVaTech; in these cases the correlation coefficient is negative, which means that the effectiveness of these techniques is expected to decrease as the number of errors Fig. 10. Comparison of learning times. Fig. 11. Comparison of extraction times. in the input documents increases. As a conclusion, our experiments do not show any statistical evidence that the effectiveness of our technique is sensitive to malformed input documents. 5RELATED WORK In the introduction, we listed and classified many of the proposals on data extraction that we have found in the literature. Our conclusion was that Trinity is closely related to RoadRunner [11]–[13], ExAlg [2], and FiVaTech [21], which are the other three proposals that learn a regular expression that models the template used to generate the input documents. This is the reason why we restrict our conceptual comparison to them. RoadRunner was originally proposed by [13]. It works on a collection of web documents and compares them side by side in order to infer a union-free regular expression that describes their template. Although the proposal works on the text of the input documents, it requires them to be repaired beforehand using tools like JTidy since the algorithm needs the input documents to be well-formed. The proposal constructs the extraction rule incrementally by means of a string alignment algorithm that is specifically tailored to XHTML. The initial rule is set to any of the input documents, and it is then used to parse the others. During parsing, the algorithm may find mismatches Fig. 12. Correlation from number of errors to the F1 measure.