1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// fstlib.h
2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License");
4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License.
5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at
6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson//
7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson//     http://www.apache.org/licenses/LICENSE-2.0
8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson//
9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software
10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS,
11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and
13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License.
14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson//
15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc.
16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: riley@google.com (Michael Riley)
17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson//
18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \page FstLib FST - Weighted Finite State Transducers
19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This is a library for constructing, combining, optimizing, and
20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// searching "weighted finite-state transducers" (FSTs). Weighted
21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// finite-state transducers are automata where each transition has an
22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// input label, an output label, and a weight. The more familiar
23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// finite-state acceptor is represented as a transducer with each
24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// transition's input and output the same.  Finite-state acceptors
25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// are used to represent sets of strings (specifically, "regular" or
26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// "rational sets"); finite-state transducers are used to represent
27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// binary relations between pairs of strings (specifically, "rational
28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// transductions"). The weights can be used to represent the cost of
29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// taking a particular transition.
30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson//
31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// In this library, the transducers are templated on the Arc
32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// (transition) definition, which allows changing the label, weight,
33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// and state ID sets. Labels and state IDs are restricted to signed
34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// integral types but the weight can be an arbitrary type whose
35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// members satisfy certain algebraic ("semiring") properties.
36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson//
37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// For more information, see the FST Library Wiki page:
38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://wiki.corp.google.com/twiki/bin/view/Main/FstLibrary
39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file
41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// This convenience file includes all other FST inl.h files.
42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson//
43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_FSTLIB_H__
45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_FSTLIB_H__
46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Abstract FST classes
49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/fst.h>
50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/expanded-fst.h>
51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/mutable-fst.h>
52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Concrete FST classes
54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/compact-fst.h>
55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/const-fst.h>
56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/edit-fst.h>
57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/vector-fst.h>
58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// FST algorithms and delayed FST classes
60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/arcsort.h>
61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/arc-map.h>
62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/closure.h>
63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/compose.h>
64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/concat.h>
65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/connect.h>
66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/determinize.h>
67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/difference.h>
68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/encode.h>
69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/epsnormalize.h>
70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/equal.h>
71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/equivalent.h>
72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/factor-weight.h>
73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/intersect.h>
74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/invert.h>
75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/map.h>
76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/minimize.h>
77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/project.h>
78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/prune.h>
79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/push.h>
80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/randequivalent.h>
81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/randgen.h>
82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/rational.h>
83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/relabel.h>
84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/replace.h>
85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/replace-util.h>
86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/reverse.h>
87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/reweight.h>
88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/rmepsilon.h>
89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/rmfinalepsilon.h>
90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/shortest-distance.h>
91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/shortest-path.h>
92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/statesort.h>
93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/state-map.h>
94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/synchronize.h>
95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/topsort.h>
96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/union.h>
97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/verify.h>
98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/visit.h>
99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Weights
101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/weight.h>
102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/expectation-weight.h>
103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/float-weight.h>
104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/lexicographic-weight.h>
105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/pair-weight.h>
106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/power-weight.h>
107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/product-weight.h>
108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/random-weight.h>
109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/signed-log-weight.h>
110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/sparse-power-weight.h>
111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/sparse-tuple-weight.h>
112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/string-weight.h>
113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/tuple-weight.h>
114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Auxiliary classes for composition
116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/compose-filter.h>
117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/lookahead-filter.h>
118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/lookahead-matcher.h>
119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/matcher-fst.h>
120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/matcher.h>
121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/state-table.h>
122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Data structures
124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/heap.h>
125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/interval-set.h>
126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/queue.h>
127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/union-find.h>
128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Miscellaneous
130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/accumulator.h>
131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/add-on.h>
132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/arc.h>
133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/arcfilter.h>
134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/cache.h>
135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/complement.h>
136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/dfs-visit.h>
137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/generic-register.h>
138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/label-reachable.h>
139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/partition.h>
140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/properties.h>
141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/register.h>
142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/state-reachable.h>
143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <iostream>
144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fstream>
145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/symbol-table.h>
146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/symbol-table-ops.h>
147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/test-properties.h>
148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/util.h>
149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson
151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif  // FST_LIB_FSTLIB_H__
152