2 Related work

Structural analysis of a document is the process of making the logical structure underlying the document explicit by means of some automated methods. As the structure within the document is extracted, it can be represented in the form of a structured document based on a schema. The main motivation behind this process is facilitating the use of the information contained in the documents since structured infor1)mation can be interpreted much more easily by computer applications. Based on this observation, there has been a great deal of studies for extracting the structural representation underlying documents written as flat texts.

The analysis of document structure and extraction of structural and semantic information in the documents is becoming increasingly important especially for Web documents due to the wide spread use of the World Wide Web. Web documents are usually encoded in HTML format (HTML 4.01 Specification 1999) and can contain rich structural information. However, since HTML is concerned with the presentation of content, it does not always correspond to the semantics of the data. As a result, Web documents are considered as ‘semi-structured’ documents (Chaudhuri Reference Chaudhuri2006). The practical applications of document analysis include the display of content on small-screen devices such as personal digital assistants (PDA), summarization of content, more intelligent retrieval of information, etc. Most of the studies that target analysis of HTML documents make use of the document object model (DOM) tree representation since it provides a global view of the document structure (Jensen, Madsen and Moller Reference Jensen, Madsen and Moller2011). DOM is a platform- and language-independent interface and allows programs to dynamically access and update the content, structure and style of documents. In the DOM paradigm, documents are represented as a hierarchy of nodes, which is referred to as the DOM tree (Document Object Model 2012).

One approach used for document structural analysis is considering it as a syntactic analysis problem (Mao et al. Reference Mao, Rosenfeld and Kanungo2003). In this approach, the order and containment relations between physical components (paragraphs, words, figures, etc.) and logical components (titles, authors, sections, etc.) of a document are represented in the form of an ordered tree. This is analogous to the analysis of a sentence which can be described as a tree with grammatical relationships among its words. In this respect, some syntactic analysis methods used in natural language processing are adapted to the document analysis problem.

In one of the studies, the transformation-based learning method that was applied previously to syntactic parsing is used for the conversion of HTML documents into extensible markup language (XML) format (Curran and Wong Reference Curran and Wong1999). The authors use a large number of transformation templates and an evaluation function that is specific to the error types in XML tagging. Although the structure of the system and the details of the system components were explained, no evaluation results were given. In another study, the logical structure of a document is modeled via a structural representation of patterns formed of entities in the document (Brugger, Zramdini and Ingold Reference Brugger, Zramdini and Ingold1997). The document structure is constructed in a hierarchical way where local tree node patterns are defined similar to n-grams. The originality of the work stems from using the n-gram concept to model nodes in a tree in addition to modeling sequential entities. Branavan, Deshpande and Barzilay (Reference Branavan, Deshpande and Barzilay2007) propose a method that automatically generates a table-of-contents structure for long documents such as books. They first segment a document hierarchically and then generate an informative title for each segment. A model is learnt using the incremental parsing approach of Collins and Roark (Reference Collins and Roark2004), which is also the approach we use for extracting hierarchical structures of documents in this work. In this approach, the parse tree is incrementally constructed by applying simple corrective updates to the parameters during training and beam search is incorporated to reduce the size of the exponential search space of possible parses.

Similar to approaching the problem of document structure analysis as a syntactic analysis problem, some works aim at modeling the document structure explicitly by grammar rules and parsing a given document with respect to the grammar built. In an early study that targets extracting logical structures of documents from their physical representations, a document given in image form is first converted into text form (Niyogi and Srihari Reference Niyogi and Srihari1995). The structure of documents is modeled by a set of context-free grammar rules formed for a specific domain. The documents are parsed according to the defined grammar and the hierarchical structures are obtained. In another study, it is argued that different types of document analysis tasks can be solved using discriminative grammar formalisms (Shilman, Liang and Viola Reference Shilman, Liang and Viola2005). In the case of document structure analysis, document layout is modeled by a grammar based on the assumption that a document is a sequence of pages where a page is formed of paragraphs, a paragraph is formed of lines, and so on. A grammar learning algorithm is trained on a set of training examples and the optimal parse for a given document is obtained using the learned model. The experiments on a small corpus showed about 85 per cent success rates (f-measure).

The grammar-based approaches used in document layout analysis have the advantages that the grammar rules are easy to interpret since they reflect the logical segmentation of documents into entities and there exist plenty of sound mechanisms for parsing. However, it is quite difficult to build a grammar in advance that can sufficiently represent the hierarchical relationships between entities in a document, except in very formal domains such as academic papers. This is especially the case for Web documents due to their cluttered structures and irregular forms (Gupta et al. Reference Gupta, Kaiser, Neistadt and Grimm2003). In addition to the actual content, Web documents include several entities such as advertisements, unrelated images, links scattered around the screen, and navigation menus, which makes modeling such pages with a grammar difficult. In grammar-based approaches, this problem is handled by identifying a domain (e.g. newspaper stories) and then building a grammar specific to that domain.

Some studies in the document analysis field approach the problem from a content extraction perspective rather than (or, in addition to) structural analysis. In one of these studies, Rahman, Alam and Hartono (Reference Rahman, Alam and Hartono2001) propose a rule-based approach that extracts the contents of a Web document and produces a summary to be used in PDA devices. The methodology used in the work follows the stages of analyzing the structure of a document, decomposing the document into zones, analyzing and summarizing each zone, and reordering the summary sentences based on their importance. Gupta, Kaiser and Stolfo (Reference Gupta, Kaiser and Stolfo2005) address the problem of domain dependency that degrades the performance in document analysis studies. They split the content extraction problem into two stages. First the genre of a Web page is determined using search engine snippets and then its content is grouped into related parts using a predefined setting for the identified genre. The major drawback of this strategy is that it requires deciding on a set of genres in advance and building a schema for each genre. In another study, the authors worked on eliminating the non-content in the documents (i.e. cluttered parts around the body of a document that distract the user from actual content) rather than identifying the important content directly (Gupta et al. Reference Gupta, Kaiser, Neistadt and Grimm2003). For this purpose, they use a set of filters and the document that remains after the non-content parts are eliminated is given as the output. Although the cluttered parts in the documents are removed by this approach, it fails in distinguishing important and unimportant parts in a document and outputs all the remaining content.

There are some works that limit document analysis to the extraction of important entities from documents. Xue et al. (Reference Xue, Hu, Xin, Song, Shi, Cao, Lin and Li2007) use support vector machines and conditional random fields (CRF) to extract the main title from the content of a Web document using DOM tree and vision-based features. The authors address HTML documents and form a specification of a title in these documents based on formatting features. The method was evaluated on a document retrieval setting and was compared with a simple baseline method. In their work, Le and Thoma (Reference Le and Thoma2003) considered the problem of assigning predefined labels (title, author names, affiliation, and abstract) to scientific documents. After the DOM tree representation of a document is built, the unnecessary nodes in the tree are eliminated, a set of string patterns are generated, and the document parts are labelled using a pattern matching algorithm. The patterns are formed using both position-based and content-based features. As the research is restricted to formal documents and clearly-written parts in these documents, success rates up to 95 per cent were achieved. A work that uses CRF for document analysis was given by Pinto et al. (Reference Pinto, McCallum, Wei and Croft2003). In this work, the problem is restricted to the extraction of tables in the documents. The authors identified a rich set of features and compared the performance of the model with the hidden Markov model (HMM) and the maximum entropy (MaxEnt) approach. The f-measure results obtained were about 65 per cent, 85 per cent and 93 per cent for HMM, MaxEnt and CRF, respectively.

These works have a limited scope in the sense that they focus on specific document entities and develop algorithms specialized for this purpose. They do not target identifying the relationships between elements in the documents. A work addresses a more general problem, which is the problem of finding the headings in a document together with the underlying hierarchy (Pembe and Güngör Reference Pembe and Güngör2009). The authors use a rule-based approach based on a number of heuristics and DOM tree processing. The proposed methodology was evaluated on a search engine setting and it was shown that the use of structural information in extracts output by search engines improves the effectiveness of the search.

Some researchers consider the document analysis problem as a semantical analysis problem and use clustering or machine learning techniques to identify related parts in documents. Liu, Wang and Wang (Reference Liu, Wang and Wang2006) aim at segmenting a Web page into a set of semantically related blocks based on the idea that text portions inside a particular segment usually share some common contents and presentation styles. They propose a vision-based page segmentation algorithm that first converts an HTML DOM tree into a semantic tree and then applies a Naive Bayes classifier using a set of content and spatial features. In another work, it is assumed that subtrees that have a similar structure in the DOM tree representation of a document belong to the same group (cluster) (Mukherjee et al. Reference Mukherjee, Yang, Tan and Ramakrishnan2003). This is referred to as a schema, which is defined as representing the concepts and relationships among the document parts in a hierarchical fashion. The authors propose a partitioning algorithm to divide a given Web page into a set of schemas. Kao, Ho and Chen (Reference Kao, Ho and Chen2004) split a Web document into information blocks of different types by means of a form of clustering. The work basically targets more efficient display on PDAs and proposes that hierarchical search on such devices is easier than recursive search. The authors use a three step process based on the information space tree concept and obtain about 80–90 per cent f-measure scores on different datasets. Yang and Zhang (Reference Yang and Zhang2001) view the content of a Web document as formed of objects and employ a classification algorithm to identify different types of objects. They base the classification on a number of similarity measures used for objects of the same type. Given a document, the parts that have similar contents are extracted using a pattern detection algorithm. Based on the identified objects, document hierarchy is built recursively. The approach basically focuses on the visual appearance of a Web page by means of the so-called content objects and does not take into account the actual content within these objects. Feng, Haffner and Gilbert (Reference Feng, Haffner and Gilbert2005) use two learning approaches in order to segment a given Web document into blocks and to identify the semantic categories of the blocks. They define 12 category types that occur frequently in Web pages and make use of different types of features such as visual clues and linguistic phrases. The work aims at obtaining a flat sequence of segments without considering the hierarchical structure in the document.

One of the practical applications of Web document analysis that has drawn attention of researchers is the display of content on small-screen devices such as PDAs. Some of the studies in the literature concentrate on this goal and develop algorithms tailored for this particular area. In a study, a browsing method, named as accordion summarization, for displaying the contents of Web pages on PDAs was proposed (Buyukkokten, Garcia-Molina and Paepcke Reference Buyukkokten, Garcia-Molina and Paepcke2001; Buyukkokten et al. Reference Buyukkokten, Kaljuvee, Garcia-Molina, Paepcke and Winograd2002). Three different summarization techniques are applied, which are page summarization, keyword-driven summarization and automated view transitions. In each, some heuristics are used related to the contents of the documents and a hierarchical summary is formed. Another work that targets similar devices extracts the hierarchy of a Web page by exploiting the observation that the variety of information content decreases as we move towards lower parts of the tree (Chen, Ma and Zhang Reference Chen, Ma and Zhang2003). A rule-based method is applied by using heuristics for different types of page elements (header, footer, separators, etc.) and the content is displayed using a page adaptation mechanism that splits the page to fit on the small screen of a device. Xiao et al. (Reference Xiao, Luo, Hong, Fu, Xie and Ma2009) attempt to partition the content of a Web page into a set of subpages, each of which fits on the screen. A tree formed of page blocks is built by taking into account some factors such as the size and number of blocks and semantic coherence between blocks. The internal nodes of the tree serve as index pages that allow access to the actual contents of the Web page.

The works on document analysis can be classified with respect to a number of criteria such as the aim of the analysis (extracting entities, a flat structure, or a hierarchical structure), the scope of the analysis (all entities, titles, tables, etc.), the approach used (rule-based, machine learning, clustering, grammar-based, etc.), being domain-independent or not, and the targeted environment (computer, PDA, mobile phone, etc.). The difference of the current work from previous studies lies in the methodology used and in expanding the coverage of those studies by building the structural representation of the whole document content. We attempt to obtain the hierarchical structures of documents using a two-step process by first identifying the headings that will aid in determining the structure and then forming a sectional hierarchy based on these headings and also the non-heading content. The work addresses the whole document content, is domain-independent, and employs a learning paradigm. In addition, it builds a summarization framework that makes use of the results of structural analysis and forms a structural summarization component that is useful in many application areas. In these respects, the current work can be regarded as proposing a new way for solving the document analysis problem. As will be shown in Section 6 and discussed in Section 7, the methods built in this work yield high success rates in document structure analysis and structural summarization and outperform the approaches used in similar works.

3 System architecture

The components of the system built in this work are shown in Figure 1. First, the documents collected from the Web are processed in order to obtain their DOM tree representations. In this work, we compiled the document collection using a set of TREC (Text Retrieval Conference 2010) queries by submitting each query to a search engine and retrieving the results output by the search engine (Section 6.1). The DOM tree representations were obtained using the Cobra HTML Renderer and Parser open source toolkit (Cobra: Java HTML Renderer and Parser 2010). Although the DOM tree of a document can be regarded as a form of hierarchical representation, it is too complicated and does not reveal the actual content of a Web page. This is due to the fact that DOM tree only aims at making the relationships between document entities determined by HTML tags explicit. However, as mentioned previously, these tags are used to get a desired visual effect and do not reflect the actual layout of a document. Thus it is necessary to process further the DOM tree to obtain the structure of the document.

Fig. 1.

System architecture.

In the methodology used, we accept a text unit as the basic element that is used by the learning algorithms. A text unit corresponds to a text fragment (e.g. sentence, paragraph, heading) that is assumed to be coherent in itself. In our preliminary experiments, we observed that dividing a document into such units instead of sentences yields more meaningful results. After the DOM tree of a document is built, the text units within the document are identified (Section 4) and the values of the features for each text unit are computed. The work makes use of a rich set of features formed of different types of features to encode both the properties of individual units and the relationships between consecutive units (Section 4.3).

The output of the feature extraction component which consists of the text units in the documents accompanied with feature values is fed into the heading extraction module (Section 4.1). In the training phase, the heading extraction module learns a model that discriminates headings and non-headings. In the test phase, given a document, this model is used and a binary classification is performed in order to identify the headings in the document. This process is followed by hierarchy extraction in which the hierarchical relationships between the heading units are determined and the hierarchical structure of the document is built using the heading and non-heading units (Section 4.2). As will be detailed later, an incremental approach is employed during hierarchy construction and a number of alternative variations of the main algorithm are tested in order to determine the best method (Section 4.4).

The last step in the system architecture is testing the usefulness of the methodology in a search engine setting. For this purpose, a given user query and hierarchical representations of documents are first subjected to simple linguistic preprocessing operations such as stemming, case folding, and stop words elimination. Then the documents are summarized by taking into account the query terms and structural summaries are obtained (Section 5). Finally, the performance of the summarization component is evaluated.

4 Structural processing of Web documents

In general, the structure of a document can be considered as a hierarchy where the document is formed of sections, each section has subsections, and so on, together with the corresponding headings and subheadings. The format of the documents used as input in the system built in this work is HTML, because it is still the most frequently used format on the Web. The output of structural processing is a tree representing the sectional hierarchy of a document where headings and subheadings are at the intermediate nodes and other text units are at the leaves. An example hierarchical structure is shown in Figure 2. The root contains a dummy unit covering the whole document. As can be seen, headings at different levels form a hierarchy together with the sentences under the headings.

Fig. 2.

Output of structural processing.

In the current system, a Web document is modeled as a sequence of text units based on their orders in the HTML source of the document. When we process the HTML code of a document in a top-down manner, we obtain a unique ordering of different types of elements (text, images, side bars, etc.) in the document. The analyses in later steps are based on this ordering of page contents. The modeling approach used here is analogous to sentence parsing where each sentence is modeled as a sequence of words. We define a text unit u_i in the document as a text fragment delimited by a newline character (i.e. paragraph delimiter) as illustrated by rectangles in Figure 3. Two machine learning models were developed: heading extraction model and hierarchy extraction model. The models are detailed in the following subsections together with the features used, learning and testing approaches, and implementation.

Fig. 3.

Part of an example HTML document with units identified.

4.2 Hierarchy extraction model

In hierarchy extraction, the problem of learning a mapping from a set of documents X to a set of possible sectional hierarchies Y is considered. This is analogous to syntactic parsing in which X corresponds to a set of sentences and Y to a set of possible parse trees (Collins and Roark Reference Collins and Roark2004). We formulate the problem as follows:

• • Training examples (x_i, y_i) ∈ X × Y for i = 1, . . ., t, where t is the size of the training set

• • A function GEN(x) which enumerates a set of possible outputs for an input x

• • A representation Φ(x_i, y_i) mapping each (x_i, y_i) to a feature vector

• • A parameter vector α

The training set includes (x_i, y_i) pairs where x_i is a Web document and y_i is the gold standard tree corresponding to the document sectional hierarchy. The learning task is to estimate the parameter vector α using the training examples as evidence. As the parameter vector is obtained, Eqn. (1) is used to choose the most likely hierarchical structure (y _max) for a given test document x. That is, at each step of the incremental learning process (Section 4.4), a number of alternative partial trees are evaluated with respect to the parameter vector and the feature set, and the one which maximizes Eqn. (1) is identified as the correct hierarchy.

(1) \begin{equation} y_{\max} = \arg \mathop {\max}\limits _{y \in {\it GEN}(x)} \Phi (x,y) \cdot \alpha \end{equation}

In general, the main difficulty in developing a tree-based (document trees in document processing, parse trees in syntactic parsing, etc.) learning approach is the exponential search space encountered during the process. That is, the set of candidate outputs for an input x, enumerated by GEN(x), can grow exponentially with the size of x, making the brute force enumeration of the set members intractable. One solution to this problem is to use a heuristic method, such as beam search, to reduce the search space. This approach has previously been successfully applied to other tasks in the literature, including syntactic parsing and generating table-of-contents for general documents (Collins and Roark Reference Collins and Roark2004; Branavan et al. Reference Branavan, Deshpande and Barzilay2007). In this method, the output tree is incrementally built by making a sequence of locally optimal choices in order to approximate a globally optimal solution, which is also the approach we take.

4.3 Features

We define different types of features corresponding to different levels in a document. The first type consists of a set of features related to the properties of the smallest item (i.e. text unit) in a document. This is followed by features based on the context of a unit that indicate the relationships between neighboring units. Finally, global features are defined considering the document as a whole.

4.3.1 Unit features

A text unit is considered as the smallest item in the system and is associated with a set of features. Text units can be automatically detected using certain tags that specify paragraphs in the HTML format, such as <br> and <p>. A text unit may correspond either to a single node in the HTML DOM tree or to more than one node if different parts of the unit are enclosed within different HTML tags. For instance, a paragraph (text unit) may contain one or more parts written in bold (enclosed inside <b> tags). In this case, the paragraph will be divided into parts as the boldness changes and will be represented as a sequence of nodes in the DOM tree.

In most of the Web documents, cascading style sheets (CSS) rules are used to define the presentation of document contents. We use Cobra HTML Renderer and Parser which supports parsing of the DOM tree and the CSS information. During parsing, the parts of a text unit divided into several nodes in the DOM tree are combined to form a single unit. After the parsing process, text units in the document are associated with features. The unit features include formatting features, DOM tree features, content features, and other types of features.

Formatting features are based on HTML tags and attributes used for formatting the text units, such as font size, boldness, color, etc. (Table 1). The formatting information is obtained after CSS information is incorporated.

Table 1.

Formatting features for a text unit

DOM tree features are related to the DOM tree parse of the document. Although the DOM tree is concerned with the presentation of the contents, it can also contain valuable information about the structural organization of the document. In HTML documents, the organization is achieved by using nested tables (<table>) and divisions (<div>). The DOM path and the DOM address (Feng et al. Reference Feng, Haffner and Gilbert2005) of a unit are used as features in this work. The DOM path of a unit refers to the sequence of node labels from the root node (<html>) to the node that is the parent of the leaf node that corresponds to the unit (e.g. ‘html.body.div.table.tr.td.b’). The DOM address of a unit is similar in the sense that it also represents the path from the root to the unit leaf, but the node labels are replaced with numbers. The children of each node in the tree are numbered consecutively starting from zero. Then the DOM address is formed as a sequence of the numbers on the path (e.g. ‘0.1.0.2.1.3.0’). Another feature used is the position of a text unit within the innermost table or division according to the DOM tree. This information is especially useful in heading extraction because headings are often found at the first position within a table or division.

Content features are related to the textual content of a unit, such as features that specify whether a unit contains certain cue words or phrases (‘back to top’, ‘login’, etc.). Other content related features include the number of characters in the text unit (e.g. 0–50, 51–100, > 100), the number of sentences the text unit contains, and the punctuation mark at the end of the text unit (if any). Such features are especially important in heading extraction; usually, headings are limited in length, consist of a single sentence, and contain no punctuation marks at the end.

Several other features are defined for a text unit. Some of these are related to the visual position of the unit in a rendered Web document (i.e., as it is displayed in a browser). For this purpose, the x and y coordinates of the text units are computed using the Cobra HTML Renderer and Parser. Other features include a feature designating whether a unit is the document root or not and a feature indicating the use of a horizontal line (<hr > tag in HTML) to separate content.

4.3.2 Contextual features

We define a contextual feature of a unit as a feature that encodes a relationship (in terms of unit features) between this unit and another unit in its context. For heading extraction, we limit the context of a unit to the two preceding and the two succeeding units in the document. Given a unit u_i, we use the notation F_ij (j = i-2, i-1, i + 1, i + 2) to denote the set of features related to u_i and u_j. For hierarchy extraction, the document tree built during the incremental learning process (see Section 4.4) is considered: the context of a unit is the set of all units in the tree that the unit can attach to. For a unit u, u_ij denotes the unit i levels above it and j units to its left in the partial tree constructed so far. For instance, given a unit u, u ₁₀ represents its parent unit, u ₀₁ its preceding sibling unit, and u ₂₀ its grandparent unit.

Contextual features utilize the difference and distance between two units in the same context. This can provide useful information in determining the headings and the sectional hierarchy in a document. Intuitively, a heading unit (i.e. parent unit) is more emphasized than the underlying text units or subheadings in terms of formatting. Similarly, text units under the same heading, i.e. sibling units, generally have similar formatting features.

Contextual features of two units are defined in terms of the formatting, DOM tree, and visual unit features. For a binary (boolean) or integer formatting feature, the corresponding contextual feature is the difference of the values of the units’ features. For instance, the contextual value of the h1 feature for two units u_i and u_j is u_i.h1- u_j.h1 (−1, 0 or 1). As another example, if u_i has a font size of 12 and u_j has a font size of 14, then the contextual font size feature will be -2.

We define a contextual DOM address feature for two units as the length of the path common to their DOM addresses starting from the root. The idea is that semantically related parts in a document show spatial locality in the DOM tree and have similar DOM addresses. This value is normalized by dividing it to the depth of the overall DOM tree for that document in order to smooth the depth differences between documents. We define contextual features related to the visual positions (x and y coordinates) of two units. The differences of x coordinates and y coordinates are considered as positive, negative, or zero. For instance, if the difference of the y coordinates between two units u_i and u_j is positive, this means that u_i comes below u_j in the visual display of the Web document; therefore, u_i cannot be a heading of u_j. The difference of the x and y coordinates can also be compared to a threshold value. As an example, if the visual y position difference between two consecutive units u_i and u_j is very large, then it is quite unlikely that u_j is a heading of u_i.

4.3.3 Global features

In addition to the features of a single unit and the contextual features, we also define global features by considering the document or the document sectional hierarchy as a whole. One such feature is the depth of the tree built so far during the learning process. These features are used in the hierarchy extraction stage.

4.4 Incremental learning approach

In document sectional hierarchy extraction, we use an incremental approach in the machine learning model. Figure 4 (units u₁-u₈) shows an example partial hierarchy for a Web document. (The unit u₉ and the dashed lines in the figure will be explained later.) The root node is a dummy node covering the whole document and each of the other nodes corresponds to a text unit in the document. The unit indices are arranged according to their order of appearance in the document. The solid lines in the figure indicate the dependency relations between the node pairs, i.e. the parent-child relationships (heading-underlying text or heading-subheading). These correspond to positive examples for the learning process. The negative examples (not shown in the figure) are the potential dependency relations which are not realized in the gold standard hierarchy.

Fig. 4.

Part of an example document tree (units u₁-u₈). The dashed lines indicate potential attachments of a unit u₉.

The main training algorithm is given in Figure 5. The input to the algorithm is the training set consisting of Web documents and corresponding gold standard hierarchies. For each document in the training set, the algorithm works on the units one by one starting from the first unit, and considers the attachment of a unit to its parent unit as a positive example and other potential attachments of the unit as negative examples. In extracting the negative examples, two constraints due to the document flow are applied. First, a unit cannot be attached to a unit coming after it in the document. Second, the connections in the tree cannot cross each other according to the projectivity rule, as in dependency parsing (Covington Reference Covington2001):

Fig. 5.

Training algorithm for hierarchy extraction.

Projectivity Rule: When searching for the parent of a unit u_i, consider only the previous unit u_{i − 1}, the parent of u_{i − 1}, the parent of the parent of u_{i − 1}, and so on until the root of the tree.

The projectivity rule states that if a unit u_{i − k} is the parent of u_i, then all the units between u_{i − k} and u_i must also be descendants of u_{i − k} in the hierarchy. The projectivity rule is implemented in lines 5–11 in Figure 5. For instance, in the example hierarchy, the connection u₄-u₆ violates the projectivity rule and hence does not count as a negative example.

In the test phase, the hierarchy for a previously unseen document is built incrementally using beam search. The testing algorithm (Figure 6) operates on each text unit sequentially based on the order in the document and maintains a set of partial solutions (PartialTrees). We adapt two operations similar to the previous work on incremental parsing (Collins and Roark Reference Collins and Roark2004; Branavan et al. Reference Branavan, Deshpande and Barzilay2007): ADV (advance) and FILTER.

Fig. 6.

Testing algorithm for hierarchy extraction.

Whenever a unit in the document is processed, its potential attachments to the existing set of partial trees are considered and the set is updated to include new partial trees (ADV operation). In Figure 4, potential attachments of a unit (u ₉) to an example partial tree are shown with dashed lines. During this process, the two constraints due to the document flow (order of units and projection principle) are also applied. To prevent the exponential growth of the set of partial trees, the FILTER operation is introduced. Using the output of the machine learning model, only the top k (beam width) highest scored partially generated trees are maintained at each step.

In this process, we also utilize the output of the heading extraction model. We apply a preprocessing step to each document that enforces two constraints. First, if a unit u_i is a heading, then the unit u_{i + 1} is automatically attached to u_i indicating that a heading must have at least one text unit (heading or non-heading) as the underlying content. Second, a unit is allowed to attach only to a heading unit, since a non-heading unit cannot serve as the parent of a text unit.

We also developed several variants of the main testing algorithm and analyzed their effects on the accuracy of sectional hierarchy extraction. The main algorithm uses a greedy approach in the sense that at each step only the partial trees with maximum scores are considered and the rest are eliminated. The disadvantage of this approach is that it is possible for a partial tree that gets high scores in most of the steps can be eliminated when it gets a low score in a step. In the modifications 1, 3 and 4 explained below, on the other hand, we include some knowledge from the previous steps in determining the best partial trees. The first variation takes into account the probabilities from the root to the current node in the partial trees. The third and fourth variations consider also the score values of a partial tree (in terms of ranks) in the previous steps. As another type of modification, the second variation analyzes the effect of using the hierarchy of headings in building the overall hierarchical structure. The details of the modifications are given below:

• • Modification 1: Instead of using the score obtained from the machine learning model directly, it is possible to convert it into a probability value using a sigmoid function as shown below (Platt Reference Platt, Smola, Bartlett, Scholkopf and Schuurmans1999; Mayfield et al. Reference Mayfield, McNamee, Piatko and Pearce2003):

(2) \begin{equation} f(x) = 1/(1 + \exp (Ax + B)) \end{equation}

In Eqn. (2), the function parameters A and B can be estimated using an iterative method (Platt Reference Platt, Smola, Bartlett, Scholkopf and Schuurmans1999). Alternatively, fixed parameters can be used (Mayfield et al. Reference Mayfield, McNamee, Piatko and Pearce2003), which is also the approach we take here with A = − 2 and B = 0. We calculate the probability of building a partial tree formed of n units by using the multiplication rule of probabilities as shown in Eqn. (3):

(3) \begin{equation} \prod \limits _{i = 1}^n {P(parent\,(u_i) = u_j)} \end{equation}

where parent(u_i) denotes the parent unit of u_i. We make the simplifying assumption that the attachments in the hierarchy are mutually independent of each other.

• • Modification 2: The testing algorithm is run in two levels. In the first level, the algorithm is applied to heading units only, i.e. heading units are connected in order to obtain the overall heading hierarchy. Note that taking into account only the heading units in this step does not cause any change to the algorithm in Figure 6. The tree obtained will be similar to a tree that would be obtained when all the units are considered, except that the leaf nodes (non-heading units) will be missing. In the second level, non-heading units are attached to the correct positions in the hierarchy using the output of the first level. This is accomplished by executing the same testing algorithm under the constraint that some of the units (headings) have already been connected (line 6 in Figure 6).

• • Modification 3: Instead of using the score output by the machine learning model directly, the partial trees are assigned integer ranks starting from ‘1’ which is given to the best scored tree. During the filtering process, the number of times a partial tree has obtained rank ‘1’ in previous steps is calculated to obtain its score. The trees with higher scores are favored. In this way, the success of a partial tree at each step is taken into account, rather than considering its success at the current step only.

• • Modification 4: The partial trees are given integer ranks similar to Modification 3. Then, the ranks at each step are summed to determine the score of a given partial tree. The trees with smaller scores are favored. The intuition behind this modification is the same in the sense that previous success rates of the partial trees are also considered.

5 Summary extraction

We used a structure-based and query-biased summarization method which was shown to be effective in Web search tasks (Pembe and Güngör Reference Pembe and Güngör2009). It is an extractive method consisting of two levels of scoring: sentence scoring and section scoring. In the first level, following a preprocessing stage (stemming, stop words elimination, etc.), sentences in a document are scored using statistical summarization methods by taking into account the output of the structural processing step. The methods used in this work are heading, location, term frequency, and query methods. The score of a sentence is calculated as the weighted sum of the normalized scores obtained in each method.

• • Heading method: Headings in a document include terms that give a general idea about the document contents and can be used for automatic summarization (Mani Reference Mani2001; Yang and Wang Reference Yang and Wang2008). Following this observation, using the output of the heading identification process, we give a heading score to sentences containing heading words based on the number of such words they contain. We consider all the headings in a similar manner without taking into account their levels in the hierarchy. We leave the process of differentiating between headings at different levels and using this information in the heading score as a future work.

• • Location method: Sentences located at certain positions in a document may convey important information (Mani Reference Mani2001). Based on the output of the hierarchy extraction step, we give a positive score to sentences located at the beginning of a section or subsection.

• • Term frequency method: Sentences that include terms that occur frequently in a document may be assumed to focus on the actual content of the document (Mani Reference Mani2001). There are several variations of the term frequency method in the summarization literature (Baeza-Yates and Ribeiro-Neto Reference Baeza-Yates and Ribeiro-Neto1999; White, Jose and Ruthven Reference White, Jose and Ruthven2003; Pembe and Güngör Reference Pembe and Güngör2009). In this work, we adapt a simple form and give a term frequency score to sentences based on the frequencies of the words they contain.

• • Query method: In the information retrieval context, using query-biased summaries is more effective than using generic summaries as produced by the systems in other domains (Tombros and Sanderson Reference Tombros and Sanderson1998; White et al. Reference White, Jose and Ruthven2003). For instance, a search engine should extract the fragments in a document that the user is interested in, rather than giving an overview of the document even if it reflects the content better. Based on this observation, in the current system, we give a query score to sentences containing query words based on the number of query terms they contain.

The second level of the process deals with the scoring of the sections and subsections that were identified during structural processing. The score of a section is calculated by summing the scores of the sentences it contains. Sections are represented with different number of sentences in the summary proportional to their scores. In a previous study, it has been shown that summaries longer than those of the traditional search engines improve the search experience of Web users (White et al. Reference White, Jose and Ruthven2003). Such summaries were shown to be more effective than the summaries of Google and AltaVista on a task-based evaluation. Based on this idea, we define a quota for the summary of a document (e.g. 25 sentences) and this quota is shared hierarchically among the sections according to their scores. In the output summaries, the hierarchical structure of the document is also preserved and displayed explicitly.

The structure-based summarization approach that we employ allows us to incorporate structural information about Web pages into the summarization process in two ways. The first one is using a modified form of the heading and location methods in determining the saliency of sentences by taking into account the extracted headings and hierarchies. The second one is treating each section and subsection separately, rather than considering the document as a whole, which enables more important sections to be represented more heavily in the summary. In this respect, the document structure is provided to have an important role during summarization and to be represented explicitly in the summary.

6 Experiments and results

6.1 Data collection

To evaluate the system, we need a sufficiently large and representative corpus of Web documents. Such a corpus can be compiled from the queries employed by users in real search tasks. Studies on users’ behavior related to query formation in search engines show that users usually prefer boolean queries consisting of only a few words (Ingwersen and Jarvelin Reference Ingwersen and Jarvelin2005; Markey Reference Markey2007). We followed the same strategy of using short queries in this work and compiled a set of TREC queries (from TREC 2004 Robust Track, topics 301–450) by taking into account the search interests of users in various domains (see Table 2). To collect the documents used in the experiments, each query was submitted to the Google search engine and the top 25 results (HTML documents) for each were taken. In this way, the corpus was formed of 20 TREC queries and a total of 500 documents. The corpus represents a diverse and realistic set of documents in terms of both structure and content due to the use of queries corresponding to different search interests and the use of preferred (top) results retrieved by the search engine. The documents in the corpus also show variations with respect to the document length and the markup tags used.

Table 2.

Queries used for building the corpus

The documents in the corpus contain an average number of 110.7 text units and 1,340 words. The headings in the documents were manually annotated using a specification guide (Figure 7) formed by the authors that shows the general guidelines for identification of headings. During the annotation process, we observed that the annotators can decide on whether a text unit is a heading or not more easily for units marked explicitly as headings using the heading tags. Document sectional hierarchies were also manually marked based on the identified headings and the document organization. We used two annotators for the tagging of the corpus. The documents were divided into two groups randomly and each document was tagged by one annotator. In order to observe the agreement between the annotators, we performed an additional test using a subset of the corpus (100 documents). Each document was marked by the two annotators. The agreement between the annotators was measured as 70 per cent. The annotation process resulted that a document contains 10.6 headings and has a hierarchy depth of 4.1 on the average.

Fig. 7.

Specification guide used for manual heading annotation.

6.2 Structural processing experiments

Following the proposed two-level approach, the structural processing phase was evaluated in two steps: heading extraction and hierarchy extraction. The outputs of the methods were compared with the gold standard headings and document hierarchies determined manually for each document. The machine learning experiments were performed using five-fold cross-validation.

We used the rule-based approach developed by Pembe and Güngör (Reference Pembe and Güngör2009) as a baseline. Using the heading tags in HTML or the DOM tree structure does not give rise to a proper comparison and cannot serve as a baseline, since they result in low success rates. As mentioned before, the heading tags in the HTML source of a document may not correspond to the headings in the document. The DOM tree structure, although it gives information about the layout in a document, does not represent the actual hierarchy (headings and sections) of the document. The DOM tree presents a complex view of the document and includes many irrelevant nodes. In addition, only the leaf nodes contain textual data in the DOM tree, whereas all the nodes in the trees built in the current system are formed of textual content.

In order to evaluate the accuracy of heading extraction, we adapted the recall, precision, and f-measure metrics that are widely used in information retrieval (Baeza-Yates and Ribeiro-Neto Reference Baeza-Yates and Ribeiro-Neto1999). For each document, four different values are computed: TP (true positive – the number of heading units identified correctly), FP (false positive – the number of non-heading units identified as heading), FN (false negative – the number of heading units identified as non-heading), and TN (true negative – the number of non-heading units identified correctly). Based on these values, we calculated the recall (R), precision (P), and f-measure (F) results for the heading extraction experiment as shown in Eqn. (4):

(4) \begin{equation} R \equiv \frac{{\it TP}}{{\it TP} + {\it FN}}\quad P \equiv \frac{{\it TP}}{{\it TP} + {\it FP}}\quad F \equiv \frac{{2 \times P \times R}}{{P + R}} \end{equation}

The accuracy of hierarchy extraction is determined by exploiting the structure in the output trees. We focus on the parent-child relationships in the trees since they correspond to the heading-subheading and heading-underlying text relationships. We define the accuracy for a document as the ratio of the number of correctly identified parent-child relationships (as compared with the gold standard) to the total number of parent-child relationships. Formally, given a manually identified hierarchy and an automatically extracted hierarchy for a document i, if there exists an edge between a node pair (p,c) in both of the hierarchies, we say e(p,c) = 1; otherwise, e(p,c) = 0. Given the set of manually identified parent-child node pairs PC_i for document i, the hierarchy accuracy is computed as shown in Eqn. (5). Note that we do not use the precision and recall metrics in addition to the accuracy metric in hierarchy evaluation, since precision and recall yield the same results as accuracy in this problem.

(5) \begin{equation} Accuracy_i \equiv \frac{{\sum \nolimits _{\left({p,c} \right) \in PC_i} {e(p,c)}}}{{\left| {PC_i} \right|}} \end{equation}

6.2.1 Heading extraction

We used the classification model explained in Section 4 to classify the text units as heading or non-heading. Intuitively the idea is that heading and non-heading units can be determined by considering their features relative to the units in their context. For instance, a heading unit is usually more emphasized than the immediately following unit. We defined five feature sets using different combinations of features as shown in Table 3. F_i denotes the features of the current unit; F_{i (i + 1)} and F_{i (i + 2)} denote the contextual features related to the current unit and, respectively, the succeeding unit and the unit following the succeeding unit; and F_{i (i − 1)} and F_{i (i − 2)} denote the contextual features related to the current unit and, respectively, the preceding unit and the unit before the preceding unit.

Table 3.

Feature sets used in heading extraction

We evaluated the performance of heading extraction using SVM and perceptron with different feature sets. In the heading extraction task, the number of negative examples (non-heading text units) is much larger than the number of positive examples (heading units), resulting in relatively low recall rates. In the literature, there exist several approaches for dealing with such unbalanced distributions, including oversampling or undersampling the classes (by random resampling, directed resampling, or adding new samples), adjusting the costs of the classes, recognition-based learning, or using modified forms of learning algorithms (Chawla Reference Chawla, Maimon and Rokach2005; Weiss, McCarthy and Zabar Reference Weiss, McCarthy and Zabar2007; Ganganwar Reference Ganganwar2012). In this work, we adopted the method of using different costs for the positive and negative classes. In the case of SVM, we experimented with different cost factors to adjust the cost of training errors on positive examples (false positives) versus the cost of errors on negative examples (false negatives). In the experiments presented in this section, a cost factor of two was used as it yields the best performances. We also experimented with different kernel types, which are the linear, polynomial and RBF kernels. In polynomial kernel, we used d = 2 as the degree of the polynomial which yielded more accurate results in the tests.

Table 4 shows the recall, precision and f-measure results for heading extraction. The best results in each method with respect to the f-measure are displayed in bold. The best results were obtained using SVM with polynomial and RBF kernels. It seems that as more features are included the accuracies improve in both of the learning algorithms. In this respect, Φ₄ and Φ₅ yield the highest f-measure values. The effect of using different feature sets is less obvious for linear SVM. However, especially for SVM with RBF kernel and perceptron, incorporating more contextual information in the model generally improves the f-measure rates. The results also show that machine learning approaches provide significant increase in the accuracy compared to the rule-based approach. The improvements are more clear with the use of a nonlinear technique (i.e. polynomial or RBF kernel) in SVM. ANOVA tests verify that the results are significant with p < 0.05 for recall, p < 0.0001 for precision, and p < 0.0001 for f-measure.

Table 4.

Performance results for heading extraction

To understand the effect of different types of features on heading extraction, we also performed experiments using the unit features and the contextual features separately. We used SVM with polynomial kernel as it shows successful behavior in heading extraction. The last part of the table shows the results for the unit features F_i, and the contextual features F_{i (i + 1)}, F_{i (i + 2)}, F_{i (i − 1)} and F_{i (i − 2)}. We see that when only the unit features are used or only a limited amount of context is taken into account, the success rates drop significantly. This indicates that, while deciding on whether a unit is a heading or not, both features about that unit and features that encode its relations with its context should be considered. We also notice that the context following a unit is much more important than the previous context. This observation is in accordance with the results obtained in other natural language processing tasks (Indurkhya and Damerau Reference Indurkhya and Damerau2010).

6.2.2 Hierarchy extraction

We evaluated the tree-based learning approach used for the identification of sectional hierarchies in documents. The initial experiments showed that unit features are not effective in hierarchy extraction since they encode only absolute values related to a single unit (e.g. font size of a text unit). Instead, contextual features which show the relationships between pairs of units (e.g. font size difference between two units) should be used. This observation is in parallel with the nature of the hierarchy extraction task that aims to determine the correct parent-child unit pairs in the documents. Hence, we employed only the contextual features in the hierarchy extraction models.

Following the notation given in Section 4.3.2, we name the contextual features of a unit u as F₁₀ (features related to u and its candidate parent unit), F₀₁ and F₀₂ (features related to u and its two candidate sibling units that are on the left in the partial tree), and F₂₀ (features related to u and its candidate grandparent unit). We defined four feature sets using different combinations of features as shown in Table 5.

Table 5.

Feature sets used in hierarchy extraction

The initial experiments also showed that the use of heading information improves the accuracy of hierarchy extraction. Thus, the output of the heading extraction step was also utilized in the hierarchy identification step (line 2 in Figure 6). The headings obtained with the polynomial SVM and the feature set Φ₅ (all features) were used since it was one of the best models in heading extraction.

The accuracies obtained in the hierarchy extraction experiments are given in Table 6 for different feature combinations and a beam width of 100. The results show that the SVM-based approach performs significantly better than the perceptron-based approach for high feature numbers. The nonlinear SVM models (polynomial and RBF kernels) yield more successful results than the linear kernel. Surprisingly, the performance of the perceptron algorithm, which is a linear approach, decreases as more contextual features are included. The best accuracies were obtained when the contextual differences with only the parent unit were considered. The analysis of the success rates with respect to the feature sets shows that each algorithm shows a similar behavior with Γ₂, Γ₃ and Γ₄. This indicates that the information provided by non-adjacent units (grandparents and distant siblings) does not contribute much in identifying the correct hierarchical position of a unit. The rule-based approach used in Pembe and Güngör (Reference Pembe and Güngör2009) resulted in about 61 per cent accuracy for hierarchy extraction. Considering this as a baseline, we see that the machine learning approach (nonlinear SVM models with increasing number of contextual features) outperforms the rule-based approach significantly.

Table 6.

Accuracies of SVM and perceptron in hierarchy extraction

In order to analyze the effect of the beam width on the incremental learning paradigm, we repeated the experiments with varying beam width factors. Table 7 shows the results for SVM polynomial and RBF kernels for beam widths ranging from 1 to 100. As can be seen, the beam width does not have a significant effect on the accuracies. This result indicates that it is sufficient to store only a few partial trees at each iteration, highly reducing the time and space complexities. The incremental learning approach allows us to solve the problem in polynomial time, as opposed to an exponential time approach that considers all possible tree structures that can be formed from the text units in a document. Similarly, with regard to the space requirements, we need to store only a number of trees that is dependant on the beam width during processing, rather than storing all possible partial trees.

Table 7.

Effect of different beam widths in hierarchy extraction

We also analyzed the success rates of the models explained in Section 4.4 and compared with the main model. Table 8 shows the results of the main model (M₀) and its variations (M₁ to M₄) for the feature set Γ₄ and a beam width of 100. It seems that all the models except M₂ where hierarchy extraction is formed of two consecutive steps show similar behavior. First extracting the hierarchy of the headings and then placing the non-headings into this hierarchy does not work. The reason is that at each of these independent steps the algorithm cannot make use of the information used in the other step. For instance, while determining the correct hierarchical location of a heading, in addition to the locations of other headings in the hierarchy, the properties (features) of the non-headings may also be important. The other variations of the main model have similar performance which indicates that using scores produced by the machine learning component or converting them into probabilities or ranks does not have a significant impact on the success rates.

Table 8.

Accuracies of alternative methods in hierarchy extraction

Considering heading identification as a preprocessing step for hierarchy extraction, we measured the performance loss in hierarchy extraction that results from this preprocessing step. For this purpose, we compared the results of hierarchy extraction that is based on automatically identified headings (as discussed above) and manually identified (gold standard) headings. Table 9 shows the results for the feature set Γ₄ and a beam width of 100 for both rule-based and machine learning models. As can be expected, using gold standard headings causes a significant improvement on the success rates. Given the heading structure of a document, it is possible to extract the hierarchical structure with about 80 per cent performance using learning algorithms. On the other hand, when the headings are also extracted by the algorithm, the success rate drops significantly. However, it should be noted that the latter case is a fully automatic and more realistic approach. Given an input document, the document hierarchy (heading and non-heading hierarchies) is completely extracted. The methods introduced show that this can be done with nearly 70 per cent success rates.

Table 9.

Manual versus automatic heading identification in hierarchy extraction

6.3 Summarization experiments

We conducted a task-based evaluation of the system where the task is Web search. The document sectional hierarchies were fed into the summarization module explained in Section 5. The summaries output by the summarization system were evaluated in terms of their usefulness in a search engine. Five types of summaries were used in the experiments:

• • Unstructured1, Unstructured2 – Query-biased summaries without the use of structural information.

• • Structured1, Structured2 – Structure-preserving and query-biased summaries created by the system.

• • Google – Query-biased extracts provided by Google.

In the models Unstructured2, Structured1, and Structured2, the parts in the documents that cause a cluttered view (navigation menus, links, etc.) were identified using some heuristics and eliminated. In Unstructured1, such document parts were kept in the documents. Structured1 is based on the output of the structural processing step, whereas Structured2 is based on the manually identified document structure. All the summaries in these models are long summaries with similar sizes (about 25 sentences) to make them comparable with each other. The model referred to as Google corresponds to the extracts (2–3 lines summaries) displayed by the search engine Google as a result of a user query. Since the outputs of Google and the proposed models have different sizes, we cannot make a direct comparison between the model Google and the other four models. However, we include Google in this evaluation in order to compare the results obtained in this work with those of a state-of-the-art search engine.

The structured summaries are displayed in a hierarchical way in accordance with the sectional hierarchy. The headings and subheadings are shown in bold. The context of the text fragments selected as part of the summary is provided within this structure. In this way, the users are expected to judge the relevance of the search results better. An example summary output of the system (Structured1 model) for the query Amazon rain forest is given in Figure 8.

Fig. 8.

An example summary output of the proposed system.

The queries used in the evaluation (see Table 2) cover different types of information needs of users (Ingwersen and Jarvelin Reference Ingwersen and Jarvelin2005): search for a number of items (12 queries), decision search (2 queries), and background search (6 queries). A repeated measures design was used with four subjects. The summaries were evaluated based on the relevance judgment paradigm instead of relying on a gold standard (Mani et al. Reference Mani, Klein, House, Hirschman, Firmin and Sundheim2002). As the success criterion, we used the relevance prediction measure that was shown to yield more reliable results than manual metrics for summary evaluation (Hobson et al. Reference Hobson, Dorr, Monz and Schwartz2007). Human subjects were asked to determine the relevance of original documents with respect to the given query (either relevant or not) using the summaries. That is, a subject's judgment on a summary is compared with his or her own judgment on the original document. If the subject marks both the document and the summary as relevant or irrelevant, the summary is deemed as a successful summary. In this way, the effect of differences in human subjects is reduced. The summaries and documents were presented in random order in order to reduce carry-over effects and an original document was not displayed until all the summaries of that document were displayed. In addition, we included a user poll during evaluation to rate the helpfulness of each summary. For this purpose, a 5-point Likert scale was used with 1 as not helpful and 5 as very helpful (Tombros and Sanderson Reference Tombros and Sanderson1998; White et al. Reference White, Jose and Ruthven2003).

For each summarization model, four different metrics were calculated by comparing the relevance judgments of the users for the summaries and the original documents: TP (true positive), FP (false positive), FN (false negative), and TN (true negative). Using these values, the recall (R), precision (P), and f-measure (F) results were obtained (Eqn. (4)). In addition, accuracy (A), false negative rate (FNR) and false positive rate (FPR), which correspond to, respectively, the number of useful summaries over the number of all summaries, the number of summaries that correspond to documents relevant to the query but marked as irrelevant over the number of all relevant summaries, and the number of summaries that correspond to documents that are not relevant to the query but marked as relevant over the number of all irrelevant summaries were computed as shown in Eqn. (6):

(6) \begin{equation} A \equiv \frac{{\it TP} + {\it TN}}{{\it TP} + {\it TN} + {\it FP} + {\it FN}}\quad {\it FNR} \equiv \frac{{\it FN}}{{\it FN} + {\it TP}}\quad {\it FPR} \equiv \frac{{\it FP}}{{\it FP} + {\it TN}} \end{equation}

A total of 400 relevance judgments were obtained for each summarization method. The results are shown in Table 10. We used the most successful hierarchy extraction model (model M₄, SVM with polynomial kernel, feature set Γ₄) for Structured1. The results show that structured summaries are superior to unstructured summaries in terms of accuracy, precision, recall and f-measure. Also, they significantly reduce the false negative rate (the number of search results missed by the user) and the false positive rate (the time spent with irrelevant items). When compared to the model Google, we see that the long outputs of the unstructured and structured models enable the users to determine the relevancy of search results better than the extracts produced by Google. The repeated measures ANOVA test verifies that the results (structured models over unstructured models and unstructured models over Google) are significant with p < 0.05 for both accuracy and f-measure. Table 11 shows the average time for deciding the relevancy of a summary/document, the average size of a summary/document, and the average user ratings. The last row of the table corresponds to the original document for comparison. The table shows that the models based on (structured or unstructured) summaries have acceptable judgment times despite the summary sizes much longer than search engine snippets. Also, we observe that structured summaries have quite high user ratings compared to unstructured summaries and search engine extracts.

Table 10.

Results of the summarization experiment

Table 11.

Average judgment times, summary/document sizes and ratings

It is worth noting that we use the model Google in the experiments in order to compare the approach proposed in this work (long and structured summaries) with the approach used by traditional search engines. We do not aim at making a direct comparison between the outputs, which would result in an unfair comparison due to the difference in the size of the content displayed to the user. The use of a search engine in the experiments shows us useful information in two dimensions. First, we observe that a model that displays structured and richer content to the users increases the relevancy of the results significantly and thus seems to be more helpful than the current search engine models. Second, we see that the users can judge the relevancy of the results in an acceptable time although they are provided with much more content. In these respects, we conclude that the summaries produced by the system built in this work direct the users more effectively at a cost of a small increase in response time.