Using finite-state networks to store weights in a finite-state network
AssigneeXerox Corporation
InventorKenneth R. Beesley
Life of this patent
Estimating the term…
Abstract
In a weighted finite state network process, a finite state network object is stored. The finite state network object includes arcs, and each arc has an associated weight stored as a weight-defining finite state network object. The finite state network object is applied to an input. The applying includes combining weights of one or more arcs matching the input using finite state network-combining operations.
Claims20
A weighted finite state network process comprising:
- storing a finite state network object including one or more arcs defining one or more paths, at least one arc having an associated weight stored as a weight-defining finite state network object;
- and
- applying the finite state network object to an input, the applying including combining weights of one or more arcs matching the input using at least one of:
- (i) a collection operation to combine weights of parallel paths, the collection operation being implemented as a finite state network-combining operation acting on weight-defining finite state network objects, and
- (ii) an extension operation to combine weights of arcs along a path, the extension operation being implemented as a finite state network-combining operation acting on weight-defining finite state network objects;
- wherein the storing and the applying are performed by a processor.
A weighted finite state network process comprising:
- storing a finite state network object including one or more arcs defining one or more paths, at least one arc having an associated weight stored as a weight-defining finite state network object, wherein each weight-defining finite state network object encodes a regular language;
- and
- applying the finite state network object to an input, the applying including combining weights of one or more arcs matching the input using at least one of:
- (i) a collection operation to combine weights of parallel paths, the collection operation being implemented as a finite state network-combining operation acting on weight-defining finite state network objects, and
- (ii) an extension operation to combine weights of arcs along a path, the extension operation being implemented as a finite state network-combining operation acting on weight-defining finite state network objects;
- wherein the storing and the applying are performed by a processor.
A digital storage medium storing instructions executable to perform weighted finite state network processing including (i) storing a finite state network object including one or more arcs, at least one arc being associated with a weight stored as a weight-defining finite state network object, and (ii) applying the stored finite state network object to an input, the applying including combining weights of one or more arcs using finite state network-combining operations, wherein the storing includes storing the finite state network object and the weight-defining finite state network objects as associated but separate objects.
A weighted finite state network process comprising:
- storing a finite state network object including one or more arcs;
- and
- storing a weight associated with each arc of the finite state network object, each weight being stored as a weight-defining finite state network object;
- wherein each weight-defining finite state network object encodes one of (i) a language and (ii) a features set;
- and
- wherein the storing operations are performed by a processor.
Dependencies are inferred from the claim text.