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

• US 6,105,044 A
• Filed: 07/13/1999
• Issued: 08/15/2000
• Est. Priority Date: 07/19/1991
• Status: Expired due to Fees

• Current Assignee: Enigma Information Systems Ltd (PTC Inc.)
• Original Assignee: Enigma Information Systems Ltd (PTC Inc.)
• Inventors: Vogel, Jeffrey, DeRose, Steven
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/353,262
• Time in Patent Office: 399 Days
• Field of Search: 707/3, 707/514, 707/501, 707/529, 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 producing a digital form 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 method 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:

sending a request for a portion of the digital document using an indication of a starting point within the digital document;

receiving only the requested portion of the digital document including selected elements containing the indicated starting point; and

generating a digital form of the received portion of the digital document by applying properties corresponding to the received selected elements to the text content of said elements.

2. The method of claim 1, wherein receiving only the requested portion includes receiving a starting point element, the starting point element having been selected according to the indicated starting point;

and

wherein the step of generating a digital form includes;

providing a plurality of property specifications for type names utilized for elements in the digital document;

receiving an identity of any ancestor elements of the starting point element; and

applying a property specification corresponding to the type name of ancestor elements identified for each selected element to the text content of each selected element to produce the digital form.

3. The method of claim 2, wherein the step of applying the property specification includes:

retrieving the property specification of each ancestor element of the starting point element in the digital document; and

combining the property specifications of the ancestor elements with the property specification of the starting point element.

4. The method of claim 3, further comprising the steps of:

providing access, for each markup element, to an element descriptor addressable by a unique identifier for the markup element for storing a unique identifier of the parent element of the markup element; and

wherein the step of applying property specifications includes retrieving an indication of said each ancestor element from the element descriptor for the starting point element and said each ancestor element using the unique element identifiers corresponding to the starting point element and said each ancestor element.

5. The method of claim 3, wherein the type name of a markup element includes the type name of any ancestor element;

and

wherein the step of retrieving the property specification of each ancestor element comprises retrieving said property specification using the type name of the ancestor element obtained from the type name of the starting point element.

6. The method of claim 3, further comprising the step of temporarily storing in a stack the property specification of any ancestor element.

7. The method of claim 2, further comprising the steps of:

providing access to a web that stores an annotation to an element in the digital document, said web including, for each annotation, the unique element identifier of the annotated element and an indication of the annotation; and

wherein the step of applying property specifications to the text content of an element includes the steps of searching the web for the unique element identifier of the element and generating an indication that the element has an annotation if the element identifier for the element is found in the web.

8. The method of claim 2, further comprising the step of storing an indication of the starting point element in a history table.

9. The method of claim 2, wherein an element may have a security attribute and wherein the step of applying property specifications to the text content of an element includes the step of omitting the text content of an element having a security attribute.

10. The method of claim 2, further comprising the steps of:

receiving said indication of a starting point within the digital document; and

providing at an output the digital form.

11. A process of producing a digital information product comprising computer data signals defining a digital form 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 method 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 process comprising:

sending a request for a portion of the digital document using an indication of a starting point within the digital document;

receiving only the requested portion of the digital document including selected elements containing the indicated starting point; and

generating a digital form of the received portion of the digital document by applying properties corresponding to the received selected elements to the text content of said elements, and encoding the digital form in a computer data signal.

12. The process of claim 11, wherein receiving only the requested portion includes receiving a starting point element, the starting point element having been selected according to the indicated starting point;

and

wherein the step of generating a digital form includes;

providing a plurality of property specifications for type names utilized for elements in the digital document;

receiving an identity of any ancestor elements of the starting point element; and

applying a property specification corresponding to the type name of ancestor elements identified for each selected element to the text content of each selected element to produce the digital form.

13. The process of claim 12, wherein the step of applying the property specification includes:

retrieving the property specification of each ancestor element of the starting point element in the digital document; and

combining the property specifications of the ancestor elements with the property specification of the starting point element.

14. The process of claim 13, further comprising the steps of:

providing access, for each markup element, to an element descriptor addressable by a unique identifier for the markup element for storing a unique identifier of the parent element of the markup element; and

wherein the step of applying property specifications includes retrieving an indication of said each ancestor element from the element descriptor for the starting point element and said each ancestor element using the unique element identifiers corresponding to the starting point element and said each ancestor element.

15. The process of claim 13, wherein an element may have a security attribute and wherein the step of applying property specifications to the text content of an element includes the step of omitting the text content of an element having a security attribute.

16. The process of claim 13, wherein the type name of a markup element includes the type name of any ancestor element;

and

wherein the step of retrieving the property specification of each ancestor element comprises retrieving said property specification using the type name of the ancestor element obtained from the type name of the starting point element.

17. The process of claim 13, further comprising the step of temporarily storing in a stack the property specification of any ancestor element.

18. The process of claim 12, further comprising the steps of:

providing access to a web that stores an annotation to an element in the digital document, said web including, for each annotation, the unique element identifier of the annotated element and an indication of the annotation; and

wherein the step of applying property specifications to the text content of an element includes the steps of searching the web for the unique element identifier of the element and generating an indication that the element has an annotation if the element identifier for the element is found in the web.

19. The process of claim 12, further comprising the step of providing access to an indication of the starting point element in a history table.

20. The process of claim 12, further comprising the steps of:

receiving said indication of a starting point within the digital document; and

providing at an output the digital form.

21. A data processing system for producing a digital form 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 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 sending a request for a portion of the digital document using an indication of a starting point with in the digital document;

means for receiving only the requested portion of the digital document including selected elements containing the indicated starting point; and

means for generating a digital form of the received portion of the digital document by applying properties corresponding to the received selected elements to the text content of said elements.

22. The data processing system of claim 21, wherein the means for receiving only the requested portion includes means for receiving a starting point element, the starting point element having been selected according to the indicated starting point;

and

wherein the means of generating a digital form includes;

means for providing a plurality of property specifications for type names utilized for elements in the digital document;

means for receiving an identity of any ancestor elements of the starting point element; and

means for applying a property specification corresponding to the type name of ancestor elements identified for each selected element to the text content of each selected element to produce the digital form.

23. The data processing system of claim 22, wherein means for applying the property specification includes:

means for retrieving the property specification of each ancestor element of the starting point element in the digital document; and

means for combining the property specifications of the ancestor elements with the property specification of the starting point element.

24. The data processing system of claim 23, further comprising:

means for providing access, for each markup element, to an element descriptor addressable by a unique identifier for the markup element for storing a unique identifier of the parent element of the markup element; and

wherein the means for applying property specifications includes means for retrieving an indication of said each ancestor element from the element descriptor for the starting point element and means for said each ancestor element to use the unique element identifiers corresponding to the starting point element and said each ancestor element.

25. The data processing system of claim 23, wherein the type name of a markup element includes the type name of any ancestor element;

and

wherein the means for retrieving the property specification of each ancestor element comprises means for retrieving said property specification using the type name of the ancestor element obtained from the type name of the starting point element.

26. The data processing system of claim 23, further comprising means for temporarily storing in a stack the property specification of any ancestor element.

27. The data processing system of claim 22, further comprising:

means for providing access to a web that stores an annotation to an element in the digital document, said web including, for each annotation, the unique element identifier of the annotated element and an indication of the annotation; and

wherein the means for applying property specifications to the text content of an element includes means for searching the web for the unique element identifier of the element and means for generating an indication that the element has an annotation if the element identifier for the element is found in the web.

28. The data processing system of claim 22, further comprising means for providing access to an indication of the starting point element in a history table.

29. The data processing system of claim 22, wherein an element may have a security attribute and wherein the means for applying property specifications to the text content of an element includes means for omitting the text content of an element having a security attribute.

30. The data processing system of claim 22, further comprising:

means for receiving said indication of a starting point within the digital document; and

means for providing at an output the digital form.

31. A data processing system for producing a digital form 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 method 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 requesting component that produces at an output a request for a portion of the digital document including an indication of a starting point within the digital document; and

a data processing component that receives as an input the requested portion of the digital document including selected elements containing the indicated starting point, received in response to the output of the data requesting component, and that generates at an output a digital form of the digital document, the output being generated by the application of properties corresponding to the received selected elements to the text content of said elements.

32. The data processing system of claim 31, wherein the received portion includes a starting point element, the starting point element having been selected according to the indicated starting point;

and

wherein the data processing component includes;

means for providing a plurality of property specifications for type names utilized for elements in the digital document;

means for receiving an identity of any ancestor elements of the starting point element; and

means for applying a property specification corresponding to the type name of ancestor elements identified for each selected element to the text content of each selected element to produce the digital form.

33. The data processing system of claim 32, wherein the means for applying property specifications includes:

means for retrieving the property specification of each ancestor element of the starting point element in the digital document; and

means for combining the property specifications of the ancestor elements with the property specification of the starting point element.

34. The data processing system of claim 33, further comprising:

a first data access component that provides access, for each markup element, to an element descriptor addressable by a unique identifier for the markup element for storing a unique identifier of the parent element of the markup element; and

wherein the means for applying property specifications includes means for retrieving an indication of said each ancestor element from the element descriptor for the starting point element and means for said each ancestor element to use the unique element identifiers corresponding to the starting point element and said each ancestor element.

35. The data processing system of claim 33, wherein the type name of a markup element includes the type name of any ancestor element;

and

wherein the means for retrieving the property specification of each ancestor element comprises means for retrieving said property specification using the type name of the ancestor element obtained from the type name of the starting point element.

36. The data processing system of claim 33, further comprising a storage component that temporarily stores in a stack the property specification of any ancestor element.

37. The data processing system of claim 32, further comprising:

a second data access component that provides access to a web that stores an annotation to an element in the digital document, said web including, for each annotation, the unique element identifier of the annotated element and an indication of the annotation; and

wherein the means for applying property specifications to the text content of an element includes means for searching the web for the unique element identifier of the element and means for generating an indication that the element has an annotation if the element identifier for the element is found in the web.

38. The data processing system of claim 32, further comprising:

a third data access component that provides access to an indication of the starting point element in a history table.

39. The data processing system of claim 32, wherein an element may have a security attribute and wherein the means for applying property specifications to the text content of an element includes means for omitting the text content of an element having a security attribute.

40. The data processing system of claim 32, wherein the data requesting component receives at an input said indication of a starting point within the digital document.

41. A computer program product for producing a digital form 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 method 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 computer program product comprising:

a computer readable medium having computer program logic stored thereon, wherein the computer program logic defines;

a data requesting component which produces at an output a request for a portion of the digital document including an indication of a starting point within the digital document; and

a data processing component that receives as an input the requested portion of the digital document including selected elements containing the indicated starting point, received in response to the output of the data requesting component, and which generates at an output a digital form of the digital document, the output being generated by the application of properties corresponding to the received selected elements to the text content of said elements.

42. The data processing system of claim 41, wherein the received portion includes a starting point element, the starting point element having been selected according to the indicated starting point;

and

wherein the data processing component includes;

means for providing a plurality of property specifications for type names utilized for elements in the digital document;

means for receiving an identity of any ancestor elements of the starting point element; and

means for applying a property specification corresponding to the type name of ancestor elements identified for each selected element to the text content of each selected element to produce the digital form.

43. The data processing system of claim 42, wherein means for applying the property specification includes:

means for retrieving the property specification of each ancestor element of the starting point element in the digital document; and

means for combining the property specifications of the ancestor elements with the property specification of the starting point element.

44. The data processing system of claim 43, wherein the computer program logic further defines:

a first data access component that provides access, for each markup element, to an element descriptor addressable by a unique identifier for the markup element for storing a unique identifier of the parent element of the markup element; and

wherein the means for applying property specifications includes means for retrieving an indication of said each ancestor element from the element descriptor for the starting point element and means for said each ancestor element to use the unique element identifiers corresponding to the starting point element and said each ancestor element.

45. The data processing system of claim 43, wherein the type name of a markup element includes the type name of any ancestor element;

and

wherein the means for retrieving the property specification of each ancestor element comprises means for retrieving said property specification using the type name of the ancestor element obtained from the type name of the starting point element.

46. The data processing system of claim 43, wherein the computer program logic further defines a storage component that temporarily stores in a stack the property specification of any ancestor element.

47. The data processing system of claim 42, wherein the computer program logic further defines:

a second data access component that provides access to a web that stores an annotation to an element in the digital document, said web including, for each annotation, the unique element identifier of the annotated element and an indication of the annotation; and

wherein the means for applying property specifications to the text content of an element includes mean s for searching the web for the unique element identifier of the element and means for generating an indication that the element has an annotation if the element identifier for the element is found in the web.

48. The data processing system of claim 42, wherein the computer program logic further defines a third data access component that provides access to an indication of the starting point element in a history table.

49. The data processing system of claim 42, wherein an element may have a security attribute and wherein the means for applying property specifications to the text content of an element includes means for omitting the text content of an element having a security attribute.

50. The data processing system of claim 42, wherein the data requesting component receives at an input said indication of a starting point within the digital document.