Data processing system and method for generating a representation for and for representing electronically published structured documents

• US 5,708,806 A
• Filed: 06/07/1995
• Issued: 01/13/1998
• 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: DeRose, Steven, Vogel, Jeffrey
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): Homere, Jean Raymond
• Application Number:
  US08/488,547
• Time in Patent Office: 951 Days
• Field of Search: 395/600, 395/616, 395/942, 395/935, 395/615, 395/613, 395/776, 395/779, 364/DIG. 1
• US Class Current: 1/1
• 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 storing a representation of an electronic document, including first means for storing the electronic document, the electronic 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 data processing system comprising:

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 data processing system as set forth in claim 1, further comprising:

fifth means for storing the text content of the electronic 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 markup element.

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

means for parsing the electronic 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 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 data processing system 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 data processing system 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 data processing system of claim 1, further comprising:

means for parsing the electronic 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 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 fourth means for storing for the element.

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

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

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

means for storing an index of at least the text content of the electronic 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 data processing system 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 data processing system of claim 1, further comprising:

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

11. The data processing system of claim 10, wherein the record for an element includes an indication of the type name of the element.

12. The data processing system 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 within the element including the attribute.

13. A method for generating a representation of an electronic document, the electronic 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, a right sibling element, and wherein at least one element contains text content, the method comprising the steps of:

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.

14. The method as set forth in claim 13, 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.

15. The method as set forth in claim 14, 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.

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

17. The method of claim 13, further comprising the step of:

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

18. The method of claim 13, 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.

19. The method of claim 18, 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.

20. The method of claim 13, 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 electronic document which is not contained within the element.

21. The method of claim 20, wherein the record for an element includes an indication of the type name of the element.

22. The method of claim 13,

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.

23. A data processing system for constructing a representation of an electronic document, the electronic 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 data processing system comprising:

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.

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

means for storing the text content of the electronic document separate from the electronic 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.

25. The data processing system of claim 23, 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.

26. The data processing system of claim 23, wherein the means for assigning element identifiers assigns numbers according to a sequence matching the sequence of events provided by the parser.

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

means for indexing at least the text content of the electronic 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.

28. The data processing system of claim 27, 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.

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

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

30. The data processing system of claim 29 wherein the record for an element includes an indication of the type name of the element.

31. The data processing system of claim 23,

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.

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

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

33. A method for constructing a representation of an electronic document, the electronic 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 method comprising the steps of:

parsing the electronic 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.

34. The method of claim 33 further comprising the step of storing the text content of the electronic document separate from the electronic 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.

35. The method of claim 33 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.

36. The method of claim 33 wherein the step of assigning element identifiers includes assigning sequential numbers according to the sequence of events provided by the step of parsing.

37. The method of claim 33 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.

38. The method of claim 37 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.

39. The method of claim 33 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 electronic document which is not contained within the element.

40. The method of claim 39 wherein the record for an element includes an indication of the type name of the element.

41. The method of claim 33,

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.

42. The method of claim 33, further comprising the step of:

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

43. A digital information product containing an electronic document, wherein the electronic document has 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, digital information product comprising a computer-readable medium on which computer-readable signals are stored, wherein the computer-readable signals define an element directory containing an element descriptor for each element wherein each element descriptor is accessible using an identifier of the element descriptor for an element and includes a value indicative of a parent element for each element having a parent element, a value indicative of a first child element for each element having a child element, and a value indicative of a left sibling element for each element having a left sibling element.

44. The digital information product of claim 43,

wherein the element descriptor of each element further includes a value indicative of any last child element for the element.

45. The digital information product of claim 44,

wherein the element descriptor of each element further includes a value indicative of any right sibling element for the element.

46. The digital information product of claim 43,

wherein the element descriptor of each element further includes a value indicative of any right sibling element for the element.

47. The digital information product of claim 43,

wherein the element descriptor of each element further includes a value indicative of any text contained within the element.

48. The digital information product of claim 47, wherein the text content of the electronic document is defined by the computer-readable signals separately form the element directory and wherein for each element the value indicative of the text content contained within the element is a value indicative of the location of the text content contained within the element in the text content stored in the computer-readable medium.

49. The digital information product of claim 43,

wherein the element descriptor of each element further includes a value indicative of the type name for the element.

50. The digital information product of claim 43, wherein the computer-readable signals further define an index of the text content of the electronic document including a record for each word in the text content, addressable by an indication of the word, wherein the record includes an indication of each element containing the word and an indication of a number of occurrences of the word in the element.

51. The digital information product of claim 50, 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.

52. The digital information product of claim 43, a table of contents including,

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

53. The digital information product of claim 52, wherein the record for an element includes an indication of the type name of the element.

54. A data processing system for providing access to an electronic document, wherein the electronic document has 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 data processing system comprising:

a computer-readable medium on which computer-readable signals are stored, wherein the computer-readable signals define an element directory containing an element descriptor for each element wherein each element descriptor is accessible using an identifier of the element descriptor for an element includes a value indicative of a parent element for each element having a parent element, a value indicative of a first child element for each element having a child element, and a value indicative of a left sibling element, for each element having a left sibling element; and

means for accessing the computer-readable medium using an identifier of an element to retrieve the element descriptor of the element.