Parsing method

• US 20070016398A1
• Filed: 07/13/2006
• Published: 01/18/2007
• Est. Priority Date: 07/15/2005
• Status: Abandoned Application

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Buchholz, Sabine
• Application Number:
  US11/485,299
• Publication Number:
  US 20070016398A1
• Time in Patent Office: Days
• US Class Current: 704/4
• CPC Class Codes: G06F 40/205 Parsing

Abstract

A method of parsing natural language comprising the steps of: a) receiving a tokenised and part-of-speech tagged utterance comprising n tokens b) for the first token; i) calculating a partial parse consisting of one dependency relation by assigning a role and a head for the first token; ii) calculating the probability of the partial parse from step (i) iii) repeating steps (b)(i) and (b)(ii) for all possible heads and roles of the token and storing the A most likely resulting partial parses c) advancing to the next successive token and, for each of the A partial parses from the previous step: iv) calculating a possible next extension to the partial parse by one dependency relation v) calculating the probability of the extended partial parse from (c)(i) vi) repeating steps (c)(i) and (c)(ii) for all possible heads and roles of the token and storing the A most likely resulting partial parses d) repeating step (c) for each successive token until all n tokens have been parsed.

Claims

1. A method of parsing natural language comprising the steps of:

a) receiving a tokenised and part-of-speech tagged utterance comprising n tokens

b) for the first token;

i) calculating a partial parse consisting of one dependency relation by assigning a role and a head for the first token;

ii) calculating the probability of the partial parse from step (i)

iii) repeating steps (b)(i) and (b)(ii) for all possible heads and roles of the token and storing the A most likely resulting partial parses

c) advancing to the next successive token and, for each of the A partial parses from the previous step;

i) calculating a possible next extension to the partial parse by one dependency relation

ii) calculating the probability of the extended partial parse from (c)(i)

iii) repeating steps (c)(i) and (c)(ii) for all possible heads and roles of the token and storing the A most likely resulting partial parses

d) repeating step (c) for each successive token until all n tokens have been parsed.

2. A method of parsing as claimed in claim 1 wherein each partial parsing calculation step includes checking that the possible dependency relation does not result in a dependency cycle.

3. A method of parsing as claimed in claim 1 wherein the information that is stored for each partial parse comprises the probability of the parse, the role of each token and the position of each token'"'"'s head.

4. A method as claimed in claim 1 wherein only projective parses are calculated.

5. A method as claimed in claim 4 wherein the information that is stored for each partial parse comprises the probability of the parse, the role of each token, the position of each token'"'"'s head and the distance to the leftmost left child of each token.

6. A method of parsing as claimed in claim 1 wherein steps (b)(ii) and (c)(ii) further include calculating left and right STOP child probabilities.

7. A data processing program for execution in a data processing system comprising software code portions for performing a method according to claim 1 when said program is run on said computer.

8. A computer program product stored on a computer usable medium, comprising computer readable program means for causing a computer to perform a method according to claim 1 when said program is run on said computer.

9. A system comprising means adapted for carrying out the steps of the method according to claim 1.