Processing natural language text using autonomous punctuational structure

• US 5,111,398 A
• Filed: 11/21/1988
• Issued: 05/05/1992
• Est. Priority Date: 11/21/1988
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Smith, Brian C., Stansbury, H. Tayloe, Nunberg, Geoffrey D., Abbott, Curtis
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Kibby, Steven
• Application Number:
  US07/274,158
• Time in Patent Office: 1,261 Days
• Field of Search: 364/419, 364/200 MS File, 364/900 MS File, 364/300, 364/225.6, 364/225.8, 364/226.1, 364/226.4, 364/920.4
• US Class Current: 704/9
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

A technique for processing natural language text uses a data structure that includes structure data in the text data. The structure data indicates an autonomous punctuational structure of the text, a punctuational structure that is independent of the lexical content of the text and therefore can be manipulated without considering the meaning of the words in the text. The data structure can be a tree in which each node has a textual type such as a paragraph, sentence, clause, phrase, or word. The data structure could alternatively be parallel data sequences, one with codes indicating the text'"'"'s characters and the other with codes indicating textual types. The data structure is produced and maintained using a grammar of textual types, indicating for each textual type the textual types of units into which it can properly be divided. During editing, a text sequence is generated by applying rendering rules to the data structure, and the text is presented to the user based on the text sequence. Prior to generating the text sequence, information relating to punctuational features is propagated through the data structure. User signals requesting editing operations are applied to modify the data structure using operations rules, and the user'"'"'s pointing or selecting signals are mapped onto the data structure. The modified data structure is checked with the grammar of textual types to ensure that it has an autonomous punctuational structure. A modified text sequence is then generated, and a modified text is displayed based on it.

Claims

1. A method comprising steps of:

storing first text data representing a first natural language text that includes a first set of words and a first set of punctuational features with positions relative to the first set of words;

the first text data including first structure data indicating types of a first set of text units at the boundaries of which the first set of punctuational features are positioned, the first structure data further indicating nesting relationships between the first set of words and the first set of text units such that the first set of punctuational features and their positions relative to the first set of words can be determined from the first structure data; and

operating on the first text data to produce second text data representing a second natural language text that is different from the first natural language text;

the second natural language text including a second set of words and a second set of punctuational features with positions relative to the second set of words;

the second text data including second structure data indicating types of a second set of text units at the boundaries of which the second set of punctuational features are positioned, the second structure data further indicating nesting relationships between the second set of words and the second set of text units such that the second set of punctuational features and their positions relative to the second set of words can be determined from the second structure data.

2. The method of claim 1 in which the first set of words and the second set of words include the same words, first set of words being in a different order than the second set of words, the first set of punctuational features being different than the second set of punctuational features.

3. The method of claim 2 in which the first text data has a plurality of levels of nodes, each node representing a respective one of the first set of text units;

the levels of nodes including a top level and at least one lower level below the top level, the first structure data including first linking data indicating a first set of links between the nodes;

the step of operating on the first text data to produce the second text data comprising a substep of modifying the first linking data to produce second linking data, the second linking data indicating a second set of links different than the first set of links.

4. The method of claim 1 in which the step of operating on the first text data to produce the second text data comprises a substep of determining whether the second structure data indicate types and nesting relationships such that the second set of punctuational features and their positions relative to the second set of words can be determined from the second structure data.

5. The method of claim 4 in which the determining substep comprises a substep of applying a set of rules to the second structure data, each rule indicating, for any text unit of one of the types, types of other text units into which the text unit can be divided.

6. A method comprising steps of:

storing text data representing a natural language text that includes words and punctuational features with positions relative to the words;

the text data including structure data indicating types of text units at the boundaries of which the punctuational features are positioned, the structure data further indicating nesting relationships between the words and the text units such that the punctuational features and their positions relative to the words can be determined from the structure data; and

operating on the text data to produce codes indicating the words and the punctuational features in the natural language text;

the step of operating on the text data comprising a substep of determining the punctuational features and their positions relative to the words from the structure data;

the codes produced by the step of operating on the text data being in a sequence such that the codes indicate that the punctuational features are in their positions relative to the words as determined from the structure data.

7. The method of claim 6 in which the step of operating on the text data comprises a substep of applying a rule from a set of rules to the structure data.

8. The method of claim 7 in which the step of operating on the text data further comprises a substep of including punctuation codes in the code sequence in accordance with the structure data included in the text data.

9. The method of claim 8 in which the step of operating on the text data further comprises, prior to the substep of including the punctuation codes, a substep of propagating information relating to punctuational features through the text data.

10. The method of claim 6, further comprising steps of:

presenting the natural language text to a user based on the code sequence;

receiving signals from the user, the signals including selection data indicating a selected part of the presented natural language text; and

mapping the selection data onto the text data to identify a selected part of the text data.

11. The method of claim 10 in which the signals received in the receiving step further include operation data indicating an operation to be performed on the selected part of the presented natural language text;

the method further comprising a step of performing the indicated operation by modifying the text data to produce modified text data representing a modified natural language text that is different from the natural language text represented by the text data prior to the step of performing the indicated operation.

12. The method of claim 11 in which the modified natural language text includes a modified set of words and a modified set of punctuational features with positions relative to the modified set of words;

the modified text data including modified structure data indicating types of the modified set of text units at the boundaries of which the modified set of punctuational features are positioned, the modified structure data further indicating nesting relationships between the modified set of words and the modified set of text units;

the step of performing the indicated operation further comprising a substep of determining whether the modified structure data indicate types and nesting relationships such that the modified set of punctuational features and their positions relative to the modified set of words can be determined from the modified structure data.

13. The method of claim 11, further comprising the steps of:

accessing the modified text data;

regenerating a modified code sequence from the modified text data;

the modified code sequence including codes that indicate words and punctuational features in the modified natural language text;

the regenerating step comprising a substep of including punctuation codes in the modified code sequence in accordance with the structure data; and

presenting a modified natural language text to the user based on the modified code sequence.

14. The method of claim 11 in which the signals received in the receiving step further include position data indicating a position within the presented natural language text at which to perform the indicated operation;

the performing step comprising mapping the position data onto the text data to identify a position within the text data corresponding to the position within the presented natural language text and performing the indicated operation at that position.

15. A method comprising steps of:

obtaining codes representing a natural language text that includes words and punctuational features, the codes being in a sequence such that the codes indicate that the punctuational features are in positions relative to the words; and

operating on the codes to produce text data representing the natural language text;

the text data including structure data indicating types of text units at the boundaries of which the punctuational features are positioned, the structure data further indicating nesting relationships between the words and the text units such that the punctuational features and their positions relative to the words as indicated by the codes can be determined from the structure data.

16. The method of claim 15 in which the step of operating on the codes comprises a substep of applying a set of rules to the codes representing the natural language text to obtain the structure data.

17. The method of claim 16 in which the applying substep comprises a substep of analyzing the natural language text into text units, each text unit having a respective one of the types:

the step of operating on the codes further comprising a substep of including in the structure data, for each text unit, a structure code indicating its type.

18. The method of claim 15 in which the step of operating on the codes comprises a substep of analyzing the natural language text into the text units.

19. A data structure produced for use in a system that includes:

memory for storing the data sturcture; and

a processor connected for accessing the data structure when stored in the memory;

the data structure comprising text data representing a natural language text that includes words and punctuational features with positions relative to the words;

the text data comprising structure data indicating types of text units at the boundaries of which the punctuational features are positioned, the structure data further indicating nesting relationships between the words and the text units such that the processor can access the text data and use the structure data to determine the punctuational features and their positions relative to the words when the data structure is stored in the memory.

20. The data structure of claim 19 in which the structure data comprises, for each text unit, a structure code indicating its type.

21. The data structure of claim 19 in which the text data has a plurality of levels of nodes, each node representing a respective one of the text unit;

the level of nodes including a top level and at least one lower level below the top level, the structure data including linking data linking a first node at one of the lower levels to a second node at a level above that lower level, the second node'"'"'s respective text unit including the first node'"'"'s respective text unit.

22. The data structure of claim 21 in which the levels of nodes and the linking data form a tree.

23. The data structure of claim 19 in which the text data includes a sequence of text data unit that indicate words in the natural language text and a sequence of sturcture data units, each structure data unit being parallel to a respective one of the text data units and including a part of the structure data relating to the respective text data unit.

24. A system comprising:

memory for storing text data representing a natural language text that includes words and punctuational features with positions relative to the words;

the text data including structure data indicating types of text units at the boundaries of which the punctuational features are positioned, the structure data further indicating nesting relationships between the words and the text units such that the structure data can be used to detrermine the punctuational features and their positions relative to the words; and

a processor connected for accessing the text data when stored in the memory, the processor comprising means for using the structure data to determine the punctuational features and their positions relative to words.

25. The system of claim 24 further commprising a stored set of rules, each rule indicating, for any text unit of one of the types, types of other text units into which the text unit can be divided;

the means for using the structure data determining the punctuational features and their positions relative to the words by applying rules from the stored set of rules.

26. The system of lcaim 24 in which the processor further comprises means for regenerating the natural language text from the text data by producing a sequence of codes including punctuation mark codes indicating the punctuational features as determined by the means for using the structure data.

27. The system of claim 26 further comprising a display and a user input device;

the processor further comprising means for representing the regenerated natural language text to a user on the display and means for receiving signals from the user through the user input device.

28. The system of claim 27 in which the signals include selection data indicating a selected part of the regenerated natural language text;

the processor further comprising means for mapping the selection data onto the text data to identify a selected part of the text data.

29. The system of clim 28 in which the signals further include operation data indicating operation to be performed on the selected part of the regenerated natural language text;

the processor further comprising means for performing the indicated operation by modifying the text data by modifying the structure data.

30. The system of claim 29 in which the processor further comprises means for generating a modified natural language text from the modified text data by producing a modified sequence of codes including punctuation mark codes indicating punctuational features as determined from the modified structure data by the means for using the sturcture data.

31. The system of claim 29 in which the signals further include position data indicating a position withiln the regenerated natural language text at which to perform the indicated operation;

the processor further comprising means for mapping the position data onto the text data to identify a position within the text data corresponding to the position within the regenerated natural language text, the means for performing the indicated operation performing the indicated operation at that position.