Method and apparatus for processing natural language using tape-intersection
First Claim
Patent Images
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
7 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
Specification