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

• US 6,101,512 A
• Filed: 07/13/1999
• Issued: 08/08/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: DeRose, Steven, Vogel, Jeffrey
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/353,257
• Time in Patent Office: 392 Days
• Field of Search: 707/3, 707/100, 707/104, 707/513, 707/514, 707/531, 707/907, 707/529
• 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 computer program product for storing a representation of a digital document, including first means for storing the digital document, the digital document having descriptive markup defining a plurality of hierarchical elements, wherein each element except a root element has an ancestor element and wherein each element has a type name and wherein an element may have a child element, a left sibling element, a right sibling element, and wherein at least one element contains text content, the computer program product comprising:

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

second means for storing a value indicative of a parent element for each element having a parent element;

third means for storing a value indicative of a first child element for each element having a child element; and

fourth means for storing a value indicative of a left sibling element, for each element having a left sibling element.

2. The computer program product as set forth in claim 1, wherein the computer program logic farther defines:

fifth means for storing the text content of the digital document;

for each element containing text content, sixth means for storing a value indicative of the location of the text content in the fifth means for storing the text content; and

seventh means for storing, for each element, the type name of the mark up element.

3. The computer program product as set forth in claim 2, wherein the computer program logic further defines:

means for parsing the digital document to provide a sequence of element events response to detection of elements and text events in response to detection of text content;

means for assigning a unique element identifier to each element event and to each text event;

means for constructing the type name of each element from the descriptive markup defining the element;

means for generating an element descriptor for each element event and for each text event, addressable by the element identifier assigned to the event, wherein the element descriptor for an element event includes a combination of the second through seventh means for storing for the element.

4. The computer program product as set forth in claim 3, wherein the indication of the parent, child and sibling elements in each of the means for storing is the element identifier of the element event provided in response to detection of the parent, child and sibling elements.

5. The computer program product as set forth in claim 4, wherein the means for assigning element identifiers assigns numbers in a sequence for the sequence of events provided by the means for parsing.

6. The computer program product of claim 1, wherein the computer program logic further defines:

means for parsing the digital document to provide a sequence of element events in response to detection of elements and text events in response to detection of text content;

means for assigning a unique element identifier to each element event and to each text event;

means for constructing the type name of each element from the descriptive markup defining the element;

means for generating an element descriptor for each element event and for each text events addressable by the element identifier assigned to the event, wherein the element descriptor for an element event includes a combination of the second through fourth means for storing for the element.

7. The computer program product of claim 1, wherein the computer program logic further defines:

means for accessing the second through fourth means for storing for an element using a unique identifier for the element.

8. The computer program product of claim 1, wherein the computer program logic further defines:

means for storing an index of at least the text content of the digital document including a record for each word in the text content, addressable by an indication of the word, and for storing an indication of the element containing the text content containing the word, and for storing an indication of the number of occurrences in the element of the word.

9. The computer program product of claim 8, wherein the descriptive markup for an element may include an attribute and wherein the index further includes a record for each word in the attribute.

10. The computer program product of claim 1, wherein the computer program logic further defines:

for selected elements, a record for storing the element identifier of the element and the element identifier of a next element in the digital document which is not contained within the element.

11. The computer program product of claim 10, wherein the record for an element includes an indication of the type name of the element.

12. The computer program product of claim 1,

wherein the descriptive markup for an element may include an attribute;

and

wherein the element descriptor of the element stores an indication of the attribute as the indication of any text content contained wit the element including the attribute.