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

• US 5,557,722 A
• Filed: 04/07/1995
• Issued: 09/17/1996
• Est. Priority Date: 07/19/1991
• Status: Expired due to Term

• Current Assignee: Enigma Information Systems Ltd (PTC Inc.)
• Original Assignee: Electronic Book Technologies, Inc. (eBT International, Inc.)
• Inventors: Vogel, Jeffrey, DeRose, Steven
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/419,051
• Time in Patent Office: 529 Days
• Field of Search: 395/145, 395/148, 395/600, 395/146, 395/144, 364/DIG. 1, 364/
• 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 data processing system for randomly accessing and formatting a portion of an electronically published document having fixed text content and fixed structure defined by descriptive markup defining a plurality of hierarchical elements, wherein each element except a root element has an ancestor element and a type name and at least one element has text content, the data processing system comprising:

means for storing a format specification for each type name utilized for elements in the electronically published document, wherein the format specification for a type name defines appearance of the text content of the elements in the electronically published document having the type name, and wherein the means for storing is separate from the electronically published document;

means for receiving an indication of a starting point within the electronically published document;

means for selecting a starting point element within the electronically published document according to the received indication of the starting point;

means for selecting elements of the electronically published document beginning with the selected starting point element;

means for identifying any ancestor elements of the selected elements; and

means for formatting the text content of each selected element according to a combination of the format specifications for the type names of ancestor elements identified for the selected element and for the type name of the selected element.

2. A data processing system as set forth in claim 1, wherein the means for formatting includes means for retrieving the format specification for the type name of each ancestor element of the selected element in the electronically published document, and means for combining the format specifications for the type names of the ancestor elements with the format specification for the type name of the selected element.

3. A data processing system as set forth in claim 2, further comprising:

for each element, means, addressable by a unique identifier for the element, for storing a unique identifier of any parent element of the element; and

wherein the means for identifying ancestor elements includes means for retrieving an indication of each ancestor element of the selected element from the addressable means for storing by addressing the addressable means for storing with the unique identifier of the selected element and each ancestor element.

4. The data processing system of claim 2,

wherein the type name of an element includes the type name of any ancestor element;

and

wherein the means for retrieving the format specification for the type name of each ancestor element of the selected element comprises means for retrieving the format specification using the type name of the ancestor element obtained from the type name of the selected element.

5. The data processing system of claim 2, further comprising a stack for temporarily storing the format specification for the type name of any ancestor element.

6. A data processing system as set forth in claim 1, wherein at least one format specification includes an indication of a breaking point to occur between elements, and

wherein the means for selecting a starting point element includes means for searching backward from the starting point in the electronically published document for a selected breaking point;

and

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

7. A data processing system as set forth in claim 6, wherein the selected breaking point is the first breaking point preceding the starting point.

8. A data processing system as set forth in claim 1, wherein the means for selecting a starting point element includes:

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

wherein the starting point element is the selected element.

9. A data processing system as set forth in claim 8, wherein the selected element is the first element having the selected type name and preceding the starting point.

10. The data processing system of claim 1, further comprising:

a web for storing annotations to an element in the electronically published document, wherein the web includes, for each annotation, an identifier for each element having an annotation and an indication of the annotation; and

wherein the means for formatting the text content of each selected element includes means for searching the web for the identifier of the selected element and means for generating an indication that the selected element has an annotation if the identifier for the selected element is found in the web.

11. The data processing system of claim 1 wherein an element may have a security attribute and wherein the means for formatting the text content of each selected element omits the selected element if the selected element has a security attribute.

12. The data processing system of claim 1 further comprising a history table for storing an indication of the starting point element.

13. A computer-implemented method for randomly accessing and formatting a portion of an electronically published document having fixed text content and fixed structure defined by descriptive markup defining a plurality of hierarchical elements, wherein each element except a root element has an ancestor element and a type name, and at least one element has text content, the method using a memory storing a format specification for each type name utilized for elements in the electronically published document, wherein the format specification for a type name defines appearance of the text content of the elements in the electronically published document having the type name, and wherein the memory separately stores the electronically published document, the method comprising the steps, performed by the computer, of:

receiving an indication of a starting point within the electronically published document;

selecting a starting point element within the electronically published document according to the received indication of the starting point;

selecting elements of the electronically published document beginning with the selected starting point element;

identifying ancestor elements of the selected elements; and

formatting the text content of each selected element according to a combination of format specification for the type names of ancestor elements identified for the selected element and for the type name of the selected element.

14. A method as set forth in claim 13 wherein the step of formatting includes the steps of retrieving the format specifications for the type name of each ancestor element of the selected element in the electronically published document, and combining the format specifications for the type names of the ancestor elements with the format specification of the type name of the selected element.

15. A method as set forth in claim 14, further comprising the steps of:

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

wherein the step of identifying ancestor elements includes the step of retrieving an indication of each ancestor element from the provided element descriptor for the selected element and for each ancestor element using the unique element identifiers corresponding to the selected element and to each ancestor element.

16. A method as set forth in claim 14,

wherein the type name of an element includes the type name of any ancestor element;

and

wherein the step of retrieving the format specification for the type name of each ancestor element of the selected element comprises the step of retrieving the format specification using the type name of the ancestor element obtained from the type name of the selected element.

17. The method of claim 14, further comprising the step of temporarily storing in a stack the format specification for the type name of any ancestor element.

18. A method as set forth in claim 13, wherein at least one format specification includes an indication of a breaking points to occur between displayed elements, wherein the step of selecting a starting point element includes the step of:

searching backward from the starting point in the electronically published document for a selected breaking point; and

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

19. A method as set forth in claim 18, wherein the selected breaking point is the first breaking point preceding the starting point.

20. A method as set forth in claim 13, wherein the step of selecting a starting point element includes the step of:

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

wherein the starting point element is the selected element.

21. A method as set forth in claim 20, wherein the selected element is the first element having the selected type name and preceding the starting point.

22. The method of claim 13 further comprising the steps of:

storing, in a web, an annotation to an element in the electronically published document, wherein the web includes, for each annotation, an identifier for each element having an annotation and an indication of the annotation; and

wherein the step of formatting the text content of the selected element includes the steps of searching the web for the identifier of the selected element and generating an indication that the selected element has an annotation if the identifier for the selected element is found in the web.

23. The method of claim 13 further comprising the step of storing an indication of the starting point element in a history table.

24. The method of claim 13 wherein an element may have a security attribute and wherein the step of formatting the text content of each selected element includes the step of omitting the selected element if the selected element has a security attribute.

25. A method for randomly accessing and formatting a portion of an electronically published document having fixed content and fixed structure defined by descriptive markup defining a plurality of hierarchical elements, wherein each element has a type name, wherein each element except a root element has an ancestor element and wherein at least one element has content, the electronically published document having a format specification for each type name utilized for elements in the electronically published document, wherein the format specification for a type name defines appearance of content of the elements in the electronically published document having the type name, the method comprising the steps of:

selecting a starting point element within the electronically published document;

selecting elements of the document beginning with the starting point element;

identifying any ancestor elements of the selected elements; and

formatting the content of each selected element according to a combination of format specifications for the type names of ancestor elements identified for the selected element and for the type name of the selected element beginning with the starting point element.

26. A method as set forth in claim 25, wherein the step of formatting comprises the steps of:

retrieving the format specifications for the type names of the selected element and each ancestor element of the selected element;

combining the format specification for the type names of all ancestor elements with the format specification for the type name of the selected element; and

applying the combined format specifications to the content of the selected element.

27. The method of claim 25, wherein a format specification is modifiable, the method further comprising the steps of;

receiving an indication of a modified format specification, and

reformatting only the portion of the electronically published document according to the modified format specification.

28. The method of claim 25, further comprising the steps of:

receiving an indication of a modification to a display area for which the electronically published document is formatted; and

reformatting only the portion of the electronically published document according to the new display area.

29. A data processing system for randomly accessing and formatting content of an electronically published document having fixed content and fixed structure defined by descriptive markup defining a plurality of hierarchical elements, wherein each element has a unique identifier and a type name, wherein each element except a root element has an ancestor element and at least one element has content, comprising:

means for storing the electronically published document;

means for storing a format specification for each type name utilized for elements in the electronically published document, wherein the format specification for a type name defines appearance of the text content of the elements in the electronically published document having the type name;

means for storing an element directory including means for storing the unique identifier of any parent element of each element having a parent element, in a manner accessible using the unique identifier of the element;

means for receiving an indication of a selected element within the electronically published document;

means for accessing the element directory to identify any ancestor elements of the selected element; and

means for formatting the content of the selected element according to a combination of format specifications for the type names of ancestor elements identified for the selected element and for the type name of the selected element beginning with the selected element thereby formatting the content of the selected element.

30. A data processing system for randomly accessing and formatting a portion of an electronically published document having fixed text content and fixed structure deflated by descriptive markup defining a plurality of hierarchical elements, wherein each element except a root element has an ancestor element, wherein each element has a type name and at least one element has text content, the data processing system comprising:

means for storing, for each element, an indication of any ancestor element;

means for storing a format specification for each type name utilized for elements in the electronically published document, wherein the format specification for a type name defines appearance of the text content of the elements in the electronically published document having the type name, and wherein the means for storing is separate from the electronically published document;

means for receiving an indication of a starting point within the electronically published document;

means for selecting at least one element within the electronically published document according to the received indication of the starting point; and

means for formatting the text content of each selected element according to a combination of format specifications for the type names of ancestor elements for the selected element and for the type name of the selected element, including means for accessing the means for storing to identify any ancestor elements.