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

• US 6,101,511 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: Vogel, Jeffrey, DeRose, Steven
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US09/352,588
• Time in Patent Office: 392 Days
• Field of Search: 707/3, 707/100, 707/104, 707/513, 707/514, 707/531, 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 computer program product for constructing a representation of a 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 may have a child element, a left sibling element and a right sibling element, and wherein at least one element contains text content, the computer program product comprising:

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

a parser for providing a sequence of element events in response to detection of elements and text events in response to text content;

means, responsive to an element event, for assigning a unique element identifier to the element event;

means, responsive to an element event, for constructing the type name for the element event from the descriptive markup defining the element event; and

means, responsive to an element event, for constructing an element descriptor, addressable by the element identifier assigned to the element event, wherein the element descriptor stores an indication of the type name and any parent element, first child element, last child element, left sibling element, right sibling element, and text content contained within the element.

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

means for storing the text content of the digital document separate from the digital document and without descriptive markup, and

wherein the indication of the text content contained within an element stored in the element descriptor of the element is indicative of the location of the text content in the separate means for storing.

3. The computer program product of claim 1, wherein the indications of any parent, child or sibling elements in the element descriptors are indicative of the element identifiers of the parent, child or sibling elements.

4. The computer program product of claim 1, wherein the means for assigning element identifiers assigns numbers according to a sequence matching the sequence of events provided by the parser.

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

means for indexing at least the text content of the digital document including means for providing a sequence of word events in response to detection of each word in the text content;

means, responsive to a word event, for constructing a record, addressable by an indication of the detected word, and for storing an indication of the element containing the text content containing the detected word, and for storing an indication of a number of occurrences in the element of the detected word.

6. The computer program product of claim 5, wherein the descriptive markup for an element may include an attribute, and wherein the means for indexing at least the text content further indexes the attribute.

7. 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.

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

9. The computer program product of claim 1,

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

and

wherein the means for constructing an element descriptor stores an indication of the attribute as the indication of any text content contained within the element including the attribute.

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

means for accessing the element descriptor of an element using the element identifier assigned to the element.

11. A process for generating a digital information product comprising computer data signals defining a representation of a 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 type name and may have a child element, a left sibling element, a right sibling element, and wherein at least one element contains text content, the process comprising:

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

assigning, in response to an element event, a unique element identifier to each element event;

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

generating an element descriptor for each element, addressable by the unique element identifier assigned to the element, wherein the element descriptor stores an indication of any parent element, any first child element, and any left sibling element for the element, and encoding each element descriptor in a computer data signal.

12. The process as set forth in claim 11, wherein the element descriptor for an element includes an indication of the location of the text content, for each element containing text content, and, for each element, the type name of the element.

13. The process as set forth in claim 12, wherein the indication of the parent, child and left sibling elements in each element descriptor is the element identifier of the parent, child and left sibling elements.

14. The process as set forth in claim 13, wherein the assigned unique element identifiers are sequential numbers assigned according to the sequence of events provided by the step of parsing.

15. The process of claim 11, further comprising the step of:

accessing the element descriptor of an element using the element identifier assigned to the element.

16. The process of claim 11, further comprising the steps of:

indexing at least the text content of the document to provide a sequence of word events in response to detection of a word in the text content;

constructing, in response to a word event, a record, addressable by an indication of the detected word, for storing an indication of the element containing the text content containing the detected word, and for storing an indication of the number of occurrences of the detected word in the element.

17. The process of claim 16, wherein the descriptive markup for an element may include an attribute, and wherein the step of for indexing at least the text content further includes indexing the attribute.

18. The process of claim 11, further comprising the step of:

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

19. The process of claim 18, wherein the record for an element includes an indication of the type name of the element.

20. The process of claim 11,

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

and

wherein the step of constructing an element descriptor includes storing an indication of the attribute as the indication of any text content of the element containing the attribute.

21. A process for constructing a digital information product comprising computer data signals defining a representation of a 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 may have a child element, a left sibling element and a right sibling element, and wherein at least one element contains text content, the process comprising:

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;

assigning a unique element identifier to each element;

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

constructing, for each element, an element descriptor addressable by the element identifier assigned to the element, wherein the element descriptor stores an indication of the type name and any parent element, first child element, last child element, left sibling element, right sibling element, and text content contained within the element, and encoding each element descriptor in a computer data signal.

22. The process of claim 21 further comprising the step of storing the text content of the digital document separate from the digital document and without descriptive markup, and wherein the indication of the text content contained within an element stored in the element descriptor of the element is indicative of the location of the text content contained within the element in the separately stored text content.

23. The process of claim 21 wherein the indications of any parent, child or sibling elements in the element descriptors are indicative of the element identifiers of the parent, child or sibling elements.

24. The process of claim 21 wherein the step of assigning element identifiers includes assigning sequential numbers according to the sequence of events provided by the step of parsing.

25. The process of claim 21 further comprising the steps of:

indexing at least the text content of the document to provide a sequence of word events in response to detection of a word in the text content;

constructing, in response to a word event, a record, addressable by an indication of the detected word, for storing an indication of the element containing the text content containing the detected word, and for storing an indication of the number of occurrences of the detected word in the element.

26. The process of claim 25 wherein the descriptive markup for an element may include an attribute, and wherein the step of for indexing at least the text content further includes indexing the attribute.

27. The process of claim 21, further comprising the step of,

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

28. The process of claim 27, wherein the record for an element includes an indication of the type name of the element.

29. The process of claim 21,

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

and

wherein the step of constructing an element descriptor includes storing an indication of the attribute as the indication of any text content of the element containing the attribute.

30. The process of claim 21, further comprising the step of:

accessing the element descriptor of an element using the element identifier assigned to the element.