TEX: An efficient and effective unsupervised Web information extractor

TEX: An efficient and effective unsupervised Web information extractor Hassan A. Sleiman ⇑ , Rafael Corchuelo Universidad de Sevilla, ETSI Informática. Avda. de la Reina Mercedes, s/n, Sevilla E-41012, Spain article info Article history: Received 23 March 2012 Received in revised form 11 October 2012 Accepted 12 October 2012 Available online 26 October 2012 Keywords: Information extraction Semi-structured web documents Malformed documents Unsupervised technique Heuristic-based technique abstract The World Wide Web is an immense information resource. Web information extraction is the task that transforms human friendly Web information into structured information that can be consumed by automated business processes. In this article, we propose an unsupervised information extractor that works on two or more web documents generated by the same server side template. It finds and removes shared token sequences amongst these web documents until finding the relevant information that should be extracted from them. The technique is completely unsupervised and does not require maintenance, it allows working on malformed web documents, and does not require the relevant information to be formatted using repetitive patterns. Our complexity analysis reveals that our proposal is computationally tractable and our empirical study on real-world web documents demonstrates that it performs very fast and has a very high precision and recall. Ó2012 Elsevier B.V. All rights reserved. 1. Introduction The Web is the hugest information repository. Usually, scripts are used to fill in templates with information that is retrieved from server-side databases; the results are formatted using HTML tags and CSS classes. The documents in the Web can be classified into two groups: unstructured documents, whose relevant information are pieces of free text, e.g., blog entries or news articles, and semistructured documents, whose relevant information are records of attributes that are usually formatted as tables or lists, e.g., an online book store. (Note that the criteria to classify which information is relevant depends completely on the context.) Our work focuses on semi-structured documents. Extracting the relevant information from a semi-structured document to feed an automated business process is not usually an easy task due to the irrelevant information that the template introduces in order to present it in a friendly format [3]. Information extractors are intended to help software engineers in this task [10]. Many information extractors rely on extraction rules. Although they can be handcrafted [15,24,4,42,51,50,20], the costs involved motivated many researchers to work on proposals to learn them automatically. These proposals are either supervised, i.e., they require the user to provide a number of information samples to be extracted [11,44,58,26,32,8,22,9,14,18,30,5,40,21,59], or unsupervised, i.e., they extract as much prospective information as they can and the user then gathers the relevant information from the results [62,12,16,2,28,25,60,39,46,64,67,38,59,57]. Since typical web documents are growing in complexity, a number of authors are also working on techniques whose goal is to identify the region within a web document where relevant information is most likely to be contained [37,7,61,63,27,34,65,66,52,45,35,6]. Sleiman and Corchuelo [55] have recently surveyed and compared the previous techniques. Information extractors that rely on extraction rules do not usually adapt well to changes to the Web. Note that once a set of extraction rules is handcrafted or learnt, the Web keeps evolving and it is not uncommon that changes may invalidate the existing extraction rules. This motivated some authors to work on proposals to maintain extraction rules (semi-)automatically [31,48,49,41,33,13]. Contrarily, others worked on unsupervised proposals that do not rely on extraction rules, but are based on a number of hypothesis and heuristics that have proven to work well in many cases [1,53,17,23]; changes to a web site do not usually have an impact on these extractors since they analyse every new web document independently from the previous ones. Our focus is on unsupervised proposals that do not rely on extraction rules. The existing proposals work on one or more input web document and search for repetitive structures that hopefully identify the regions where the relevant information resides. Álvarez et al. [1] use clustering to find a rough region where the relevant information is most likely to be located, i.e., the information region, and then use clustering, tree matching and multi-string alignment to extract prospective information; Simon and Lausen [53] first use a modified version of MDR [36] and then a multi-string alignment algorithm to extract prospective information; Buttler et al. [6] rely on six heuristics to identify the information region and to extract prospective information from it; the proposals by Refs. [17,23] focus on extracting prospective information from lists: 0950-7051/$ - see front matter Ó2012 Elsevier B.V. All rights reserved. http://dx.doi.org/10.1016/j.knosys.2012.10.009 ⇑ Corresponding author. E-mail addresses: [email protected] (H.A. Sleiman), [email protected] (R. Corchuelo). Knowledge-Based Systems 39 (2013) 109–123 Contents lists available at SciVerse ScienceDirect Knowledge-Based Systems journal homepage: www.elsevier.com/locate/knosys the former uses a corpus and a scoring function that helps delimit the information in a list and tabulate it, whereas the latter learns a statistical model according to which the information is also delimited and tabulated. Implicitly, the previous proposals assume that the input web documents contain similar information records since they all rely on finding repetitive structures. A four-page abstract of our proposal was presented elsewhere [56]. In this article, we introduce TEX, which is an unsupervised information extractor that does not rely on extraction rules. Contrarily to the previous proposals, it does not require the input web documents to be translated into DOM trees, i.e., it can work on malformed web documents without correcting them, and does not require the relevant information to be formatted using repetitive structures inside a web document. It works on two or more web documents and compares them in an attempt to discover shared patterns that are not likely to provide any relevant information, but parts of the template used to generate the web documents. (We define a shared pattern of size sbetween two token sequences t1 and t2 as a subsequence of sconsecutive tokens that occurs at least once in both t1 and t2.) The idea of identifying shared patterns lies at the heart of proposals like RoadRunner [16], which uses a multi-string alignment algorithm to learn a regular expression that models the template and its variable parts, FiVaTech [28], which relies on tree matching, tree alignment, and mining techniques, or EXALG [2], which uses two statistical techniques to differentiate the role of individual tokens and determine which are equivalent to one another. Contrarily to these proposals, TEX relies on quite a simple multi-string alignment algorithm that has proven to be very effective and efficient in practice. We have computed an upper limit to the worst-case space and time complexity of our algorithm and we have proven that it is computationally tractable (note that there are very few complexity results in this field); furthermore, we have conducted a series of experiments with 2084 web documents from 55 real-world web sites and our results confirm that our proposal can achieve a mean precision as high as 96%, a mean recall as high as 95%, with a mean execution time of 0.81 s. We conducted the same experiments using other well-known techniques in the literature, and our conclusion is that our proposal outperforms them. The rest of the article is organised as follows: Section 2presents TEX and describes the sub-algorithms on which it relies; Section 3 analyses its time complexity; Section 4reports on our experimental results and compares TEX to other techniques in the literature; finally, Section 5concludes our work. 2. Description of our proposal We present the algorithm that lies at the heart of TEX in Fig. 1.It works on a collection of web documents, which we denote as TextSet, and a range of integers, which can introduce a bias to our search procedure. Intuitively, a TextSet is a set of Texts, which are sequences of Tokens. TEX is not bound with a particular tokenisation schema; our implementation and our experiments were carried out using a simple tokenisation schema according to which tokens represent either script blocks, style blocks, HTML tags, or #PCDATA, but this is not an intrinsic feature of our proposal. Note that we use Text as a data type that allows to represent both web documents and fragments of web documents, as well as the information that is extracted from them. The algorithm works in two steps: at line 2, we invoke Algorithm extract, which makes an attempt to extract the information that varies from document to document; in other words, it attempts to discard information that is likely to belong to the template used to generate the input web documents. Algorithm extract works on the collection of input web documents and searches for shared patterns of size max;max 1;...;min.If min >1ormax is less than the size of the shortest input document, then the search has a bias that may lead to situations in which Algorithm extract returns information that actually belongs to the template, which is the reason why we invoke a filtering algorithm at line 3. Fig. 2 presents a running example. We assume that the algorithm is executed on TextSet TS1, which is composed of documents T1;T2, and T3; the result is the list of TextSetsL1, which contains the extracted TextSets TS4;TS7;TS11;TS12;TS9, and TS10. In the following subsections, we provide additional details on the ancillary algorithms on which TEX relies. 2.1. Algorithm extract Algorithm extract searches for shared patterns of size max down to min in a TextSet. For instance, assume that it is invoked on the TextSet denoted as TS1inFig. 3 and that it has to search for shared patterns whose size is in the range 10 down to 1. Note that there are neither shared patterns of size 10;9, nor 8; the longest shared pattern is <html><head><title>Results</title></Head><body>, whose size is 7 tokens. The algorithm then attempts to expand TextSet TS1 into three additional TextSets that contain the prefixes, the separators, and the suffixes into which the shared pattern partitions the TextsinTS1. In this example, there are neither prefixes nor separators, since the shared pattern is found at the beginning of the TextsinTS1; there are, however, three suffixes that are stored in TextSet TS2. The algorithm then discards TextSet TS1 and proceeds with the new TextSet TS2. The longest shared pattern that is discovered in TS2is<br/></body></html>, which results in a new TextSet that is denoted as TS3. The same procedure is applied as many times as necessary until no more shared patterns are discovered. We present Algorithm extract in Fig. 4. It works on a TextSet ts,a minimum pattern size min and a maximum pattern size max; it returns a list of TextSets that should contain as much prospective information as possible. The main loop at lines 3–15 iterates over all possible sizes from max down to min; for each size, the inner loop at lines 5–13 searches for a shared pattern of that size. Note that variable result acts as a queue in which we initially put the TextSet on which the algorithm has to work, and then the new TextSets into which it is expanded. In each iteration of the inner loop, a TextSet is removed from result and expanded at line 7. Algorithm expand, which is presented in the following section, searches for shared patterns of a given size in a TextSet; if one such pattern is found, then it is used to expand the current TextSet into new TextSets with prefixes, separators, and suffixes, which are added to result so that they can be analysed later in the inner loop; if no shared pattern is found, then the original TextSet is added to a buffer. Once the inner loop finishes, the buffer contains all of the new TextSets that have been produced, and it is transferred to the result variable so that the algorithm can search for new shared patterns of a smaller size, if possible. Algorithm expand. This algorithm searches for a shared pattern of a given size inside a given TextSet; if such a pattern is found, it then expands the TextSet into a collection of new TextSets with prefixes, separators, and suffixes. We have already illustrated how Algorithm expand works on two simple cases in which the expansion Fig. 1. Algorithm TEX. 110 H.A. Sleiman, R. Corchuelo / Knowledge-Based Systems 39 (2013) 109–123 Fig. 2. A running example. Fig. 3. Expansion of a TextSet during extraction. H.A. Sleiman, R. Corchuelo / Knowledge-Based Systems 39 (2013) 109–123 111 led to prefixes or suffixes only, cf. Fig. 3. Assume now that it is invoked on TextSet TS3inFig. 5 to search for a shared pattern of size two tokens. The algorithm can easily detect that the first two-to- ken shared pattern is <br/><b> and expands TextSet TS3 into the following new TextSets: (i) TS4, which contains the prefixes of the TextsinTS3 up to the first occurrence of the shared pattern; (ii) TS5, which contains the separators, i.e., the TextsinTS3 in between successive occurrences of the shared pattern; (iii) and TS6, which contains the suffixes of the TextsinTS3 regarding the last occurrence of the shared pattern. When expand is invoked on TextSet TS5 to find a shared pattern of size two tokens, it finds </b><br/>, and creates TS7 and TS8, which contain the prefixes and suffixes of the shared pattern respectively. The same happens when expand is invoked on the TextSet TS6 to search for a shared pattern of size two tokens, and creates TS9 and TS10. If we invoke expand on TextSet TS8 to search for a shared pattern of size one token, then, it finds pattern <br/> and creates TextSets TS11 and TS12. We present Algorithm expand in Fig. 6. Line 3 searches for the shortest Text in ts, which is used at line 5 as a basis to search for shared patterns by means of Algorithm findPattern, which is described in the following section. If this algorithm can find a shared pattern, then line 7 expands ts using that shared pattern and updates variable result; if not, result remains an empty list, which indicates that TextSet ts cannot be expanded. Algorithm findPattern. This algorithm works on a TextSet ts,a Text base, which is assumed to be the shortest non-empty Text in ts, and a size s. Its goal is to find a pattern inside base that occurs in every Text in ts. For instance, assume that the algorithm is invoked on TextSet TS3inFig. 7 to search for a pattern of size 2; we implicitly assume that base is the shortest Text in TS3, i.e., base ¼Catch Me <b>Lisa Gardner </b> $14.94 in this example. The algorithm first searches for Catch Me<br/> in every Text in TS3, but does not find it; then it searches for <br/><b>, which is found in every Text in TS3. As a conclusion <br/><b> is a shared pattern that can be used to expand TextSet TS3. Note that Algorithm find- Pattern returns a map from Text onto lists of integers; the map represents the positions where the search pattern is found. In our example, this map is fT7#h1i;T8#h1;9i;T9#h1;9ig. We present Algorithm findPattern in Fig. 8. The main loop at lines 3–11 allows to implement a sliding window over base: index iiterates from 0 until sizeðbaseÞsas long as no shared pattern is found, i.e., it searches for all patterns of size sin base. The actual search is performed in the inner loop at line 6–10: in this loop, the algorithm iterates over every Text in the input TextSet and finds all of the matches of the subsequence of base that starts at position iand has size s. We do not provide any additional details on Algorithm findMatches since it is implemented using the well-known Knuth–Pratt–Morris pattern search algorithm [29]. This algorithm Fig. 4. Algorithm extract. Fig. 5. Expansion of a sample TextSet. 112 H.A. Sleiman, R. Corchuelo / Knowledge-Based Systems 39 (2013) 109–123 returns a list of integers 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 ts; otherwise, the inner loop finishes and the outer loop slides the window on base and resets result, if possible. If the algorithm returns an empty map, this means that no shared pattern has been found. Algorithm createExpansion. When a shared pattern is found in a TextSet, the TextSet is expanded to three new TextSets, namely: prefixes, separators, and suffixes. We present Algorithm createExpansion in Fig. 9. This algorithm works on a TextSet called ts and a map rthat contains the indexes of the shared pattern inside each Text of ts. The loop at lines 6–15 iterates over all of the Textsin ts and adds the prefixes, separators, and suffixes to variables ts 1 ;ts 2 , and ts 3 , respectively. Later, we add these intermediate TextSets to the result variable as long as they are not empty. 2.2. Algorithm filter Algorithm extract returns a list of TextSets that are expected to have the variable information in the initial TextSet. Note, however, that min and max introduce a bias to the search algorithm if min is greater than one or max is less than the size of the shortest Text in the initial TextSet. Our experimental results prove that this bias helps effectively reduce the amount of effort required to extract information from typical web documents, without sacrificing effectiveness. There are, however, cases in which setting min to a value greater than one and setting max to a small value, may preventAlgorithm extract from finding small shared patterns. For instance, assume that we set min ¼2 and max ¼2 and that Algorithm extract returns the list of TextSetsL 0 1inFig.10: if the algorithm wasallowed to search for patterns of size one, then it would discover that <html> is a shared pattern and would discard TextSet TS 0 8; however, min was set to 2, which prevents the algorithm from finding this pattern. We present Algorithm filter in Fig. 11. The main loop at lines 3–7 iterates over the list of input TextSets and simply removes those without variability from the result, i.e., those TextSets in which all of the Texts are the same. 3. Complexity analysis In this section, we provide an upper limit to the worst-case time complexity of Algorithm TEX. Note that it is not common to find a complexity analysis in the literature regarding information extraction, but we think that it is important to make sure that the proposal is computationally tractable. Note, too, that the actual time complexity depends on a variety of variables that are not easy Fig. 6. Algorithm expand. Fig. 7. Searching for a pattern using Catch Me <b>Lisa Gardner </b> $14.94 as a base. Fig. 8. Algorithm findPattern. H.A. Sleiman, R. Corchuelo / Knowledge-Based Systems 39 (2013) 109–123 113 to characterise; since our only goal was to prove that TEX is computationally tractable, we have just characterised an upper bound to the worst-case time complexity building on two sensible assumptions: (i) simple instructions like adding an item to a set, comparing Fig. 9. Algorithm createExpansion. Fig. 10. A case in which filtering the results of Algorithm extract is necessary. 114 H.A. Sleiman, R. Corchuelo / Knowledge-Based Systems 39 (2013) 109–123 two tokens, or constructing a tuple can be implemented in Oð1Þ time with regard to the other algorithms in our proposal; (ii) the number of input documents is generally very small as compared with the number of tokens of the longest document to be analysed. In the following subsections, we first present a preliminary result regarding space requirements, then analyse the time complexity of the ancillary algorithms on which TEX relies, and conclude with a theorem that proves that TEX is computationally tractable. In the sequel, we use variable nto denote the number of documents that TEX has to analyse and mto denote the size in tokens of the longest such document. 3.1. Space requirements Proposition 1 (Maximum size of a TextSet). Assume that we are extracting information from a TextSet denoted as ts using Algorithm TEX. nb m 2 cis an upper bound to maximum size of a TextSet generated by TEX. Proof. Algorithm expand is the unique algorithm that generates new TextSets, which happens when a shared pattern pis found in a given TextSet. The new TextSets correspond to the prefixes, separators, and suffixes to which pleads. Regarding the prefix and suffix TextSets, note that there cannot be more than nsuch prefixes or suffixes; that is, nis an upper bound to the maximum size of a TextSet that contains prefixes or suffixes. Regarding separator TextSets the worst case happens when pis a one-token pattern that occurs every two tokens; that is, b m 2 cis an upper bound to the number of separators in this case, or, otherwise, nb m 2 cis an upper bound to the maximum size of a TextSet that contains separators. As a conclusion, nb m 2 cis an upper bound to the maximum size of a TextSet generated by TEX. h 3.2. Time requirements Lemma 1 (Algorithm createExpansion). Let ts be a Textset, r be a map from the Texts in ts to lists of indices that denote where a shared pattern occurs, and s be the size of the shared pattern. Oðnm 2 Þis an upper bound to the worst-case time required to execute createExpansionðts;r;sÞ. Proof. The algorithm iterates through every Text in ts. According to Proposition 1,nb m 2 cis an upper bound to the maximum size of a TextSet, which means that the nmis 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 Proposition 1, the maximum number of separators in a given Text is b m 2 c, which is less than m. Then, OðmÞis an upper bound to the time required to compute the separators. As a conclusion, OðnmmÞ¼Oðnm 2 Þis an upper bound to the worst-case time required to execute createExpansionðts;r;sÞ.h Lemma 2 (Algorithm findPattern). Let ts be a TextSet, base be the shortest Text in ts, and s be the size of the pattern for which the algorithm searches. Then, Oðnm 3 Þis an upper bound to the worst-case time required to execute findPatternðts;base;sÞ. Proof. The main loop iterates through base until finding a pattern of stokens that occurs in every other Text in ts. 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stimes, i.e., OðmÞtimes. Ineach iteration of the main loop, the innerloop iterates through the Textsints. According to Proposition 1,nb m 2 cis an upper bound to the maximum size of a TextSet, which implies that the inner loop does not iterate more than nb m 2 ctimes. 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 [29]. 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ðmnb m 2 cmÞ#Oðnm 3 Þis an upper bound to the worst-case time required to execute findPatternðts;base;sÞ.h Lemma 3 (Algorithm expand). Let ts be a TextSet, and s be a pattern size. Oðnm 3 Þis an upper bound to the worst-case time required to execute expandðts;sÞ. Proof. The algorithm first searches for the shortest Text in ts. According to Proposition 1,nb m 2 cis an upper bound to the maximum size of a TextSet, which implies that nb m 2 cis also an upper bound to the maximum time required to find the shortest Text in aTextSet. In the worst case, the invocation to Algorithm expand requires to invoke Algorithms findPattern and createExpansion in sequence, which according to Lemmas 2 and 1 require no more than Oðnm 3 Þand Oðnm 2 Þtime in the worst case. As a conclusion, Oðnb m 2 cþnm 3 þnm 2 Þ#Oðnm 3 Þis an upper bound to the worstcase time required to execute expandðts;sÞ.h Lemma 4 (Algorithm extract). Let ts be a TextSet, min and max be the minimum and maximum sizes of the shared patterns for which the algorithm searches, respectively. Oðnm 5 Þis an upper bound to the worst-case time required to execute extractðts;min;maxÞ. Proof. The algorithm first iterates through all possible sizes between min and max, which amounts to mtimes in the worst case. In each iteration, the algorithm executes an inner loop that iterates through successive expansions of ts. Note that mputs an upper bound to the number of times that a TextSet can be expanded, which implies that mis also an upper bound to the number of iterations of the inner loop. Within this loop, the only significant instruction regarding our complexity analysis is the invocation of Algorithm expand, which according to Lemma 3 requires no more than Oðnm 3 Þtime. As a conclusion, Oðmmnm 3 Þ¼Oðnm 5 Þis an upper bound to the worst-case time required to execute extractðts;min;maxÞ.h Lemma 5 (Algorithm filter). Let L be a list of TextSets of size k. OðknmÞis an upper bound to the worst-case time required to execute filterðLÞ. Proof. The algorithm iterates through every Text in L. If we denote the size of Las k, then this loop iterates ktimes. In each iteration, the algorithm checks the variability of the current TextSet, which requires to compare the first Text to every other in order to determine whether the TextSet has variability or not. According to Fig. 11. Algorithm filter. H.A. Sleiman, R. Corchuelo / Knowledge-Based Systems 39 (2013) 109–123 115 Proposition 1,nb m 2 cis an upper bound to the number of Textsina TextSet, which implies that Oðknb m 2 cÞ #OðknmÞis an upper bound to the worst-case time required to execute filterðLÞ.h 3.3. Complexity of TEX Theorem 1 (Algorithm TEX). Let ts be a TextSet and min and max be the minimum and maximum sizes of the shared patterns for which TEX searches. Then, Oðnm 5 Þis an upper bound to the worst-case time required to execute TEXðts;min;maxÞ. Proof. The proof follows straightforwardly from the previous lemmas. Note that Algorithm TEX invokes Algorithms extract and filter in sequence, which, according to Lemmas 4 and 5 require no more than Oðnm 5 Þand OðknmÞtime to complete, where kdenotes the size of the list of TextSets returned by Algorithm extract. Note that mputs an upper bound to the size of this list, which implies that Oðnm 5 þnm 2 Þ#Oðnm 5 Þis an upper bound to the worst-case time required to execute TEXðts;min;maxÞ.h Corollary 1. If we assume that n m, then Oðm 5 Þis an upper bound to the worst-case time complexity of Algorithm TEX, which makes it computationally tractable. 4. Experimental results In this section, we present the results of the experiments we have carried out to compare TEX to other techniques in the literature from an empirical point of view. We have developed a prototype of TEX using the CEDAR framework [54]. We performed our experiments on a machine that was equipped with an Intel Core i7 processor that ran at 3.4 GHz, had 8 GB of RAM, Windows 7 Pro 64-bit, Oracle’s Java Development Kit 1:7:003 b02, and GNU Regex 1:1:4. First, we describe the datasets used in our experimental study, then we describe the techniques in the literature with which we compared TEX, next we study the effectiveness and the efficiency of the techniques, and finally we rank them statistically. 4.1. Datasets We performed our experiments on a collection of 55 datasets that contain a total of 2084 web documents that can be classified into two groups: the first group is composed of 41 datasets gathered from 41 real-world web sites, whereas the second group is composed of 14 datasets downloaded from two 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, i.e., we created a number of TextSets with the information that we would like to extract from each site. The second group contains all of the datasets available online at the EXALG repository [2] and the datasets composed of semistructured web documents available at the RISE repository [43]. Table 1 show the information in which we were interested from the datasets. JTidy is a Java implementation of HTML tidy [47], which is a proposal that is intended to preprocess web documents by fixing their HTML code and converting it into XHTML. For instance, it fixes web document doctype declarations, adds missing end tags, and reports on unknown attributes, if necessary. Since our datasets were gathered from real-world web sites, they usually contained errors in their HTML code. Table 2 presents the results we have gathered regarding a subset of common HTML errors that are reported by JTidy; the full report is too large to be reproduced here. Our only purpose was to make it clear that we have dealt with actual documents, and that they usually contain errors that must be fixed heuristically. JTidy is a constituent part of many information extraction proposals that build on DOM trees. Note that TEX does not require to use JTidy since it can work on malformed input documents. Table 3 reports on some properties of the datasets. The first column illustrates the categories of the datasets; the second and the third columns list the web sites and an identifier that we use in the following tables; the fourth column reports on the number of documents inside each dataset; the fifth column shows the mean size of documents in kibibytes; the sixth column shows the mean number of errors reported by JTidy inside each dataset; the seventh column reports on the mean time in seconds required to clean and fix a web document; finally, the last column reports on the mean time to tokenise each document. 4.2. Other techniques We searched the Web or requested the authors of the related information extraction techniques to send us the implementations of their proposals. Unfortunately, we only managed to get the following implementations: RoadRunner [16]: It takes two or more web documents as input and tries to learn a union-free regular expression that describes them. It considers the first web document as a base template and then iterates through the other web documents; in each iteration, it compares the current web document with the base template using a string alignment algorithm, then collapses mismatches, and applies a backtracking algorithm to detect optional and repetitive patterns. FiVaTech [28]: It takes one or more web documents as input and tries to learn the template that was used to generate them. FiVaTech applies a clustering algorithm that applies a tree-edit distance to the DOM nodes of the input web documents; it then uses a matrix alignment algorithm to align the previous nodes on a per-cluster basis; then, it applies an algorithm to mine repetitive patterns in the aligned matrix, and, finally, applies some heuristics to detect optionality. SoftMealy [26]: It takes a collection of web documents and their corresponding annotations as input and learns an extraction rule that is a non-deterministic finite-state transducer. The states of the transducer indicate the attributes to extract, the transitions account for the possible orderings of the attributes in the input web documents, and the conditions indicate when the extraction of an attribute should start or end. Transition conditions are learnt using a token alignment and generalisation algorithm. WIEN [32]: It takes a collection of annotated web documents as input and learns simple regular expressions that contain the delimiters of the information that should be extracted. These delimiters are the longest common prefix of characters, and the longest common suffix of characters for each type of attributes. WIEN cannot handle optional attributes. 4.3. Effectiveness analysis We first ran RoadRunner, FiVaTech, SoftMealy, and WIEN on the datasets in order to learn extraction rules. Since there is not an 116 H.A. Sleiman, R. Corchuelo / Knowledge-Based Systems 39 (2013) 109–123 upper bound to the learning time, we set a time out of 15 CPU minutes. We then computed precision (P), recall (R), and F 1 -measure (F 1 ). In the case of SoftMealy and WIEN, it was easy to compute the precision and recall for each attribute since both techniques are supervised, i.e., they require the user to provide annotations with the information to be extracted so that an extraction rule can be learnt and validated. Contrarily, TEX, RoadRunner, and FiVaTech are unsupervised, i.e., they extract as much prospective information as possible, and it is the responsibility of the user to label that information appropriately. TEX extracts the information in the form of TextSets, RoadRunner as sets that correspond to the instantiation of variables in the regular expressions it learns, and FiVa- Tech from so-called basic types in the template it learns. In spite of the differences, note that the result of the extraction process is always a collection of TextSets, which are labelled with userdefined labels in the case of SoftMealy and WIEN, but computergenerated labels in the case of TEX, RoadRunner, and FiVaTech. Since we handcrafted annotations for every web document in our datasets, we could find which extracted TextSet was the closest to each annotation. To validate our technique, we compared each TextSet extracted to every annotation, and computed the number of true positives (tp), false negatives (fn), and false positives (fp), which allowed us to compute precision as P¼ tp tpþfp , recall as R¼ tp tpþfn , and the F 1 -measure as F 1 ¼2 PR PþR . Given an annotation, we considered that the precision and recall to extract it correspond to the extracted TextSet with the highest F 1 measure. Recall that TEX can introduce a bias to the algorithm that searches for shared patterns. In our experiments, we used the following heuristic to find the most appropriate bias: we first set min to 1 and max to the size of the longest input document, let it be m, and we measured precision and recall; note that this does not introduce any bias, since these values allow TEX to explore every possible shared pattern. We then set max ¼b m 2 cand measured precision and recall again; if there were no changes, we then set max ¼b m 4 cand repeated the procedure until precision or recall was affected. Similarly, we explored changes to min. We experimentally found that setting min ¼2 and max ¼b0:05mcwas the maximum allowable bias. This resulted in a significant reduction of CPU time, without having an impact on neither precision nor recall. Table 4 shows our results regarding effectiveness. The first few rows provide a summary in terms of mean and standard deviation of precision, recall, and F 1 -measure regarding TEX and the other techniques. In average, TEX seems to outperform the other techniques in both precision and recall. The remaining rows provide the results we obtained for each web site. Note that some cells contain a dash, which indicates that the corresponding technique was not able to learn an extraction rule in 15 CPU minutes. The drawbacks and the weak points of each technique were reflected in the previous results. RoadRunner and WIEN do not take disjunctions into account, which means that they have trouble with web documents in which different formats are used to display the same information; this is the reason why their precision and recall are relatively low and the standard deviation is relatively high. FiVaTech and RoadRunner could not learn the extraction rules for many datasets due to the complexity of their learning algorithms. SoftMealy has the problem known as early matching, which was reported by [44]: it does not consider the cases in which Table 1 Information of interest from the datasets. Repository Category Information of interest Ours Books Title, author, price, year, isbn Cars Model, year, description, price, type, colour, milage, transmission, engine, doors Conferences Title, date, place, url Doctors Name, address, phone, fax, specialty Jobs Location, company Movies Title, director, actor, year, runtime Real estate Address, bedrooms, bathrooms, price, size Sports Name, birth, hight, weight, age, college, country, club, position EXALG cars.amazon.com Model, make, price players.uefa.com Name, country popartist.amazon.com Name teams.uefa.com Fifa-affiliation, founded, general-secretary, president, press-officer, uefa-affiliation ausopen.com Birthdate, birthplace, country, height, money, name, weight ebay.com Price, bids, location majorleaguebaseball.com Name, position, team netflix.com Title, director, length, year rpmfind.net Name, description, operative-system RISE bigbook.com Name, city, phone, street iaf.net Name, email, organisation, service-provider laweekly.com/restaurants Name, address, speciality okra.ucr.edu Name, email zagat.com Name, address, type Table 2 Subset of common errors. Error Mean Error: <> is not recognised! 0.16 ± 0.57 Error: <> missing ‘>’ for end of tag 0.41 ± 1.07 Error: discarding unexpected <> 1.50 ± 6.46 Error: missing quotemark for attribute value 0.01 ± 0.10 Warning: <> element not empty or not closed 24.31 ± 42.45 Warning: <> is not approved by W3C 2.70 ± 6.14 Warning: <> is not allowed after elements 0.03 ± 0.17 Warning: <> is not allowed in <> elements 13.71 ± 11.14 Warning: <> should not be nested 0.07 ± 0.46 Warning: <> unexpected or duplicate quote mark 3.65 ± 30.00 Warning: adjacent hyphens within comment 1.32 ± 2.29 Warning: discarding unexpected <> 3.33 ± 6.12 Warning: inserting implicit <> 1.23 ± 4.95 Warning: link is not allowed in <> elements 0.00 ± 0.02 Warning: meta is not allowed in <> elements 0.06 ± 0.45 Warning: missing <> before <> 3.21 ± 7.36 Warning: missing <> declaration 1.00 ± 0.00 Warning: missing <> 4.68 ± 8.02 Warning: plain text is not allowed in <> elements 0.74 ± 0.45 Warning: replacing element <> by <> 0.09 ± 0.29 Warning: replacing unexpected <> by <> 0.21 ± 1.01 H.A. Sleiman, R. Corchuelo / Knowledge-Based Systems 39 (2013) 109–123 117