1// difference.h
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Copyright 2005-2010 Google, Inc.
16// Author: riley@google.com (Michael Riley)
17//
18// \file
19// Class to compute the difference between two FSAs
20
21#ifndef FST_LIB_DIFFERENCE_H__
22#define FST_LIB_DIFFERENCE_H__
23
24#include <vector>
25using std::vector;
26#include <algorithm>
27
28#include <fst/cache.h>
29#include <fst/compose.h>
30#include <fst/complement.h>
31
32
33namespace fst {
34
35template <class A,
36          class M = Matcher<Fst<A> >,
37          class F = SequenceComposeFilter<M>,
38          class T = GenericComposeStateTable<A, typename F::FilterState> >
39struct DifferenceFstOptions : public ComposeFstOptions<A, M, F, T> {
40  explicit DifferenceFstOptions(const CacheOptions &opts,
41                                M *mat1 = 0, M *mat2 = 0,
42                                F *filt = 0, T *sttable= 0)
43      : ComposeFstOptions<A, M, F, T>(mat1, mat2, filt, sttable) { }
44
45  DifferenceFstOptions() {}
46};
47
48// Computes the difference between two FSAs. This version is a delayed
49// Fst. Only strings that are in the first automaton but not in second
50// are retained in the result.
51//
52// The first argument must be an acceptor; the second argument must be
53// an unweighted, epsilon-free, deterministic acceptor. One of the
54// arguments must be label-sorted.
55//
56// Complexity: same as ComposeFst.
57//
58// Caveats: same as ComposeFst.
59template <class A>
60class DifferenceFst : public ComposeFst<A> {
61 public:
62  using ImplToFst< ComposeFstImplBase<A> >::SetImpl;
63  using ImplToFst< ComposeFstImplBase<A> >::GetImpl;
64
65  using ComposeFst<A>::CreateBase1;
66
67  typedef A Arc;
68  typedef typename A::Weight Weight;
69  typedef typename A::StateId StateId;
70
71  // A - B = A ^ B'.
72  DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2,
73                const CacheOptions &opts = CacheOptions()) {
74    typedef RhoMatcher< Matcher<Fst<A> > > R;
75
76    ComplementFst<A> cfst(fst2);
77    ComposeFstOptions<A, R> copts(CacheOptions(),
78                                  new R(fst1, MATCH_NONE),
79                                  new R(cfst, MATCH_INPUT,
80                                        ComplementFst<A>::kRhoLabel));
81    SetImpl(CreateBase1(fst1, cfst, copts));
82
83    if (!fst1.Properties(kAcceptor, true)) {
84      FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
85      GetImpl()->SetProperties(kError, kError);
86    }
87 }
88
89  template <class M, class F, class T>
90  DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2,
91                const DifferenceFstOptions<A, M, F, T> &opts) {
92    typedef RhoMatcher<M> R;
93
94    ComplementFst<A> cfst(fst2);
95    ComposeFstOptions<A, R> copts(opts);
96    copts.matcher1 = new R(fst1, MATCH_NONE, kNoLabel, MATCHER_REWRITE_ALWAYS,
97                           opts.matcher1);
98    copts.matcher2 = new R(cfst, MATCH_INPUT, ComplementFst<A>::kRhoLabel,
99                           MATCHER_REWRITE_ALWAYS, opts.matcher2);
100
101    SetImpl(CreateBase1(fst1, cfst, copts));
102
103    if (!fst1.Properties(kAcceptor, true)) {
104      FSTERROR() << "DifferenceFst: 1st argument not an acceptor";
105      GetImpl()->SetProperties(kError, kError);
106    }
107  }
108
109  // See Fst<>::Copy() for doc.
110  DifferenceFst(const DifferenceFst<A> &fst, bool safe = false)
111      : ComposeFst<A>(fst, safe) {}
112
113  // Get a copy of this DifferenceFst. See Fst<>::Copy() for further doc.
114  virtual DifferenceFst<A> *Copy(bool safe = false) const {
115    return new DifferenceFst<A>(*this, safe);
116  }
117};
118
119
120// Specialization for DifferenceFst.
121template <class A>
122class StateIterator< DifferenceFst<A> >
123    : public StateIterator< ComposeFst<A> > {
124 public:
125  explicit StateIterator(const DifferenceFst<A> &fst)
126      : StateIterator< ComposeFst<A> >(fst) {}
127};
128
129
130// Specialization for DifferenceFst.
131template <class A>
132class ArcIterator< DifferenceFst<A> >
133    : public ArcIterator< ComposeFst<A> > {
134 public:
135  typedef typename A::StateId StateId;
136
137  ArcIterator(const DifferenceFst<A> &fst, StateId s)
138      : ArcIterator< ComposeFst<A> >(fst, s) {}
139};
140
141// Useful alias when using StdArc.
142typedef DifferenceFst<StdArc> StdDifferenceFst;
143
144
145typedef ComposeOptions DifferenceOptions;
146
147
148// Computes the difference between two FSAs. This version is writes
149// the difference to an output MutableFst. Only strings that are in
150// the first automaton but not in second are retained in the result.
151//
152// The first argument must be an acceptor; the second argument must be
153// an unweighted, epsilon-free, deterministic acceptor.  One of the
154// arguments must be label-sorted.
155//
156// Complexity: same as Compose.
157//
158// Caveats: same as Compose.
159template<class Arc>
160void Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
161             MutableFst<Arc> *ofst,
162             const DifferenceOptions &opts = DifferenceOptions()) {
163  typedef Matcher< Fst<Arc> > M;
164
165  if (opts.filter_type == AUTO_FILTER) {
166    CacheOptions nopts;
167    nopts.gc_limit = 0;  // Cache only the last state for fastest copy.
168    *ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts);
169  } else if (opts.filter_type == SEQUENCE_FILTER) {
170    DifferenceFstOptions<Arc> dopts;
171    dopts.gc_limit = 0;  // Cache only the last state for fastest copy.
172    *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
173  } else if (opts.filter_type == ALT_SEQUENCE_FILTER) {
174    DifferenceFstOptions<Arc, M, AltSequenceComposeFilter<M> > dopts;
175    dopts.gc_limit = 0;  // Cache only the last state for fastest copy.
176    *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
177  } else if (opts.filter_type == MATCH_FILTER) {
178    DifferenceFstOptions<Arc, M, MatchComposeFilter<M> > dopts;
179    dopts.gc_limit = 0;  // Cache only the last state for fastest copy.
180    *ofst = DifferenceFst<Arc>(ifst1, ifst2, dopts);
181  }
182
183  if (opts.connect)
184    Connect(ofst);
185}
186
187}  // namespace fst
188
189#endif  // FST_LIB_DIFFERENCE_H__
190