1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
// rmfinalepsilon.h
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
//
// \file
// Function to remove of final states that have epsilon only input arcs.
#ifndef FST_LIB_RMFINALEPSILON_H__
#define FST_LIB_RMFINALEPSILON_H__
#include <ext/hash_set>
using __gnu_cxx::hash_set;
#include "fst/lib/connect.h"
#include "fst/lib/mutable-fst.h"
namespace fst {
template<class A>
void RmFinalEpsilon(MutableFst<A>* fst) {
typedef typename A::StateId StateId;
typedef typename A::Weight Weight;
// Determine the coaccesibility of states.
vector<bool> access;
vector<bool> coaccess;
uint64 props = 0;
SccVisitor<A> scc_visitor(0, &access, &coaccess, &props);
DfsVisit(*fst, &scc_visitor);
// Find potential list of removable final states. These are final states
// that have no outgoing transitions or final states that have a
// non-coaccessible future. Complexity O(S)
hash_set<StateId> finals;
for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) {
StateId s = siter.Value();
if (fst->Final(s) != Weight::Zero()) {
bool future_coaccess = false;
for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
const A& arc = aiter.Value();
if (coaccess[arc.nextstate]) {
future_coaccess = true;
break;
}
}
if (!future_coaccess) {
finals.insert(s);
}
}
}
// Move the final weight. Complexity O(E)
vector<A> arcs;
for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) {
StateId s = siter.Value();
Weight w(fst->Final(s));
arcs.clear();
for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
const A& arc = aiter.Value();
// is next state in the list of finals
if (finals.find(arc.nextstate) != finals.end()) {
// sum up all epsilon arcs
if (arc.ilabel == 0 && arc.olabel == 0) {
w = Plus(Times(fst->Final(arc.nextstate), arc.weight), w);
} else {
arcs.push_back(arc);
}
} else {
arcs.push_back(arc);
}
}
// If some arcs (epsilon arcs) were deleted, delete all
// arcs and add back only the non epsilon arcs
if (arcs.size() < fst->NumArcs(s)) {
fst->DeleteArcs(s);
fst->SetFinal(s, w);
for (size_t i = 0; i < arcs.size(); ++i) {
fst->AddArc(s, arcs[i]);
}
}
}
Connect(fst);
}
}
#endif // FST_LIB_RMFINALEPSILON_H__
|
