System for normalizing a discourse representation structure and normalized data structure

• US 7,295,966 B2
• Filed: 01/14/2002
• Issued: 11/13/2007
• Est. Priority Date: 01/14/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Calcagno, Michael V., Barklund, Pär Jonas
• Primary Examiner(s): {hacek over (S)}mits; Talivaldis Ivars
• Application Number:
  US10/047,472
• Publication Number:
  US 20030171915A1
• Time in Patent Office: 2,129 Days
• Field of Search: 704/9, 704/7
• US Class Current: 704/9
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation

Abstract

The present invention is a system and method for normalizing a discourse representation structure (DRS). 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. The present invention can also include a data structure for a DRS. The DRS is 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 method, implemented at least in part by a computing system, of normalizing a discourse representation structure (DRS) that includes boxes with box elements and box element arguments having markers, box identifiers and data values, the method comprising:

receiving the DRS;

normalizing a form in which boxes and box elements are represented in the DRS by deleting unused boxes from the DRS;

sorting the boxes and box elements, based on the box and box element normal form and regardless of the markers, to obtain a preliminary ordering;

normalizing a form in which markers are represented in the DRS;

sorting the boxes and box elements based on the preliminary ordering and based on the marker normal form, to generate a DRS in a normal form; and

providing an output comprising the DRS in the normal form.

2. The method of claim 1 wherein normalizing the form in which box elements are represented comprises:

deleting unused box elements from the DRS.

3. The method of claim 2 wherein normalizing the form in which boxes are represented comprises:

re-numbering the boxes with consecutive indices.

4. The method of claim 3 wherein normalizing the form in which box elements are represented comprises:

re-numbering the box elements with consecutive identifiers.

5. The method of claim 4 wherein sorting the boxes and box elements, based on the box and box element normal forms and regardless of the markers, comprises:

lexicographically ordering the boxes and box elements based on the indices and identifiers to obtain lexicographically ordered boxes and box elements.

6. The method of claim 5 wherein sorting the boxes and box elements, based on the box and box element normal forms and regardless of the markers, comprises:

updating the boxes to refer to re-numbered box elements.

7. The method of claim 6 wherein sorting the boxes and box elements, based on the box and box element normal forms and regardless of the markers, comprises:

updating the box elements to refer to re-numbered boxes.

8. The method of claim 7 wherein normalizing the form in which markers are represented in the DRS comprises:

generating a mapping between each marker and a list identifying a box and box element containing the marker.

9. The method of claim 8 wherein normalizing the form in which markers are represented in the DRS comprises:

generating an inverse mapping between the list identifying a box and box element containing a marker and each marker.

10. The method of claim 9 wherein normalizing the form in which markers are represented in the DRS comprises:

re-numbering the markers with consecutive marker values.

11. The method of claim 10 wherein normalizing the form in which markers are represented in the DRS comprises:

updating the box elements to refer to the re-numbered markers.

12. The method of claim 11 wherein sorting the boxes and box elements based on the preliminary ordering and based on the marker normal forms comprises:

sorting the lexicographically ordered boxes and box elements based on the re-numbered markers to obtain a normalized DRS.

13. The method of claim 12 and further comprising:

generating a string representative of the normalized DRS.