Method and apparatus for recognizing multiword expressions

• US 7,346,511 B2
• Filed: 12/13/2002
• Issued: 03/18/2008
• Est. Priority Date: 12/13/2002
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Poirier, Herve, Privault, Caroline
• Primary Examiner(s): Edouard; Patrick N.
• Assistant Examiner(s): YEN, ERIC L
• Application Number:
  US10/248,057
• Publication Number:
  US 20040117184A1
• Time in Patent Office: 1,922 Days
• Field of Search: 704/251, 704/254, 704/255, 704/9
• US Class Current: 704/255
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/268 Morphological analysis

Abstract

Words of an input string are morphologically analyzed to identify their alternative base forms and parts of speech. The analyzed words of the input string are used to compile the input string into a first finite-state network. The first finite-state network is matched with a second finite-state network of multiword expressions to identify all subpaths of the first finite-state network that match one or more complete paths in the second finite-state network. Each matching subpath of the first finite-state network and path of the second finite-state network identify a multiword expression in the input string. The morphological analysis is performed without disambiguating words and without segmenting the input string into sentences in the input string to compile the first finite-state network with at least one path that identifies alternative base forms or parts of speech of a word in the input string.

Claims

1. A method for identifying multiword expressions in an input string, comprising:

morphologically analyzing words of the input string to replace words identified in the input string with their alternative base forms and parts of speech;

using the analyzed words of the input string to compile the input string into a first finite-state network;

matching the first finite-state network with a second finite-state network of multiword expressions to identify all subpaths of the first finite-state network that match one or more complete paths in the second finite-state network;

each matching subpath of the first finite-state network and complete path of the second finite-state network identifying a multiword expression in the input string;

wherein the analyzing is performed without disambiguating words in the input string to compile the first finite-state network with at least one path that identifies alternative base forms or parts of speech of a word in the input string; and

wherein said matching comprises;

i) generating a set of states comprising one state from the first finite-state network and one state from the second finite-state network;

ii) pushing at least the set of states onto a stack, in order to record start states of potentially matching subnetworks of the first and second finite-state networks; and

iii) recording start states of potentially matching subnetworks of the first and second finite-state networks.

2. The method according to claim 1, wherein said morphological analysis is performed without segmenting the input string into sentences to permit multiword expressions to span multiple sentences.

3. The method according to claim 2, wherein the input string is a plurality of sentences.

4. The method according to claim 2, wherein the first finite-state network is an automaton and the second finite-state network is a transducer with subnets.

5. The method according to claim 2, further comprising maintaining the order of states and transitions in the first finite-state network consistent with:

(a) the order of the words in the input string; and

(b) the order in which word senses are assigned during morphological analysis.

6. The method according to claim 5, further comprising:

recording each match between the first finite-state network and the second finite-state network as a sequence of symbols from the second finite-state network;

identifying a path number in the second finite-state network that corresponds to each sequence of symbols from the second finite-state network determined by a match of a complete path in the second finite-state network with a subpath in the first finite state network;

determining each multiword expression matching the input string with each path number identified;

wherein the path number is computed without accounting for contributions to the path number from matching factorized subnets of the second finite-state network.

7. The method according to claim 6, wherein the second finite-state network is non-circular.

8. The method according to claim 6, further comprising retrieving information related to each multiword expression matching the input string using its identified path number.

9. The method according to claim 6, further comprising outputting inflected parts of the input string corresponding to each multiword expression matching the input string using its identified path number.

10. The method according to claim 1, further comprising building the second finite-state network by:

encoding each of a plurality of multiword expressions into a regular expression that defines derivative forms of each multiword expression;

compiling with factorization each of the plurality of regular expressions into a set of finite-state networks;

performing a union of the finite-state networks in the set of finite-state networks to define the second finite-state network.

11. An apparatus for identifying multiword expressions in an input string, comprising:

a morphological analyzer for morphologically analyzing words of the input string to replace words identified in the input string with their alternative base forms and parts of speech;

a finite-state compiler for using the analyzed words of the input string to compile the input string into a first finite-state network;

an expression identifier for matching the first finite-state network with a second finite-state network of multiword expressions to identify all subpaths of the first finite-state network that match one or more complete paths in the second finite-state network;

each matching subpath of the first finite-state network and path of the second finite-state network identifying a multiword expression in the input string;

wherein said morphological analyzers performs morphological analysis without disambiguating words in the input string to compile the first finite-state network with at least one path that identifies alternative base forms or parts of speech of a word in the input string and wherein said matching comprises;

i) generating a set of states comprising one state from the first finite-state network and one state from the second finite-state network;

ii) pushing at least the set of states onto a stack, in order to record start states of potentially matching subnetworks of the first and second finite-state networks; and

iii) recording start states of potentially matching subnetworks of the first and second finite-state networks.

12. The apparatus according to claim 11, wherein said morphological analyzer performs morphological analysis without segmenting the input string into sentences to permit multiword expressions to span multiple sentences.

13. The apparatus according to claim 12, wherein the input string is a plurality of sentences.

14. The apparatus according to claim 12, wherein the first finite-state network is an automaton and the second finite-state network is a transducer with subnets.

15. The apparatus according to claim 12, wherein the expression identifier maintains the order of states and transitions in the first finite-state network consistent with:

(a) the order of the words in the input string; and

(b) the order in which word senses are assigned during morphological analysis.

16. The apparatus according to claim 15, wherein the expression identifier further comprises:

means for recording each match between the first finite-state network and the second finite-state network as a sequence of symbols from the second finite-state network;

means for identifying a path number in the second finite-state network that corresponds to each sequence of symbol from the second finite-state network determined by a match of a complete path in the second finite-state network with a subpath in the first finite state network;

means for determining each multiword expression matching the input string with each path number identified;

wherein the path number is computed without accounting for contributions to the path number from matching factorized subnets of the second finite-state network.

17. The apparatus according to claim 16, wherein the expression identifier retrieves information related to each multiword expression matching the input string using its identified path number.

18. The apparatus according to claim 16, further comprising outputting inflected parts of the input string corresponding to each multiword expression matching the input string using its identified path number.

19. The apparatus according to claim 11, further comprising building the second finite-state network by:

encoding each of a plurality of multiword expressions into a regular expression that defines derivative forms of each multiword expression;

compiling with factorization each of the plurality of regular expressions into a set of finite-state networks;

performing a union of the finite-state networks in the set of finite-state networks to define the second finite-state network.

20. An article of manufacture for use in a machine comprising:

a) a memory;

b) instructions stored in the memory for identifying multiword expressions in an input string, the instructions adapted to perform a method comprising;

morphologically analyzing words of the input string to replace words identified in the input string with their alternative base forms and parts of speech;

using the analyzed words of the input string to compile the input string into a first finite-state network;

matching the first finite-state network with a second finite-state network of multiword expressions to identify all subpaths of the first finite-state network that match one or more complete paths in the second finite-state network;

each matching subpath of the first finite-state network and path of the second finite-state network identifying a multiword expression in the input string;

wherein said morphological analysis is performed without disambiguating words in the input string to compile the first finite-state network with at least one path that identifies alternative base forms or parts of speech of a word in the input string and wherein said matching comprises;

i) generating a set of states comprising one state from the first finite-state network and one state from the second finite-state network;

ii) pushing at least the set of states onto a stack, in order to record start states of potentially matching subnetworks of the first and second finite-state networks; and

iii) recording start states of potentially matching subnetworks of the first and second finite-state networks.