Method and apparatus for structuring documents based on layout, content and collection

[0001] The following relates to the information storage and processing arts. It finds application in conjunction with electronic document format conversion and in particular with cataloging of legacy documents in a marked-up format such as extensible markup language (XML), standard generalized markup language (SGML), hypertext markup language (HTML), or the like, and will be described with particular reference thereto. However, it is to be appreciated that the following is amenable to other like applications.

[0002] More than ever, documents are now central in many activities. Knowledge is stored in documents and knowledgeable exchange is performed by circulating those documents. In this context, the recent evolution toward “structured documents” (especially around the W3C XML language format) as an effort to endow documents with new properties will continue to ease the automatic processing of the documents.

[0003] Legacy document conversion relates to converting unstructured documents existing in formats such as Adobe® portable document format (PDF), various text formats, various word processing formats, and the like into structured documents employing a markup language such as XML, SGML, HTML, and the like. In structured documents, content is organized into delineated sections such as document pages with suitable headers/footers and so forth. Alternatively, other kinds of segmentable text blocks can be identified. Such organization typically is implemented using markup tags. In some structured document formats such as XML, a document type definition (DTD) or similar document portion provides overall information about the document, such as an identification of the sections, and facilitates complex document structures such as nested sections.

[0004] There is thus interest in converting unstructured documents to a structured format when such structure can facilitate storage and access of this document as a “legacy document”. The particular motivations for converting documents are diverse, typically including intent to reuse or repurpose parts of the documents, desire for document uniformity across a database of information store, facilitating document searches, and so forth. Technical manuals, user manuals and other proprietary reference documents are common candidates for such legacy conversions.

[0005] A particular problematic issue that arises during the conversion process is the rebuilding or preserving of structural information. The output structure can be very different from the input structure and depending on what one wants to do with a document, a different structure may be needed. For example, a layout-oriented structure allows publishing a document on different media but would not very much help semantic search or automatic summarization, and page segmentation is often discarded in a logical representation, where logical units are elements such as chapters and sections (pages are usually considered as a physical element and do not appear).

[0006] The “document understanding” or “document analysis” research field precisely aims at analyzing a presentation-oriented document representations to build some more abstract document structures. It is a very heterogeneous field since different disciplines, such as image processing (OCR, document page layout analysis) and Natural Language Processing aim at analyzing documents. Each of these disciplines has its particular view point and vocabulary and there is not yet anything like a shared understanding of what “presentation-oriented”, “logical” or “content-oriented” structures might be. Nevertheless, there is a shared working hypothesis about their interdependency. (Marco Aiello, Christof Monz, Leon Todoran, and Marcel Worring, Document understanding for a broad class of documents. International Journal of Document Analysis and Recognition, 5:1-16, 2002. Richard Power, Donia Scott, and Nadget Bouayad-Aga. Document Structure. Computational Linguistics, 29(2):211-260, 2003.)

[0007] Thus there is a need for transforming a document (more precisely, documents comprising a homogeneous collection) with a layout-oriented structure into a document with a more abstract generic structure hereinafter identified as a “logical structure”. The logical structure can then be used as an intermediary step toward a content-oriented structure, more specific to a particular document or document collection. Such a system would be particularly advantageous if the “presentation-oriented”, “logical” and “content-oriented” structures could be related, i.e., by using both knowledge of the layout and knowledge of the content to reach the desirably structured document. Additionally, it would also be advantageous if information related to the document could be computed at the collection level.

[0008] For purposes of this application, “layout” is intended to include the physical presentation of a document including segmenting constructs such as chapters, sections, pages, tables and appendices. By “content”, it is intended to comprise the textual material itself within the document. By “collection”, it is intended to mean a related or homogeneous associated set of documents, e.g., a collection of technical manuals relating to a particular product line.

[0009] Copending, commonly assigned applications comprise a Method and Apparatus for Detecting a Table of Contents and Reference Determination (Xerox ID 200040274-US-NP, Ser. No. ______); Method and Apparatus for Detecting Pagination Constructs Including A Header and A Footer In Legacy Documents (Xerox ID 200040273-US-NP, Ser. No. ______); and Systems and Methods for Converting Legacy and Projecting Documents Into Extended Markup Language Format, (Ser. No. 10/756,313, filed Jan. 14, 2004), which are herein incorporated by reference.

[0010] The following provides improved apparatuses and methods that overcome the above-mentioned disadvantages and others to provide structuring documents based on their content, layout and collection.

[0011] The systems and methods according to this invention convert legacy and proprietary documents in a first layout-oriented structural format into an extended markup language format having a more abstract generic structure, i.e., “logical structure”. In the exemplary embodiments, the document is preferably part of a homogeneous collection. The conversion involves transforming the layout-oriented structure into ordered trees of a model wherein the tree content elements are organized by hierarchical dependency in accordance with predetermined categories representative of the document content elements in a logical structure.

[0012] The process structure comprises selective structuring processes including fragmenting the document from its initial layout structure into a plurality of document content elements in accordance with a predetermined set of document attributes identifiable from the initial document format. Selective sets of the fragmented content elements are clustered in accordance with similar attributes. The clustered sets are validated with reference to common textual properties in organizational content of documents within the homogeneous collection. The clustered sets are then categorized into predetermined categories comprising desired structured elements of the logical structure document format. The document format elements are then organized by hierarchal dependency from the predetermined categories wherein the organized document elements comprise the desired logical structure.

[0013] In various embodiments, the fragmenting comprises forming the document content elements of the logical structure as a text block, selectively including an optional head, a body and an optional tail. Language format tags are attached indicative of the text block.

[0014] The organizing also includes assigning hierarchical level attributes to the fragmented document elements. The fragment elements are assigned relative nested positions in accordance with the hierarchical level attributes whereby the nested relative positions form the desired ordered tree model.

[0015] Alternatively, the document content elements can be further enriched with additional attributes derived from initial layout structure format, such as capital letters, text, length of textual content, selected linguistic content and saliency.

[0016] An apparatus is disclosed to implement the aforementioned structuring processes.

[0017] FIG. 1 is flowchart block diagram of the processes for transforming an input document into a desired structure document; and

[0018] FIG. 2 is an organized hierarchical tree model of an excerpt of the logical structure format of a desired document format.

[0019] With reference to FIG. 1, the initial structure of the input document 10 reflects the document layout (e.g., W3C XSL-FO, Extended Stylesheet Language, cf. www.w3.org/Style/XSL). The initial structure is an XML vocabulary for specifying formatting semantics, as is commonly known in the art. The desired converted logical structure of the structured document 30 will reflect a more abstract structure organized in accordance with the input document layout content and collection for enhanced ease of access and storage in a legacy document collection (e.g., an XML DTD).

[0020] A representation of the generic logical structure as intended for the structured document is as follows:

	TABLE 1
	<! ELEMENT	Block	(Head?, Body, Tail?)>
	<! ELEMENT	Head	(#PCDATA | BLOCK)>
	<! ELEMENT	Tail	(#PCDATA | BLOCK)>
	<! ELEMENT	Body	(#PCDATA | BLOCK)>
	<! ATTRLIST	Head Level	#IDREF>
	<! ATTRLIST	Tail Level	#IDREF>
	<! ATTRLIST	Body Level	#IDREF>

[0021] Use of such a logical structure for the document structure analysis provides advantageous access and use of a structured document 30 in a legacy collection. Such a logical structure is generic enough for different kinds of document collections, and is applicable at all the hierarchical levels of the document (from high levels such as chapters, to low levels such as lists).

[0022] FIG. 2 is an example of a portion of a document so structured in a desired DTD comprising a tree model logical structure. For mere purposes of example, the subject processes will be explained with reference to documents of a collection 12 comprising travel guides.

[0023] With particular reference to FIG. 2, a logical portion of the document 10 is composed of an optional head 42, a body 44 and an optional tail (not shown). Each such element is recursive and contains either text or a block. The relative position of the block within the structured tree model can be defined by a level attribute associated as a format tag in order to identify the hierarchical position of the element. Normally, the heads 42 will correspond to titles of a document, chapters, sections, etc. For example, a book is composed of a head (everything from the beginning of the book to the beginning of the first chapter), a body (sequence of chapters), and a tail (everything from the end of the last chapter to the end of the book). Each head, body and tail can then be also structured as is shown in FIG. 2.

[0024] Continuing with the example of the travel guide of FIG. 2, if a certain chapter of the travel guide were concerned with personal travel items 50, then it may have a section on handling luggage 52 and the recommended travel wear (clothing, shoes) 54. The luggage itself can then be further organized into whether the luggage is all types 56 or travels with the traveler as checked or carry-on luggage 58, 60.

[0025] Accordingly, what is layout oriented as a mere descriptive textual paragraph suggesting helpful travel guidelines can be reformatted into a logical structure much more easily accessible by subject matter or attribute within a legacy document collection.

[0026] With continued references to the FIGURES, the objective of the processing for implementing the desired conversion comprises converting a layout document comprising a listing of content elements (a flat tree) into a deeper tree that reflects the logical structure of the document in which a tree model is compliant with a desired generic DTD.

[0027] In the subject embodiments, documents have been coded in an XSL-FO format so that the initial text block or element list is composed by fragmenting the document into a plurality of document content elements conventionally tagged as document blocks in XSL-FO. However, other input formats are just as applicable to the present process (HTML, PDF files converted into XML). The subject processes are thus applicable to any input document containing information about its layout that can be converted into XML. The following comprises an exemplary list of the attributes for a particular element provided by XSL-FO for encoding the layout information:

	TABLE 2
	<fo: block keep-with-next.within-column=”always”
	line-height=”12.5pt” margin-left=”0.0pt”
	margin-right=0.0pt” orphans=”2”
	space-after=”6.0pt”
	space-before=”0.0pt” text-align=”justify”
	text-indent=0.0pt”
	white-space-collapse+”false” widows=”2”>
	<fo: inline font-family=”Comic
	Sans MS, cursive”
	font-size-“11.0pt”
	text-decoration=”underline”>
	LUGGAGE
	</fo:inline>
	</fo:block>

[0028] In this example, the structuring process is generic because the semantics of the initial element and attribute names are not employed. It is not necessary to try to put a priori semantics in the layout attributes. For example, it is not necessary to consider that centered and bold elements are certainly titles. On the other hand, one of the more important fragmenting bases is saliency (i.e., if two contiguous elements do not share most of their attributes, then they likely belong to two different kinds of logical elements.) Such fragmenting by documenting attributes identifiable from the input document format facilitates distinguishing a head from its body (i.e., a section title from its body), whatever the layout attributes of the head are. The basic operation of the fragmenting thus comprises a comparison between the attribute sets of two elements (mainly for clustering similar elements as will be explained below). Such an approach which does not use attributes semantics explicitly allows the development of heuristics for structuring documents that apply to any selected collection of documents.

[0029] With particular reference FIG. 1, the conversion process gradually converts the initial flat structure of the input document into the target structure of the structured document, with the following structuring processes:

• • [0030] 1. Element enrichment 14 with new attributes.
  • [0031] 2. Element clustering 16 based on similarity between the attribute set of different elements.
  • [0032] 3. Cluster validation 18 using collection and content information.
  • [0033] 4. Cluster categorization 20 into the three logical categories (Head, Block, or Tail).
  • [0034] 5. Element structuring 22 by adding new logical levels of hierarchy into the document.

[0035] These steps are iteratively applied to the documents of the document collection 12 until the categorization processes 20 do not identify new hierarchical elements. The output of this algorithm is the structured document 30 collection compliant with the target DTD.

[0036] The details of the conversion process are as follows.

[0037] Any preprocessing extracts the XSL-FO elements labeled “block” (see Table 2 above) corresponding to the elements containing the textual parts of the document. The attributes of the “inline” elements of each block, are copied at the block level. Accordingly, the processes of FIG. 1 are employed only at the block level.

[0038] Enrichment 14 process involves selectively adding new characteristic properties for the textual elements of the input document 10. The elements can be preferably enriched with new attributes whose value is automatically computed. Such new attributes may selectively comprise a layout characteristic element that is not explicit in XSL-FO. In particular, attributes are added to text blocks whose PCDATA is written in capital letters only. Additionally, at least for documents written in English, the fact that each work in a PCDATA begins with a capital is also a useful characteristic. Another enriching attribute is the length (number of characters) of the PCDATA content of an element. In addition, results of linguistic content analysis can also be added as enriching attributes. Lastly, saliency can be computed for each element of the document.

[0039] The clustering 16 process comprises aggregating by attribute similarity the homogeneous elements of the fragmented document. Elements can be clustered using all the attributes provided by XSL-FO, and some of the new attributes added during the enrichment 14. Since the semantic of the attributes are known, selection of desired ones may be taken into account during the clustering. The resulting textual elements that are clustered during the clustering 16 will provide homogenous clusters corresponding to the desired target elements. Each cluster should contain elements belonging to the same possible category: head 42, body 44 and tail of the same level. The table below shows the clustering of the elements of the document logically structured in FIG. 2:

TABLE 3
Cluster	Elements
1	Luggage
	Clothing shoes
2	1/carry-on baggage
	2/checked baggage
3	The luggage you carried on . . .
	The luggage you checked . . .
4	PERSONAL ITEMS
5	all types of luggage

[0040] The clustering of document elements by attribute similarities should result in clusters that are common or shared across all the documents of the homogeneous collection. The clusters thus provide a gathering of the same elements, (i.e., elements having the same textual contents) to broaden the clustering into as broad a base as possible. In other words, it is expected that for the conversion of textual manuals, such as car user manuals, clusters tagged by certain manual section headings will be the same text (e.g., the same titles) for all the different car manuals in the collection.

[0041] Thus, the collection can be used for validating 18 (or possibly correcting) the clustering by content analysis of the documents of the collection. Verification by identical textual content is one way to validate the cluster formations. Unfortunately, it is common that often times other levels of structuring may use titles which are systematically different for different documents of the collection. For example, in the same subject matter travel descriptions, the main title may be different, so that not all clusters can be validated this way, but where such validation processes are available, they are useful to employ.

[0042] Clustering validation can also be implemented by content analysis of the textual form of the text block elements. For example, content patterns that are particularly associated with a section numbering in a manual can be used for helping to validate a cluster made of the content elements. Continuing the example, if a particular section number were missing, the conversion process could possibly look elsewhere for the misclassified or improperly clustered section. It should be noted that merely using a pattern that describes a document section numbering is not new in itself. What is important is that it should be appreciated that the use of content of the elements of a cluster can be available for validating so that the ordered elements of a particular cluster are at the same or appropriate level for the structured document format. For example, patterns that describe block numbering help validate a cluster made of the elements:

	80	Battery
	81	Light
	82	Anti-starting
	83	Instrument board
	85	Wipers
	86	Wiring

[0043] In the foregoing, element 84 is missing and could suggest a search for it elsewhere.

[0044] Cluster categorization 20 is the next processing step in the conversions. Once a set of clusters is generated, the clusters must be categorized into three possible categories suggested by the target DTD: head 42, body 44 or tail. The categorization 20 is based upon generic knowledge about each category. Saliency is particularly useful as a basis for categorization. As noted above, the saliency of a particular textual element in a document corresponds to the difference (in terms of attributes) between itself and its immediate preceding and following neighbors. This can be mathematically expressed as:
sal(x_i)=diff(x_i,x_i−1)+diff(x_i,x_i+1)  (1) $\begin{array}{cc}\mathrm{diff}\left(x,y\right)=\frac{\mathrm{attr}\left(x\right)-\left(\mathrm{attr}\left(x\right)\bigcap \mathrm{attr}\left(y\right)\right)}{\mathrm{attr}\left(x\right)}& \left(2\right)\end{array}$

[0045] where attr(x) is the set of attributes of the element x. Saliency is used in order to characterize head elements. Elements with a high saliency usually correspond to head/tail of the structure. The cluster saliency is the mean of the saliency of each cluster element. In practice, only the cluster with the highest saliency is categorized, which is enough for structuring the document.

[0046] Other criteria (positive as well as negative) can be used for categorizing 20. These include the position of the elements; if an element occurs at the end of the list, it cannot be a head; if the element occurs in the table of contents (certainly a head); if the element occurs first in the list (certainly a head); and, if two elements within the cluster are contiguous (certainly a part of the body). Combinations of any of these criteria can also be used to correctly categorize the content elements.

[0047] The last process in the conversion structuring is hierarchization 22 to form the tree model as shown in FIG. 2 comprising a plurality of hierarchical levels, wherein each level is added at a structuring process iteration. In other words, the structuring process to effect the conversion is top-down and iterative. At each iteration, a list of document content elements is presented (initially the list of all the preprocessed blocks of the document), where the heads 42 are marked up (i.e., the elements of the cluster with the highest saliency). For each head 42 a new block 46 is added with its substructure; head 42 and body 44. The bodies 44 are composed of document elements between two heads of the same cluster/level. This transformation is illustrated in FIG. 2. Each new body 44 is processed for the very next iteration, until no new head can be found. Thus, after the entire document has been processed to form the structured document 30, a tree model 40 of the type illustrated in FIG. 2 will comprise a structured representation of the entire document. Such a structure format 30 comprising a legacy format, comprise an improved stored form of the document providing enhanced usefulness in access and reference than could be obtained with the layout structure of the input document 10.

[0048] The claims, as originally presented and as they may be amended, encompass variations, alternatives, modifications, improvements, equivalents, and substantial equivalents of the embodiments and teachings disclosed herein, including those that are presently unforeseen or unappreciated, and that, for example, may arise from applicants/patentees and others.