16ab7cd853e9c15cf986a8a7c3db1f8d20e275409Sebastian Redl// fstlib.h 22cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 32cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Licensed under the Apache License, Version 2.0 (the "License"); 42cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// you may not use this file except in compliance with the License. 52cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// You may obtain a copy of the License at 62cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 72cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// http://www.apache.org/licenses/LICENSE-2.0 82cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 92cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Unless required by applicable law or agreed to in writing, software 10c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl// distributed under the License is distributed on an "AS IS" BASIS, 112cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 122cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// See the License for the specific language governing permissions and 138b12273c86ede439edf52d35b170fd32b2ed49d4Sebastian Redl// limitations under the License. 14f29f0a28c4d9599b389bbb6d186e14af753dc5a3Sebastian Redl// 15f29f0a28c4d9599b389bbb6d186e14af753dc5a3Sebastian Redl// Copyright 2005-2010 Google, Inc. 162cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Author: riley@google.com (Michael Riley) 17f0aaf7a59729a4ae0146e3464ee987745be95829Douglas Gregor// 1830a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// \page FstLib FST - Weighted Finite State Transducers 19833ca991c1bfc967f0995974ca86f66ba1f666b5John McCall// This is a library for constructing, combining, optimizing, and 200a0428e96c6f1e8bef7a481a9eb69a6f6df38951Douglas Gregor// searching "weighted finite-state transducers" (FSTs). Weighted 211afb661bc5444462a246cefa0effa61ef25fab29Jonathan D. Turner// finite-state transducers are automata where each transition has an 221afb661bc5444462a246cefa0effa61ef25fab29Jonathan D. Turner// input label, an output label, and a weight. The more familiar 23668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor// finite-state acceptor is represented as a transducer with each 247f94b0b0c6791013d2f72ced9b4bedd3b23673a6Douglas Gregor// transition's input and output the same. Finite-state acceptors 25c544ba09695e300f31355af342258bd57619e737Douglas Gregor// are used to represent sets of strings (specifically, "regular" or 2630a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// "rational sets"); finite-state transducers are used to represent 2730a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// binary relations between pairs of strings (specifically, "rational 2830a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// transductions"). The weights can be used to represent the cost of 2930a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// taking a particular transition. 3030a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// 3130a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// In this library, the transducers are templated on the Arc 3230a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// (transition) definition, which allows changing the label, weight, 3330a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// and state ID sets. Labels and state IDs are restricted to signed 3417fc223395d51be582fc666bb6ea21bd1dff26dcDouglas Gregor// integral types but the weight can be an arbitrary type whose 350a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor// members satisfy certain algebraic ("semiring") properties. 360a2b45e5885b6b8477b167042c0f6cd1d99a1f13Douglas Gregor// 3730a2e16f6c27f888dd11eba6bbbae1e980078fcbChandler Carruth// For more information, see the FST Library Wiki page: 38ce12d2f8863588d408897602089d17c4d3c3d0e5Douglas Gregor// http://wiki.corp.google.com/twiki/bin/view/Main/FstLibrary 392cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 400f75323264b93a318ac9007eb5ec5b233c444068Douglas Gregor// \file 410f75323264b93a318ac9007eb5ec5b233c444068Douglas Gregor// This convenience file includes all other FST inl.h files. 422cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// 43dc3c0d20375bda7775b2fade05b20e315798b9feDaniel Dunbar 442cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#ifndef FST_LIB_FSTLIB_H__ 4503013fa9a0bf1ef4b907f5fec006c8f4000fdd21Michael J. Spencer#define FST_LIB_FSTLIB_H__ 46d89275bc865e2b552836c7b33e636d4f86b8de6dDouglas Gregor 47025452fa0eda63e150cfaeebe64f0a19c96b3a06Douglas Gregor 482cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Abstract FST classes 492cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/fst.h> 502cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/expanded-fst.h> 51677e15ffee2ecc9c1c8f46fd77cab4b5afb59640Douglas Gregor#include <fst/mutable-fst.h> 522cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 532cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor// Concrete FST classes 542cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/compact-fst.h> 552cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/const-fst.h> 562cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/edit-fst.h> 572cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/vector-fst.h> 582cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor 597d5c2f241c74e5f8d9ec492e8f9f268e5e9ae41fDouglas Gregor// FST algorithms and delayed FST classes 600af2ca4b6ddc788658069a0994941268ce250fc7Douglas Gregor#include <fst/arcsort.h> 612cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/arc-map.h> 6295f4292cc526c629fead321c7fcfd4fe0f3bc66eDouglas Gregor#include <fst/closure.h> 63f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#include <fst/compose.h> 6468a2eb0cc76267ba0615992fb5e0977853c397b2Douglas Gregor#include <fst/concat.h> 652cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/connect.h> 662cf2634ffdb4f7c8d46cef3f8e60a55993f1c57aDouglas Gregor#include <fst/determinize.h> 675f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/difference.h> 686ad9ac097918fbdeb443ea7b99d4db9e49b28534Chris Lattner#include <fst/encode.h> 696ad9ac097918fbdeb443ea7b99d4db9e49b28534Chris Lattner#include <fst/epsnormalize.h> 70ebcbe1d3dc7d4f0c1f540a632fa0684dd0a857d5Sean Hunt#include <fst/equal.h> 71cbb67480094b3bcb5b715acd827cbad55e2a204cSean Hunt#include <fst/equivalent.h> 721a49d97d762570027863e9209af81d445e4f1502Douglas Gregor#include <fst/factor-weight.h> 731de05feeeafe5b215fe7617594a7076a5192a6e2Douglas Gregor#include <fst/intersect.h> 746a5a23f8e7fb65e028c8092bc1d1a1d9dfe2e9bcDouglas Gregor#include <fst/invert.h> 759818a1d443e97677dd3422305de9cc2b1fb2a8c1Argyrios Kyrtzidis#include <fst/map.h> 76668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor#include <fst/minimize.h> 7756ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall#include <fst/project.h> 7814f79002e58556798e86168c63e48d533287eda5Douglas Gregor#include <fst/prune.h> 79a71a7d8a1ce4474e7bdb680658fb58b6caf391d3Douglas Gregor#include <fst/push.h> 80668c1a4fdcc56bdd050256b1688e116fe84b72dbDouglas Gregor#include <fst/randequivalent.h> 81025452fa0eda63e150cfaeebe64f0a19c96b3a06Douglas Gregor#include <fst/randgen.h> 82c3632730cc83ed7b51f0ab5c38997ae5a9439b0cSebastian Redl#include <fst/rational.h> 83f62d43d2afe1960755a1b5813cae1e5983bcac1bDouglas Gregor#include <fst/relabel.h> 84c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl#include <fst/replace.h> 85d527cc06d78fe5afa5f20105b51697637eb02c56Sebastian Redl#include <fst/replace-util.h> 86c3632730cc83ed7b51f0ab5c38997ae5a9439b0cSebastian Redl#include <fst/reverse.h> 87c3632730cc83ed7b51f0ab5c38997ae5a9439b0cSebastian Redl#include <fst/reweight.h> 88eb19485625c7529ffa644e10829533157a8e8d4fDaniel Dunbar#include <fst/rmepsilon.h> 890a0d2b179085a52c10402feebeb6db8b4d96a140Douglas Gregor#include <fst/rmfinalepsilon.h> 9057016dda61498294120b1a881d9e6606337b29d9Douglas Gregor#include <fst/shortest-distance.h> 912a82ca255b0f99f6201a75ed52b91fc024f6e9cfArgyrios Kyrtzidis#include <fst/shortest-path.h> 9211e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/statesort.h> 93c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl#include <fst/state-map.h> 9411e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/synchronize.h> 95c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl#include <fst/topsort.h> 9611e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/union.h> 97c43b54cbc10654ed59de797898042e1a05265246Sebastian Redl#include <fst/verify.h> 98571db7f0cb31789737be92fce1c1b738e6dbe795Sebastian Redl#include <fst/visit.h> 99571db7f0cb31789737be92fce1c1b738e6dbe795Sebastian Redl 10011e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis// Weights 101571db7f0cb31789737be92fce1c1b738e6dbe795Sebastian Redl#include <fst/weight.h> 1021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump#include <fst/expectation-weight.h> 103c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/float-weight.h> 104c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/lexicographic-weight.h> 105c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/pair-weight.h> 106c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/power-weight.h> 107c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/product-weight.h> 108c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/random-weight.h> 109c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/signed-log-weight.h> 110c544ba09695e300f31355af342258bd57619e737Douglas Gregor#include <fst/sparse-power-weight.h> 11111e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/sparse-tuple-weight.h> 11211e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/string-weight.h> 11311e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/tuple-weight.h> 11427ffa6caf965ef20fdef5ae23b81cdc3d05e7afbDouglas Gregor 11538295beb73db5f90bfcf31625fb81dbc3b96290aDouglas Gregor// Auxiliary classes for composition 11611e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/compose-filter.h> 11711e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/lookahead-filter.h> 1181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump#include <fst/lookahead-matcher.h> 11957016dda61498294120b1a881d9e6606337b29d9Douglas Gregor#include <fst/matcher-fst.h> 12011e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/matcher.h> 12157016dda61498294120b1a881d9e6606337b29d9Douglas Gregor#include <fst/state-table.h> 12257016dda61498294120b1a881d9e6606337b29d9Douglas Gregor 12327ffa6caf965ef20fdef5ae23b81cdc3d05e7afbDouglas Gregor// Data structures 12438295beb73db5f90bfcf31625fb81dbc3b96290aDouglas Gregor#include <fst/heap.h> 12511e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/interval-set.h> 12611e51106329c550d008fad2c657c053d81611ea8Argyrios Kyrtzidis#include <fst/queue.h> 1271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump#include <fst/union-find.h> 1285f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor 1295f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor// Miscellaneous 1305f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/accumulator.h> 1315f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/add-on.h> 1325f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/arc.h> 1335f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/arcfilter.h> 1345f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/cache.h> 1355f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/complement.h> 1365f3d8224af99ad0d9107601c0c31b74693371cc1Douglas Gregor#include <fst/dfs-visit.h> 1371b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/generic-register.h> 1381b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/label-reachable.h> 1391b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/partition.h> 1401b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/properties.h> 1411b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/register.h> 1421b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fst/state-reachable.h> 1431b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <iostream> 1441b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <fstream> 1451b2c3c0884e917ae5d59edde7d93b2af33c6a1b6Douglas Gregor#include <sstream> 146bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/string.h> 147bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/symbol-table.h> 148bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/symbol-table-ops.h> 149bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/test-properties.h> 150bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#include <fst/util.h> 151bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor 152bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor 153bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor#endif // FST_LIB_FSTLIB_H__ 154bbf38319edd4eddc55ec273934e990d7e84991deDouglas Gregor