Configurable representation of structured data

[0001] The present invention relates to representing and processing structured documents.

[0002] The Internet is a global network that uses a common communication protocol, the Transfer Control Protocol/Internet Protocol (“TCP/IP”), to transmit data from one computer to another. In order to use the transmitted data, computer applications adopt communication standards. For example, the World Wide Web (“Web”) is a system that includes applications supporting Hyper Text Markup Language (“HTML”) documents.

[0003] An HTML document includes content, e.g., text, and corresponding instructions, typically about how to format the content (i.e., the document is “marked up” with formatting instructions). To include an instruction, a tag is added in the document. The tag has a name that can be used to identify the corresponding instruction, and identifiers that mark the content for which the tag applies. For example, the tag can have opening and closing elements that bracket the marked content in the document. The marked content can include one or more additional tags, called child tags. Child tags can include their own children to form a hierarchical structure of the tags.

[0004] In markup languages such as Standard Generalized Markup Language (“SGML”) and eXtensible Markup Language (“XML”), generalized tags can also be used to represent structure (and not just formatting) in the content of an electronic document (and, more generally, in any type of text data). For example, a generalized <name> tag can be used to mark up all names in a document, and optionally a separate file, e.g., in eXtensible Stylesheet Language (“XSL”), can describe how tagged names should be formatted. A definition file can be used to specify the generalized tags and their relations to each other, e.g., by using Document Type Definition (“DTD”) or XML Schema languages. For example, a definition file can specify what are the allowed tags, which tags can have children, or how many and what type of children a particular tag can have. The generalized markup language document becomes self descriptive when combined with the corresponding definition file.

[0005] A graphical structure editor provides for user-configurable access to elements of source data based on interactive selection of elements of a sample hierarchy. In general, in one aspect, the invention provides methods and apparatus, including computer program products, implementing techniques for accessing elements of source data. The techniques include receiving sample data that is capable of being represented as a hierarchy of elements, presenting a graphical representation of the hierarchy of elements, receiving user input selecting one or more elements in the graphical representation of the hierarchy of elements, defining a template structure based on the selected elements, and accessing source data according to the template structure.

[0006] Particular implementations can include one or more of the following features. The sample data can be examined to define the hierarchy of elements, and a graphical representation of the defined hierarchy of elements can be presented to a user. Roles in the template structure can be specified for one or more selected elements. Selected element can be identified as representing a single item of data or a set of data in the template structure. Roles can be specified by selecting a control element associated with the selected element. A control element can be selected to specify that source data corresponding to the selected element will be accessed as unstructured data. Selection parameters can be specified for selected elements, and the source data can be accessed according to the selection parameters. Elements can be identified as elements to be included in or excluded from the template structure, and the template structure can be defined accordingly. Accessing source data can include generating a representation of the source data according to the template structure. The representation of the source data can include a subset of the source data defined according to the template structure. An electronic document can be generated incorporating the source data accessed according to the template structure. The sample data can include a plurality of elements having associated tags, and the graphical representation of the hierarchy of elements can include a representation of a hierarchy of tags associated with the elements. The sample data and the source data can each include a plurality of elements associated with a common set of tags. The template structure can be defined based on one or more selected tags included in the common set tags. Accessing the source data according to the template structure can include accessing one or more source data elements associated with the selected tags of the common set of tags.

[0007] In general, in another aspect, the invention provides methods and apparatus, including computer program products, implementing techniques for accessing elements of source data. The techniques include receiving user input identifying sample data that includes a plurality of elements associated with tags in a set of tags and is representable as a hierarchy of tags in the set of tags; presenting a graphical representation of the hierarchy of tags; receiving user input selecting one or more tags in the graphical representation of the hierarchy of tags; generating a template structure based on the selected tags; receiving user input identifying source data that including one or more elements associated with one or more tags in the set of tags; and presenting a representation of the source data according to the template structure. The representation includes one or more elements of the source data associated with tags of the selected tags.

[0008] The invention can be implemented to realize one or more of the following advantages. Users can select and access content in a structured source document according to a specified sample structure by using a graphical user interface (“GUI”). The content can be accessed without inspecting complex text documents, such as XML files. The GUI can present a comprehensive tree structure that corresponds to a hierarchical structure of sample data. The tree structure can include nodes and leaves corresponding to elements, e.g., tags, in the sample data. The tree structure can be displayed in a graphical representation that is expandable or collapsible to present or hide structural elements in the tree. Elements in the tree structure can be graphically selected according to the user's interest, and the user or an application can access and use elements of source data corresponding to the selected elements for further processing. For example, source data elements associated with selected tags can be presented, or extraneous source data elements can be hidden in a structured document according to the user's interest. The structure sample can represent a tagged hierarchy corresponding to the structure of the source data, or other data, such as similarly structured data. For example, the structure sample can be a DTD or an XML Schema.

[0009] The details of one or more implementations of the invention are set forth in the accompanying drawings and the description below. Other features and advantages of the invention will become apparent from the description, the drawings, and the claims.

[0013] Like reference numbers and designations in the various drawings indicate like elements.

[0014] FIG. 1 illustrates one implementation of a system 100 according to one aspect of the invention that is operable to select and access elements of structured source data 10 according to a template structure derived from sample data 20. The source data 10 and sample data 20 is data that can be represented as a hierarchy of elements, such as data that includes a plurality of structural and/or semantic subunits occupying relative locations in a hierarchical structure. The hierarchical structure of the data can be defined explicitly, such as by tags associated with the various elements that classify their associated elements according to the element's structural, semantic, or other role in the data. For example, the source data 10 and/or sample data 20 can be a hierarchically structured markup language document, such as a HTML, SGML, or XML document. Alternatively, the hierarchical structure of the data can be defined implicitly, such as where the source data 10 is a Portable Document Format (“PDF”) document that does not explicitly include tags, but has a hierarchical structure that can be represented by tags.

[0015] The system 100 includes a graphical structure editor 110, a display device 120, and an input device 130. The graphical structure editor 110 identifies a hierarchical structure of sample data 20. The sample data 20 is data that can be represented as a hierarchy of elements. The sample data 20 can be the same as the source data 10 or different from the source data 10. In general, the sample data 20 will have a structure that is similar (in whole or in part) to that of the source data 10, or that is expected to be similar to the structure of source data to be processed using the system 100. Using the graphical structure editor 110 in a graphical user interface (“GUI”), a user can select one or more elements in the identified structure and access elements of the source data 10 corresponding to the selected elements. The GUI is displayed to the user on the display device 120, and input from the user is received through the input device 130. The graphical structure editor 110 can transmit the selected elements of the source document 10 to a document generator, or to any other application, for further processing, such as incorporation into a structured document.

[0016] The graphical structure editor 110 includes an analyzer 112 and a graphical selector 115. The analyzer 112 examines the sample data 20 to identify a hierarchy of elements 113 that represents the structure of the sample data 20. The graphical selector 115 can display a representation of the hierarchy of elements 113 to a user and receive user input selecting elements in the hierarchy. From the selected elements, the graphical selector 115 defines a template structure 117 that can be used to access corresponding content in the source data 10.

[0017] FIG. 2 illustrates a method 200 for accessing elements of source data 10, according to one aspect of the invention. The method 200 can be performed, e.g., using a system 100 including the graphical structure editor 110. The method begins when the system receives sample data that can be represented as a hierarchy of elements (step 210). The sample data can be, for example, a structured sample document in HTML, SGML, XML or tagged Adobe® PDF format, in which elements of the sample data are associated with tags that define the logical structure of the data (e.g., a tag hierarchy). Alternatively, the sample data can be a structured document in a format, such as Adobe® PDF, in which logical structure is not represented by tagging. In still another alternative, the sample data can be a structural representation of a structured document in the form of a definition file, such as a DTD or XML Schema that expressly defines a hierarchy of elements.

[0018] The sample data can be received from a local data source or over a network such as the Internet. The graphical structure editor can request the sample data—for example, in response to user input identifying the sample data for use in accessing source data. Thus, for example, the user can specify a file name or a URL that identifies the sample data, and the graphical source editor can request the specified sample data from a file server, e.g., a web server. Optionally, where the sample data is a web document, the graphical structure editor can request a web server to parse the web document using server side scripting technology such as Active Server Pages (“ASP”), Java Server Pages (“JSP”), and Hypertext Preprocessor (“PHP”), and the web server can transmit the result of parsing, e.g., in XML format, to the graphical structure editor.

[0019] The system presents a representation of a hierarchy of elements of the sample data (step 220). The hierarchy of elements can be represented as a tree structure—i.e., a hierarchy of nodes and leaves. A node, also called a parent, has at least one child; a leaf has no child. A child is a node or leaf representing an element that is below the parent in the hierarchy and has an immediate relation to the parent. The relation between the parent and one or more children can be represented as branches of the tree structure.

[0020] In one implementation, the system 100 (e.g., analyzer 112) defines the hierarchy of elements by examining the sample data. Where the sample data explicitly defines the hierarchy, as in a tagged markup language document, the system can identify a hierarchy of elements corresponding directly to the tags in the document. The system can parse the document to identify tags and to identify the hierarchical relationships between identified tags. The system uses the identified tags and relationships to define the hierarchy, such that tags in the document correspond to nodes and leaves in the tree structure, with tags having one or more child tags being treated as nodes, the child tags as the children of the node, and tags without any child tag as leaves. Where the sample data does not explicitly include tags, a tagged representation of the sample data can be generated by extracting structure information from the sample data and associating tags with the data based on the extracted structure information using known techniques, such as those disclosed in U.S. Pat. No. 6,298,357 and U.S. patent application Ser. No. 09/266,680, filed on Mar. 11, 1999, which are incorporated by reference herein. Alternatively, where the sample data includes a predefined hierarchy of elements, such as a DTD or schema, the system can present a representation of that hierarchy without examining individual elements of the sample data.

[0021] The system can present a representation that is simpler than the tagged hierarchy defined in the sample data. For example, if a tag has multiple children carrying the same tag, the system can simplify the hierarchy by including only one of the multiple children in the representation. Furthermore, the system can disregard tags, such as certain formatting tags, that have no structural relevance for identifying the hierarchy of elements.

[0022] The system can also be configured to present a representation that is more complete in some aspect than a tagged hierarchy that is defined in the sample data. For example, the tagged hierarchy may include a tag that appears at multiple positions in the hierarchy and has different children at different positions. Such children can be united by the analyzer so that the representation of the hierarchy will include all possible children of the tag. For example, if a node <client> has only a first child—e.g., <name>—at one position of the tagged hierarchy, and only a second child—e.g., <phone>—at another position, the representation can include both children, i.e., <name> and <phone>, at each occurrence of the node <client>.

[0023] In one implementation, the system can insert nodes or leaves to the tree structure, e.g., based on user input. The inserted nodes or leaves can be, e.g., tags that have been disregarded by the system in constructing the tree structure. Alternatively, the inserted nodes or leaves can be elements that do not occur in the sample data, but that are expected to be included in the source data, or can be containers without content for integrating a subset of the elements in the hierarchy. In one implementation, the system can insert optional elements that can be activated to switch between alternative tree structures for the same sample data.

[0024] The system receives a selection of elements in the graphical representation of the hierarchy of elements (step 230). The elements can be selected by a user in a graphical user interface. Optionally, for each selected element, the user can specify one or more selection parameters to indicate how the selection can be applied to access content in corresponding elements of source data. For example, the user can specify a selection parameter to indicate that the selected element(s) will be included in or excluded from a template structure (described below) that can be used to access source data. Similarly, a selection parameter can specify how source data elements can be accessed if multiple children of the same parent carry a selected tag (e.g., <name> tags in a list of names). Selection parameters can also indicate that particular elements of the source data can be accessed only in children of a selected element and the content in the selected element itself will not be accessed. The graphical selection is discussed in more detail with reference to FIG. 3, and an exemplary GUI for the selection is shown in FIG. 4.

[0025] The system defines a template structure based on the selected elements (step 240). The template structure defines a view that can be applied to access elements of appropriately structured source data, as will be described in more detail below. The template structure incorporates the selected elements and any associated selection parameters. Thus, for example, in one implementation the template structure includes only elements of the sample hierarchy that are selected to be included in the template structure (i.e., where the selection parameters for the selected element specify that the element is to be included). The system can also be configured to include all elements of the sample hierarchy except for elements specifically selected for exclusion (i.e., where the selection parameters identify the element as one to be excluded).

[0026] The template structure can be implemented as a set of selection records that identify the selected elements in the hierarchy and, for each selected element, specify an access path and any corresponding selection parameters. The access path can include a sequence of elements, e.g., tags, through which the selected element can be accessed in a corresponding hierarchy of the source data. The selection parameters specify how content can be accessed in the selected element—for example, specifying that data corresponding to the selected element can or cannot be accessed in the source data.

[0027] The system accesses elements of the source data based on the template structure (step 250). In one implementation, the system examines the source data to identify elements corresponding to the elements defined for the template structure, and accesses those elements, optionally according to any specified selection parameters. Where the source data is tagged structured data, the system can examine the source data by parsing the tags associated with elements of the source data to identify elements associated with tags that are included in the template structure. Where the source data does not include a tagged hierarchy representing the logical structure of the data, a tagged hierarchy can be generated by extracting structural information from the source data as described above.

[0028] Thus, for example, in the implementation described above where the template structure is defined by a set of selection records, for each selected element, the system follows the specified access path to find any corresponding elements in the source document. If a corresponding element is found in the source data, the system can access the corresponding element, optionally according to the selection parameters specified for the selected element (e.g., accessing any elements corresponding to elements whose selection parameters identify the element as one to be included in the template structure, ignoring any elements having selection parameters identifying the element as one to be excluded, etc.). If no selection parameter is specified, the system can use a default access method, such as accessing only the source data element corresponding to the selected element.

[0029] If more than one corresponding element is found by following the access path in the source data, the selection parameters can be used to determine how to access the found elements. Alternatively, the system can prompt a user to select from the found elements. If no corresponding element is found in the source data, the system can ignore the selected element, or return a message indicating that the selected element is not found. Optionally, an error message can request user input for indicating instructions to handle any missing elements.

[0030] In one implementation, a representation of the template structure is presented to a user. The representation of the template structure can include only those elements selected for inclusion, as described above. The user can further simplify the template structure by further selecting from the included elements a subset of elements that will be used to access corresponding elements of the source data. The representation of the template structure can be significantly simpler than the representation of the hierarchy in the sample data.

[0031] In one implementation, the system incorporates the accessed elements into a representation of the source data based on the template structure (e.g., according to a user's selection)—that is, a representation that includes and/or excludes elements of the source data based on the template structure. The system can incorporate one or more of the accessed elements into a document having a hierarchy of elements corresponding to the template structure. The document can be a structured document that has the same or a different structure than the source document. For example, the document can incorporate the accessed elements in a non-hierarchical structure, or the document can lack any specific structure at all.

[0032] FIG. 3 shows a selecting process 300 for graphically selecting elements in a hierarchy of elements of sample data. The system displays one or more graphical representations of the hierarchy of elements (step 310). The graphical representations can be part of a GUI through which a user can interact with the system. One example of such a GUI is shown in FIG. 4. In one implementation, the graphical representation is expandable and collapsible to present and hide, respectively, structural elements in the hierarchy. For example, the user can change the graphical representation any time during the selecting process by selecting a portion of the graphical representation with a pointing device included in the input device 130.

[0033] An element of the hierarchy is selected (step 320) and a selection parameter for the selected element is specified (step 330). The element can be selected by the user through the GUI, for example, by using the pointing device and selecting the element in question. To specify selection parameters, the user can select items from a parameter menu that includes available choices for selection parameters. The parameter menu can appear automatically when the element is selected or can be shown to the user on request. Optionally, the system can be configured to provide default values for the selection parameters.

[0034] In one implementation (corresponding to the GUI shown in FIG. 4), the user can specify one of four selection parameters by using a parameter menu. The first selection parameter indicates that the selected element is “bindable”. A bindable element includes content in which the user is interested, i.e., a user of the template structure can choose to “bind”, i.e., access the content. The second selection parameter indicates that the selected element is “not-bindable”. A not-bindable element does not include content in which the user is interested, i.e., the content of such element, including children of the element, cannot be accessed according to the template structure. The third selection parameter indicates that a user of the template structure can access only content in the children of the selected element, but not the content of the selected element itself. The fourth selection parameter indicates that the selected element can be treated as a “rowset”—that is, if the selected element appears in the source document multiple times as a child of the same parent, content can be retrieved from each child. In other words, the selected element can be iterated over multiple times during accessing content in the source document.

[0035] Alternatively, or in addition, the system can be configured to provide one or more other or additional selection parameters. For example, the user can be allowed to specify a limited number of iterations for rowset elements. Optionally, the user can also select a specific starting point or inverse direction for iterating over a rowset element. Furthermore, a selection parameter can specify if source data corresponding to a selected element can be accessed as structured or unstructured data.

[0036] In one implementation, the system can specify one or more selection parameters by using control elements associated with one or more structural elements in the tree structure. The control elements can be inserted in the tree structure and selected to specify a selection parameter for the associated structural elements. For example, as shown in FIG. 4, a [body] element can be associated with each node in the tree structure. For each node, the [body] element can be selected to include or omit structural information when accessing source data corresponding to the node. For example, if the [body] element is selected as “not-bindable”, source data can be accessed as data structured according to the children of the node; if the [body] element is selected as “bindable”, source data can be accessed without structuring according to the children (optionally, it can or cannot be structured according to grandchildren of the node).

[0037] The user can select another element (“Yes” branch of decision 340). Any number of elements can be selected by repeatedly selecting elements and specifying corresponding selection parameters (steps 320 and 330). Optionally, the user can change a previous selection by selecting the same element again. Once the user is satisfied with the selection (“No” branch of decision 340), the selecting process 300 stops (step 350).

[0038] FIG. 4 shows an exemplary GUI 400 that can be provided in system 100 to receive user input for selecting elements of structured sample data. The GUI 400 includes a “Template Name” field 410 for receiving user input identifying a template structure to be edited, and a “Sample XML URL” field 420 for receiving user input identifying sample data by a URL. A graphical representation 430 of a hierarchy of elements of the sample data (derived, e.g., from an examination of the sample data as described above) is presented in a window. Elements of the hierarchy, such as nodes and leaves 432-439, can be selected in the graphical representation using a pointing device. For each selected element, a selection parameter can be specified using a parameter menu 440.

[0039] In the example shown in FIG. 4, the sample data hierarchy is represented as a tree structure that includes nodes and leaves that correspond to tags in an XML document identified in the Sample XML URL field 420. The sample data includes an <orders> tag that is represented by an ‘orders’ node 432. The ‘orders’ node 432 includes an ‘order’ node 434 that corresponds to one or more <order> tags in the sample data. Each <order> tag can have child tags: a <no> tag corresponding to an order number and represented by a ‘no’ leaf 435; a <date> tag represented by a ‘date’ leaf 436; and one or more <item> tags represented by a single ‘item’ node 437. Each <item> tag can be a parent and have child tags, such as a <quantity> tag represented by a ‘quantity’ leaf 439.

[0040] In the graphical representation 430, each element, i.e., a node or a leaf, has a corresponding icon, and the hierarchical relations between the structural elements are represented by corresponding lines. In one implementation, an element can be selected by selecting the corresponding icon with a pointing device. For each element, the corresponding icon indicates a selection parameter from the parameter menu 440. The selection parameter can be set, for example, by “right clicking” on the corresponding symbol and choosing an entry from a pop-up parameter menu 440. Furthermore, each node has an associated collapse indicator, e.g. collapse indicator 437r for ‘item’ node 437, that indicates if children of the node are shown (“−”) or hidden (“+”) in the graphical representation 430. By selecting a collapse indicator with the pointing device, the children of the associated node can be shown or hidden.

[0041] The parameter menu 440 includes entries for setting selection parameters to control access of content in the selected elements. The parameter menu 440 includes four entries: Bindable, Not bindable, Bind children only, and Treat as a rowset. The corresponding selection parameters are discussed above with reference to FIG. 3.

[0042] The invention can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. The invention can be implemented as a computer program product, i.e., a computer program tangibly embodied in an information carrier, e.g., in a machine-readable storage device or in a propagated signal, for execution by, or to control the operation of, data processing apparatus, e.g., a programmable processor, a computer, or multiple computers. A computer program can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program can be deployed to be executed on one computer or on multiple computers at one site or distributed across multiple sites and interconnected by a communication network.

[0043] Method steps of the invention can be performed by one or more programmable processors executing a computer program to perform functions of the invention by operating on input data and generating output. Method steps can also be performed by, and apparatus of the invention can be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application-specific integrated circuit).

[0044] Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for executing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto-optical disks, or optical disks. Information carriers suitable for embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in special purpose logic circuitry.

[0045] To provide for interaction with a user, the invention can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input.

[0046] By way of example, a printing device implementing an interpreter for a page description language, such as the PostScript® language, includes a microprocessor for executing program instructions (including font instructions) stored on a printer random access memory (RAM) and a printer read-only memory (ROM) and controlling a printer marking engine. The RAM is optionally supplemented by a mass storage device such as a hard disk. The essential elements of a computer are a processor for executing instructions and a memory. A computer can generally also receive programs and data from a storage medium such as an internal disk or a removable disk. These elements will also be found in a conventional desktop or workstation computer as well as other computers suitable for executing computer programs implementing the methods described here, which can be used in conjunction with any digital print engine or marking engine, display monitor, or other raster output device capable of producing color or gray scale pixels on paper, film, display screen, or other output medium.

[0047] The invention has been described in terms of particular embodiments. Other embodiments are within the scope of the following claims. For example, the steps of the invention can be performed in a different order and still achieve desirable results.