Method and apparatus for processing natural language using tape-intersection

• US 8,095,356 B2
• Filed: 11/09/2009
• Issued: 01/10/2012
• Est. Priority Date: 11/14/2003
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Kempe, Andre, Guingne, Franck, Nicart, Florent
• Primary Examiner(s): Hudspeth, David R
• Assistant Examiner(s): Spooner, Lamont
• Application Number:
  US12/614,886
• Publication Number:
  US 20100049503A1
• Time in Patent Office: 792 Days
• Field of Search: 704/1, 704/9, 704/10, 704/251, 704/256, 704/257, 707706-708
• US Class Current: 704/9
• CPC Class Codes: G06F 40/237 Lexical tools

Abstract

Operations for weighted and non-weighted multi-tape automata are described for use in natural language processing tasks such as morphological analysis, disambiguation, and entity extraction.

Claims

1. In a system for processing natural language, a method for intersecting a first tape of a first multi-tape automaton (MTA) and a second tape of a second MTA, with each MTA having a plurality of tapes and a plurality of paths, comprising:

defining a simulated filter automaton (SFA) that controls how epsilon-transitions are composed along pairs of paths in the first MTA and the second MTA; and

,

building by a processor an output MTA by;

(a) creating an initial state from the initial states of the first MTA, the second MTA, and the SFA;

(b) intersecting a selected outgoing transition of the first MTA with a selected outgoing transition of the second MTA, where each outgoing transition has a source state, a target state, and a label;

(c) creating a transition in the output MTA if the label of the first tape of the selected outgoing transition of the first MTA equals the label of the second tape of the selected outgoing transition of the second MTA, wherein the transition in the output MTA is created whose label results from pairing the labels of the selected outgoing transitions and whose target state corresponds to the target states of the selected outgoing transitions and the initial state of the SFA;

(d) if an epsilon transition is encountered on the first tape, creating a transition in the output MTA with a target state that is a function of the target state of the outgoing transition of the first MTA, the source state of the outgoing transition of the second MTA, and a first non-initial state of the SFA;

(e) if an epsilon transition is encountered on the second tape, creating a transition in the output MTA with a target state that is a function of the source state of the outgoing transition of the first MTA, the target state of the outgoing transition of the second MTA, and a second non-initial state of the SFA; and

(f) repeating (b)-(e) for each outgoing transition of the first MTA and the second MTA.

2. The method according to claim 1, further comprising revising the labels of transitions of the output MTA to remove one of its tapes corresponding to either the first tape of the first MTA or the second tape of the second MTA to complete single-tape intersection.

3. The method according to claim 1, further comprising revising the labels of each transition of the output MTA to remove both of its tapes corresponding to the first tape of the first MTA and the second tape of the second MTA to complete classical composition.

4. The method according to claim 1, further comprising performing auto-intersection on the output MTA for two selected tapes, wherein no more than one of the two selected tapes corresponds to the first tape of the first MTA or the second tape of the second MTA.

5. The method according to claim 4, further comprising revising the output MTA to eliminate redundant tapes to complete multi-tape intersection.

6. The method according to claim 1, wherein the output MTA preserves at least one other tape besides one of the first tape of the first MTA and the second tape of the second MTA.

7. The method according to claim 1, further comprising repeating (a)-(f) in a cascade of a first transduction and a second transduction, where at least one of the tapes preserved after completing the first transduction is accessed to perform the second transduction.