System for normalizing a discourse representation structure and normalized data structure

• US 8,412,515 B2
• Filed: 10/15/2007
• Issued: 04/02/2013
• Est. Priority Date: 01/14/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Barklund, Par Jonas, Calcagno, Michael V.
• Primary Examiner(s): He, Jialong
• Application Number:
  US11/872,435
• Publication Number:
  US 20080033715A1
• Time in Patent Office: 1,996 Days
• Field of Search: 704 1- 10
• US Class Current: 704/9
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation

Abstract

A system and method for normalizing a discourse representation structure (DRS) are provided. The elements of the structure are rewritten and sorted in a way such that structures which may appear different but are nonetheless equivalent can be associated with the same, normalized representation. Various embodiments can also include a data structure for a DRS. The DRS may be represented by an array of boxes, each having a set of elements which in turn has a predefined structure suitable for representing a wide variety of linguistic information.

Claims

1. A computer readable storage medium storing instructions, which, when executed by a computer, perform a method for representing a discourse input, the method comprising:

receiving a discourse input; and

parsing the discourse input to generate a discourse representation data structure (DRS) that represents entities in the discourse input and linguistic relationships of the entities, the DRS comprising an array of boxes, each box including a set of box elements with associated arguments having markers, wherein the box elements are normalized by deleting unused boxes from the DRS and are initially sorted in a preliminary order based on a box and box element normal form regardless of the markers, and wherein the markers are in a normalized form in the DRS, and the boxes and box elements are sorted based on the preliminary order and based on the marker normal form to obtain the DRS in a normal form, the box elements and associated arguments in the DRS in the normal form including a semantic representation of semantic content of the discourse input.

2. The computer readable storage medium of claim 1 and the DRS further comprising:

a string representative of the DRS.

3. The computer readable storage medium of claim 1 and the DRS further comprising:

an integer number of boxes in the DRS indicative of a length of the array of boxes.

4. The computer readable storage medium of claim 3 wherein the set of box elements is embodied as a vector of box elements and further comprising:

an integer number of box elements in the DRS indicative of a length of the vector of box elements.

5. The computer readable storage medium of claim 4 and the DRS further comprising:

a vector map that includes a vector of lists of pairs of integers in the DRS; and

an integer number of markers in the DRS, indicative of a length of the vector map.

6. The computer readable storage medium of claim 1 wherein each box in the array of boxes comprises:

a DRS pointer field that includes a pointer to the DRS containing the box.

7. The computer readable storage medium of claim 6 wherein each box in the array of boxes comprises:

an integer number of elements in the box.

8. The computer readable storage medium of claim 7 wherein each box in the array of boxes comprises:

a vector of element indices having a length given by the integer number of elements in the box.

9. The computer readable storage medium of claim 1 wherein each box element in the set of box elements comprises:

a kind field indicative of a kind of box element; and

a semantic kind field indicative of a semantic kind of the box element.

10. The computer readable storage medium of claim 9 wherein each box element further comprises:

an integer number of box element arguments in the box element; and

a vector of box element arguments in the box element, having a length indicated by the integer number of box element arguments.

11. The computer readable storage medium of claim 10 wherein each box element further comprises:

a string representative of the box element.

12. The computer readable storage medium of claim 10 wherein each box element further comprises:

a semantic node value indicative of a semantic node in an external semantic domain corresponding to the box element.

13. The computer readable storage medium of claim 1 wherein each box element argument comprises:

an argument kind field indicative of a kind of the box element argument.

14. The computer readable storage medium of claim 13 wherein each box element argument comprises:

an argument identification field including an identifier of the box element argument.

15. The computer readable storage medium of claim 13 wherein each box element argument comprises:

a data value field including a data value associated with the box element argument.