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//
16// \file
17// Class to compute the difference between two FSAs
18
19#ifndef FST_LIB_DIFFERENCE_H__
20#define FST_LIB_DIFFERENCE_H__
21
22#include "fst/lib/compose.h"
23#include "fst/lib/complement.h"
24
25namespace fst {
26
27template <uint64 T = 0>
28struct DifferenceFstOptions
29    : public ComposeFstOptions<T | COMPOSE_FST2_RHO> { };
30
31
32// Computes the difference between two FSAs. This version is a delayed
33// Fst. Only strings that are in the first automaton but not in second
34// are retained in the result.
35//
36// The first argument must be an acceptor; the second argument must be
37// an unweighted, epsilon-free, deterministic acceptor. One of the
38// arguments must be label-sorted.
39//
40// Complexity: same as ComposeFst.
41//
42// Caveats: same as ComposeFst.
43template <class A>
44class DifferenceFst : public ComposeFst<A> {
45 public:
46  using ComposeFst<A>::Impl;
47
48  typedef A Arc;
49  typedef typename A::Weight Weight;
50  typedef typename A::StateId StateId;
51
52  // A - B = A ^ B'.
53  DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2)
54      : ComposeFst<A>(fst1,
55                      ComplementFst<A>(fst2),
56                      ComposeFstOptions<COMPOSE_FST2_RHO>()) {
57    if (!fst1.Properties(kAcceptor, true))
58      LOG(FATAL) << "DifferenceFst: 1st argument not an acceptor";
59    uint64 props1 = fst1.Properties(kFstProperties, false);
60    uint64 props2 = fst2.Properties(kFstProperties, false);
61    Impl()->SetProperties(DifferenceProperties(props1, props2),
62                          kCopyProperties);
63  }
64
65  template <uint64 T>
66  DifferenceFst(const Fst<A> &fst1, const Fst<A> &fst2,
67                const DifferenceFstOptions<T> &opts)
68      : ComposeFst<A>(fst1,
69                      ComplementFst<A>(fst2),
70                      ComposeFstOptions<T | COMPOSE_FST2_RHO>(opts)) {
71    if (!fst1.Properties(kAcceptor, true))
72      LOG(FATAL) << "DifferenceFst: 1st argument not an acceptor";
73    uint64 props1 = fst1.Properties(kFstProperties, false);
74    uint64 props2 = fst2.Properties(kFstProperties, false);
75    Impl()->SetProperties(DifferenceProperties(props1, props2),
76                          kCopyProperties);
77  }
78
79  DifferenceFst(const DifferenceFst<A> &fst)
80      : ComposeFst<A>(fst) {}
81
82  virtual DifferenceFst<A> *Copy() const {
83    return new DifferenceFst<A>(*this);
84  }
85};
86
87
88// Specialization for DifferenceFst.
89template <class A>
90class StateIterator< DifferenceFst<A> >
91    : public StateIterator< ComposeFst<A> > {
92 public:
93  explicit StateIterator(const DifferenceFst<A> &fst)
94      : StateIterator< ComposeFst<A> >(fst) {}
95};
96
97
98// Specialization for DifferenceFst.
99template <class A>
100class ArcIterator< DifferenceFst<A> >
101    : public ArcIterator< ComposeFst<A> > {
102 public:
103  typedef typename A::StateId StateId;
104
105  ArcIterator(const DifferenceFst<A> &fst, StateId s)
106      : ArcIterator< ComposeFst<A> >(fst, s) {}
107};
108
109// Useful alias when using StdArc.
110typedef DifferenceFst<StdArc> StdDifferenceFst;
111
112
113typedef ComposeOptions DifferenceOptions;
114
115
116// Computes the difference between two FSAs. This version is writes
117// the difference to an output MutableFst. Only strings that are in
118// the first automaton but not in second are retained in the result.
119//
120// The first argument must be an acceptor; the second argument must be
121// an unweighted, epsilon-free, deterministic acceptor.  One of the
122// arguments must be label-sorted.
123//
124// Complexity: same as Compose.
125//
126// Caveats: same as Compose.
127template<class Arc>
128void Difference(const Fst<Arc> &ifst1, const Fst<Arc> &ifst2,
129             MutableFst<Arc> *ofst,
130             const DifferenceOptions &opts = DifferenceOptions()) {
131  DifferenceFstOptions<> nopts;
132  nopts.gc_limit = 0;  // Cache only the last state for fastest copy.
133  *ofst = DifferenceFst<Arc>(ifst1, ifst2, nopts);
134  if (opts.connect)
135    Connect(ofst);
136}
137
138}  // namespace fst
139
140#endif  // FST_LIB_DIFFERENCE_H__
141