Data processing system and method for generating a representation for and random access rendering of electronic documents

• US 5,983,248 A
• Filed: 06/30/1997
• Issued: 11/09/1999
• Est. Priority Date: 07/19/1991
• Status: Expired due to Term

• Current Assignee: Enigma Information Systems Ltd (PTC Inc.)
• Original Assignee: Inso Providence Corporation
• Inventors: Vogel, Jeffrey, DeRose, Steven
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): Homedre, Jean R.
• Application Number:
  US08/885,578
• Time in Patent Office: 862 Days
• Field of Search: 707/513, 707/514, 707/531, 707/104, 707/3, 707/906, 707/907
• US Class Current: 715/234
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06F 40/117 Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/151 Transformation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A data processing system and method for generating a representation of an electronic document, for indexing the electronic document, for navigating the electronic document using its representation and for displaying the electronic document on an output device. The system and method are used with electronic documents having descriptive markup which describes the content or meaning of the document rather than its appearance. Such documents may be represented by a tree. Each markup element defines a node or element in a tree. The tree is represented by providing a unique identifier for each element and for accessing a descriptor of the element. An element descriptor preferably includes indications of the parent, first child, last child, left sibling, right sibling, type name and text location for the element. The document representation is used to facilitate navigation of the text for constructing navigational aids such as table of contents and full text indexing. A document is also provided with a style sheet for specifying desired formatting characteristics for each type of element in the document. To display the document, a suitable starting point is found on the basis of a selected starting point. The document is displayed beginning with the suitable starting point and the format characteristics for each element displayed are retrieved from the style sheet and applied to the text of the displayed element.

Claims

1. A method of random access extraction of a portion of a hierarchical digital document, the digital document having descriptive markup defining a plurality of hierarchical elements, wherein each element has a type name, and has at least one of an ancestor element, a child element, a left sibling element, a right sibling element and unformatted text content, the data processing system using a representation of the digital document, including, for each element, an indication of any ancestor element, child element, and left and right sibling element, the method comprising:

receiving a request for a portion of a digital document including an indication of a starting point within the digital document; and

selecting elements from the digital document in accordance with the received request, including;

identifying one of the plurality of hierarchical elements within the digital document as an initial element containing the indicated starting point using the representation of the digital document; and

traversing the representation of the digital document to select elements of the digital document beginning with the initial element.

2. The method of claim 1, wherein the step of traversing the representation of the digital document includes:

identifying any ancestor elements of the initial element.

3. The method of claim 2, further comprising:

accessing a plurality of property specifications for type names utilized for elements in the digital document, said property specifications being stored separate from the digital document, wherein at least one property specification includes an indication of a breaking point to occur between elements; and

wherein the step of identifying the initial element includes searching backward from the indicated starting point in the digital document for a selected breaking point; and

wherein the initial element is the first element following the selected breaking point.

4. The method of claim 3, wherein the selected breaking point is the first breaking point preceding the indicated starting point.

5. The method of claim 1, wherein the step of identifying an initial element includes:

searching backward from the indicated starting point in the digital document for a selected element having a selected type name; and

wherein the initial element is the selected element.

6. The method of claim 5, wherein the selected element is the first element having the selected type name and preceding the indicated starting point.

7. A data processing system for random access extraction of a portion of a hierarchical digital document, the digital document having descriptive markup defining a plurality of hierarchical elements, wherein each element has a type name, and has at least one of an ancestor element, a child element, a left sibling element, a right sibling element and unformatted text content, the data processing system using a representation of the digital document, including, for each element, an indication of any ancestor element, child element, and left and right sibling element, the system comprising:

a data selection component that receives at an input a request for a portion of a digital document including an indication of a starting point within the digital document, and generates at an output selected elements from the digital document in accordance with the received request, the data selection component including;

a data identifying component that receives at an input the indicated starting point and generates at an output an initial element, the initial element identified using the representation of the digital document and being one of the plurality of hierarchical elements within the digital document containing the indicated starting point; and

a data traversing component that receives at an input the initial element and generates at an output selected elements of the digital document beginning with the initial element, the traversing component selecting elements by traversing the digital document.

8. The data processing system of claim 7, wherein the traversing component includes means for identifying any ancestor elements of the initial element.

9. The data processing system of claim 8, further comprising:

a data access component that accesses a plurality of property specifications for type names utilized for elements in the digital document, said property specifications being stored separate from the digital document, wherein at least one property specification includes an indication of a breaking point to occur between elements;

wherein the data identifying component includes means for searching backward from the indicated starting point in the digital document for a selected breaking point; and

wherein the initial element is the first element following the selected breaking point.

10. The data processing system of claim 9, wherein the selected breaking point is the first breaking point preceding the indicated starting point.

11. The data processing system of claim 7, wherein the data identifying component includes:

means for searching backward from the indicated starting point in the digital document for a selected element having a selected type name; and

wherein the initial element is the selected element.

12. The data processing system of claim 11, wherein the selected element is the first element having the selected type name and preceding the indicated starting point.

13. A computer program product for random access extraction of a portion of a hierarchical digital document, the digital document having descriptive markup defining a plurality of hierarchical elements, wherein each element has a type name, and has at least one of an ancestor element, a child element, a left sibling element, a right sibling element and unformatted text content, the data processing system using a representation of the digital document, including, for each element, an indication of any ancestor element, child element, and left and right sibling element, the system comprising:

a data selection component that receives at an input a request for a portion of a digital document including an indication of a starting point within the digital document, and generates at an output selected elements from the digital document in accordance with the received request, the data selection component including;

a data identifying component that receives at an input the indicated starting point and generates at an output an initial element, the initial element identified using the representation of the digital document and being one of the plurality of hierarchical elements within the digital document containing the indicated starting point; and

a data traversing component that receives at an input the initial element and generates at an output selected elements of the digital document beginning with the initial element, the traversing component selecting elements by traversing the digital document.

14. The data processing system of claim 13, wherein the traversing component includes means for identifying any ancestor elements of the initial element.

15. The data processing system of claim 14, further comprising:

a data access component that accesses a plurality of property specifications for type names utilized for elements in the digital document, said property specifications being stored separate from the digital document, wherein at least one property specification includes an indication of a breaking point to occur between elements;

wherein the data identifying component includes means for searching backward from the indicated starting point in the digital document for a selected breaking point; and

wherein the initial element is the first element following the selected breaking point.

16. The data processing system of claim 15, wherein the selected breaking point is the first breaking point preceding the indicated starting point.

17. The data processing system of claim 13, wherein the data identifying component includes:

means for searching backward from the indicated starting point in the digital document for a selected element having a selected type name; and

wherein the initial element is the selected element.

18. The data processing system of claim 13, wherein the selected element is the first element having the selected type name and preceding the indicated starting point.

19. A data processing system for random access extraction of a portion of a hierarchical digital document, the digital document having descriptive markup defining a plurality of hierarchical elements, wherein each element has a type name, and has at least one of an ancestor element, a child element, a left sibling element, a right sibling element and unformatted text content, the data processing system using a representation of the digital document, including, for each element, an indication of any ancestor element, child element, and left and right sibling element, the system comprising:

means for receiving a request for a portion of a digital document including an indication of a starting point within the digital document; and

means for selecting elements from the digital document in accordance with the received request, including;

means for identifying one of the plurality of hierarchical elements within the digital document as an initial element containing the indicated starting point using the representation of the digital document; and

means for traversing the representation of the digital document to select elements of the digital document beginning with the initial element.

20. The data processing system of claim 19, wherein the means for traversing the representation of the digital document includes:

means for identifying any ancestor elements of the initial element.

21. The data processing system of claim 20, further including:

means for accessing a plurality of property specifications for type names utilized for elements in the digital document, said property specifications being stored separate from the digital document, wherein at least one property specification includes an indication of a breaking point to occur between elements;

wherein the means for identifying the initial element includes means for searching backward from the indicated starting point in the digital document for a selected breaking point; and

wherein the initial element is the first element following the selected breaking point.

22. The data processing system of claim 21, therein the selected breaking point is the first breaking point preceding the indicated starting point.

23. The data processing system of claim 19, wherein the means for identifying an initial element includes:

means for searching backward from the indicated starting point in the digital document for a selected element having a selected type name; and

wherein the initial element is the selected element.

24. The data processing system of claim 23, wherein the selected element is the first element having the selected type name and preceding the indicated starting point.

25. A process of producing a digital information product comprising computer data signals defining a portion of a hierarchical digital document, the digital document having descriptive markup defining a plurality of hierarchical elements, wherein each element has a type name, and has at least one of an ancestor element, a child element, a left sibling element, a right sibling element and unformatted text content, the data processing system using a representation of the digital document, including, for each element, an indication of any ancestor element, child element, and left and right sibling element, the method comprising:

receiving a request for a portion of a digital document including an indication of a starting point within the digital document; and

selecting elements from the digital document in accordance with the received request and encoding the selected elements in a computer data signal, including;

identifying one of the plurality of hierarchical elements within the digital document as an initial element containing the indicated starting point using the representation of the digital document; and

traversing the representation of the digital document to select elements of the digital document beginning with the initial element.

26. The process of claim 25, wherein the step of traversing the representation of the digital document includes:

identifying any ancestor elements of the initial element.

27. The process of claim 26, further including:

accessing a plurality of property specifications for type names utilized for elements in the digital document, said property specifications being stored separate from the digital document, wherein at least one property specification includes an indication of a breaking point to occur between elements; and

wherein the step of identifying the initial element includes searching backward from the indicated starting point in the digital document for a selected breaking point; and

wherein the initial element is the first element following the selected breaking point.

28. The process of claim 27, wherein the selected breaking point is the first breaking point preceding the indicated starting point.

29. The process of claim 25, wherein the step of identifying an initial element includes;

searching backward from the indicated starting point in the digital document for a selected element having a selected type name; and

wherein the initial element is the selected element.

30. The process of claim 29, wherein the selected element is the first element having the selected type name and preceding the indicated starting point.