Method and apparatus for mapping multiword expressions to identifiers using finite-state networks

• US 7,552,051 B2
• Filed: 12/13/2002
• Issued: 06/23/2009
• 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): Dorvil; Richemond
• Assistant Examiner(s): YEN, ERIC L
• Application Number:
  US10/248,058
• Publication Number:
  US 20040128122A1
• Time in Patent Office: 2,384 Days
• Field of Search: 704/255, 704/251, 704/254, 704/9
• US Class Current: 704/255
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

Multiword expressions are mapped to identifiers using finite-state networks. Each of a plurality of multiword expressions is encoded into a regular expression. Each regular expression encodes a base form common to a plurality of derivative forms defined by ones of the multiword expressions. Each of the plurality of regular expressions is compiled with factorization into a set of finite-state networks. A union of the finite-state networks in the set of finite-state networks is performed to define a multiword finite-state network and a set of subnets. The multiword finite-state network and the set of subnets are traversed to identify a path corresponding to one of the plurality of multiword expressions, wherein only transitions originating from the multiword finite-state network are accounted for to ascertain a path number identifying a base form of the one of the plurality of multiword expressions.

Claims

1. A method for mapping multiword expressions to identifiers using finite-state networks, comprising:

encoding each of a plurality of multiword expressions into a regular expression;

each regular expression encoding a base form common to a plurality of derivative forms defined by ones of the multiword expressions;

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 a multiword finite-state network and a set of subnets, each subset comprising a distinct standard network having an associated distinct start state and an associated final state comprising an entry and exit point, respectively, comprising arcs and states distinct from arcs and states of the finite-state network;

traversing the multiword finite-state network and the set of subnets to identify a path corresponding to one of the plurality of multiword expressions;

wherein said traversing accounts for only transitions originating from the multiword finite-state network to ascertain a path number identifying a base form of the one of the plurality of multiword expressions; and

wherein said factorization comprises inserting an arc with a label in the multiword finite-state network at each appearance of a repeating subnet in the set of subnets, where each label is a reference to a subnet in the set of subnets.

2. The method according to claim 1, further comprising identifying information related to the one of the plurality of multiword expressions using the path number.

3. The method according to claim 2, wherein the information related to the one of the plurality of multiword expressions includes one of categorization information, frequency of use, style of use, pronunciation, nuances of use, a synonym, an antonym, and a translation.

4. The method according to claim 1, further comprising defining each of the plurality of multiword expressions using a sequence of symbols.

5. The method according to claim 4, wherein symbols in the sequence of symbols are one of alphanumeric characters, music notes, chemical formulations, biological formulations, and kanji characters.

6. The method according to claim 1, wherein the path corresponding to the one of the plurality of multiword expressions traversed through the multiword finite-state network and the set of subnets is unique.

7. The method according to claim 6, wherein the path number uniquely identifies the base form of the one of the plurality of multiword expressions.

8. The method according to claim 7, further comprising defining the path number of a base form common to a plurality of derivative forms defined by ones of the multiword expressions by transitioning through the multiword finite-state network without transition to any one the subnets in the set of subnets.

9. The method according to claim 1, wherein the multiword finite-state network is non-circular.

10. An apparatus for mapping multiword expressions to identifiers using finite-state networks, comprising:

means for encoding each of a plurality of multiword expressions into a regular expression;

each regular expression encoding a base form common to a plurality of derivative forms defined by ones of the multiword expressions;

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

means for performing a union of the finite-state networks in the set of finite-state networks to define a multiword finite-state network and a set of subnets, each subset comprising a distinct standard network having an associated distinct start state and an associated final state comprising an entry and exit point, respectively, comprising arcs and states distinct from arcs and states of the finite-state network;

means for traversing the multiword finite-state network and the set of subnets to identify a path corresponding to one of the plurality of multiword expressions;

wherein said traversing means accounts for only transitions originating from the multiword finite-state network to ascertain a path number identifying a base form of the one of the plurality of multiword expressions; and

wherein said factorization comprises inserting an arc with a label in the multiword finite-state network at each appearance of a repeating subnet in the set of subnet, where each label is a reference to a subnet in the set of subnets.

11. The apparatus according to claim 10, further comprising means for identifying information related to the one of the plurality of multiword expressions using the path number.

12. The apparatus according to claim 11, wherein the information related to the one of the plurality of multiword expressions includes one of categorization information, frequency of use, style of use, pronunciation, nuances of use, a synonym, an antonym, and a translation.

13. The apparatus according to claim 10, further comprising means for defining each of the plurality of multiword expressions using a sequence of symbols.

14. The apparatus according to claim 13, wherein symbols in the sequence of symbols are one of alphanumeric characters, music notes, chemical formulations, biological formulations, and kanji characters.

15. The apparatus according to claim 10, wherein the path corresponding to the one of the plurality of multiword expressions traversed through the multiword finite-state network and the set of subnets is unique.

16. The apparatus according to claim 15, wherein the path number uniquely identifies the base form of the one of the plurality of multiword expressions.

17. The apparatus according to claim 16, further comprising means for defining the path number of a base form common to a plurality of derivative forms defined by ones of the multiword expressions by transitioning through the multiword finite-state network without transition to any one the subnets in the set of subnets.

18. The apparatus according to claim 10, wherein the multiword finite-state network is non-circular.

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

a) a memory;

b) instructions stored in the memory for mapping multiword expressions to identifiers using finite-state networks, the instructions adapted to perform a method comprising;

encoding each of a plurality of multiword expressions into a regular expression;

each regular expression encoding a base form common to a plurality of derivative forms defined by ones of the multiword expressions;

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 a multiword finite-state network and a set of subnets, each subset comprising a distinct standard network having an associated distinct start state and an associated final state comprising an entry and exit point, respectively, comprising arcs and states distinct from arcs and states of the finite-state network;

traversing the multiword finite-state network and the set of subnets to identify a path corresponding to one of the plurality of multiword expressions;

wherein said traversing accounts for only transitions originating from the multiword finite-state network to ascertain a path number identifying a base form of the one of the plurality of multiword expressions; and

wherein said factorization comprises inserting an arc with a label in the multiword finite-state network at each appearance of a repeating subnet in the set of subnets, where each label is a reference to a subnet in the set of subnets.

20. The article of manufacture according to claim 19, wherein the method further comprises identifying information related to the one of the plurality of multiword expressions using the path number.