1 // lookahead-filter.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 // Composition filters to support lookahead matchers, useful for improving
20 // composition efficiency with certain inputs.
21
22 #ifndef FST_LIB_LOOKAHEAD_FILTER_H__
23 #define FST_LIB_LOOKAHEAD_FILTER_H__
24
25 #include <vector>
26 using std::vector;
27
28 #include <fst/fst.h>
29 #include <fst/lookahead-matcher.h>
30
31
32 namespace fst {
33
34 // Identifies and verifies the capabilities of the matcher to be used for
35 // lookahead with the composition filters below. This version is passed
36 // the matchers.
37 template <class M1, class M2>
LookAheadMatchType(const M1 & m1,const M2 & m2)38 MatchType LookAheadMatchType(const M1 &m1, const M2 &m2) {
39 MatchType type1 = m1.Type(false);
40 MatchType type2 = m2.Type(false);
41 if (type1 == MATCH_OUTPUT &&
42 m1.Flags() & kOutputLookAheadMatcher)
43 return MATCH_OUTPUT;
44 else if (type2 == MATCH_INPUT &&
45 m2.Flags() & kInputLookAheadMatcher)
46 return MATCH_INPUT;
47 else if (m1.Flags() & kOutputLookAheadMatcher &&
48 m1.Type(true) == MATCH_OUTPUT)
49 return MATCH_OUTPUT;
50 else if (m2.Flags() & kInputLookAheadMatcher &&
51 m2.Type(true) == MATCH_INPUT)
52 return MATCH_INPUT;
53 else
54 return MATCH_NONE;
55 }
56
57 // Identifies and verifies the capabilities of the matcher to be used for
58 // lookahead with the composition filters below. This version uses the
59 // Fst's default matchers.
60 template <class Arc>
LookAheadMatchType(const Fst<Arc> & fst1,const Fst<Arc> & fst2)61 MatchType LookAheadMatchType(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
62 LookAheadMatcher< Fst <Arc> > matcher1(fst1, MATCH_OUTPUT);
63 LookAheadMatcher< Fst <Arc> > matcher2(fst2, MATCH_INPUT);
64 return LookAheadMatchType(matcher1, matcher2);
65 }
66
67 //
68 // LookAheadSelector - a helper class for selecting among possibly
69 // distinct FST and matcher types w/o using a common base class. This
70 // lets us avoid virtual function calls.
71 //
72
73 // Stores and returns the appropriate FST and matcher for lookahead.
74 // It is templated on the matcher types. General case has no methods
75 // since not currently supported.
76 template <class M1, class M2, MatchType MT>
77 class LookAheadSelector {
78 };
79
80 // Stores and returns the appropriate FST and matcher for lookahead.
81 // Specialized for two matchers of same type with the (match) 'type'
82 // arg determining which is used for lookahead.
83 template <class M, MatchType MT>
84 class LookAheadSelector<M, M, MT> {
85 public:
86 typedef typename M::Arc Arc;
87 typedef typename M::FST F;
88
LookAheadSelector(M * lmatcher1,M * lmatcher2,MatchType type)89 LookAheadSelector(M *lmatcher1, M *lmatcher2, MatchType type)
90 : lmatcher1_(lmatcher1->Copy()),
91 lmatcher2_(lmatcher2->Copy()),
92 type_(type) {}
93
LookAheadSelector(const LookAheadSelector<M,M,MT> & selector)94 LookAheadSelector(const LookAheadSelector<M, M, MT> &selector)
95 : lmatcher1_(selector.lmatcher1_->Copy()),
96 lmatcher2_(selector.lmatcher2_->Copy()),
97 type_(selector.type_) {}
98
~LookAheadSelector()99 ~LookAheadSelector() {
100 delete lmatcher1_;
101 delete lmatcher2_;
102 }
103
GetFst()104 const F &GetFst() const {
105 return type_ == MATCH_OUTPUT ? lmatcher2_->GetFst() :
106 lmatcher1_->GetFst();
107 }
108
GetMatcher()109 M *GetMatcher() const {
110 return type_ == MATCH_OUTPUT ? lmatcher1_ : lmatcher2_;
111 }
112
113 private:
114 M *lmatcher1_;
115 M *lmatcher2_;
116 MatchType type_;
117
118 void operator=(const LookAheadSelector<M, M, MT> &); // disallow
119 };
120
121 // Stores and returns the appropriate FST and matcher for lookahead.
122 // Specialized for lookahead on input labels.
123 template <class M1, class M2>
124 class LookAheadSelector<M1, M2, MATCH_INPUT> {
125 public:
126 typedef typename M1::FST F1;
127
LookAheadSelector(M1 * lmatcher1,M2 * lmatcher2,MatchType)128 LookAheadSelector(M1 *lmatcher1, M2 *lmatcher2, MatchType)
129 : fst_(lmatcher1->GetFst().Copy()),
130 lmatcher_(lmatcher2->Copy()) {}
131
LookAheadSelector(const LookAheadSelector<M1,M2,MATCH_INPUT> & selector)132 LookAheadSelector(const LookAheadSelector<M1, M2, MATCH_INPUT> &selector)
133 : fst_(selector.fst_->Copy()),
134 lmatcher_(selector.lmatcher_->Copy()) {}
135
~LookAheadSelector()136 ~LookAheadSelector() {
137 delete lmatcher_;
138 delete fst_;
139 }
140
GetFst()141 const F1 &GetFst() const { return *fst_; }
142
GetMatcher()143 M2 *GetMatcher() const { return lmatcher_; }
144
145 private:
146 const F1 *fst_;
147 M2 *lmatcher_;
148
149 void operator=(const LookAheadSelector<M1, M2, MATCH_INPUT> &); // disallow
150 };
151
152
153 // Stores and returns the appropriate FST and matcher for lookahead.
154 // Specialized for lookahead on output labels.
155 template <class M1, class M2>
156 class LookAheadSelector<M1, M2, MATCH_OUTPUT> {
157 public:
158 typedef typename M2::FST F2;
159
LookAheadSelector(M1 * lmatcher1,M2 * lmatcher2,MatchType)160 LookAheadSelector(M1 *lmatcher1, M2 *lmatcher2, MatchType)
161 : fst_(lmatcher2->GetFst().Copy()),
162 lmatcher_(lmatcher1->Copy()) {}
163
LookAheadSelector(const LookAheadSelector<M1,M2,MATCH_OUTPUT> & selector)164 LookAheadSelector(const LookAheadSelector<M1, M2, MATCH_OUTPUT> &selector)
165 : fst_(selector.fst_->Copy()),
166 lmatcher_(selector.lmatcher_->Copy()) {}
167
~LookAheadSelector()168 ~LookAheadSelector() {
169 delete lmatcher_;
170 delete fst_;
171 }
172
GetFst()173 const F2 &GetFst() const { return *fst_; }
174
GetMatcher()175 M1 *GetMatcher() const { return lmatcher_; }
176
177 private:
178 const F2 *fst_;
179 M1 *lmatcher_;
180
181 void operator=(const LookAheadSelector<M1, M2, MATCH_OUTPUT> &); // disallow
182 };
183
184 // This filter uses a lookahead matcher in FilterArc(arc1, arc2) to
185 // examine the future of the composition state (arc1.nextstate,
186 // arc2.nextstate), blocking moving forward when its determined to be
187 // non-coaccessible. It is templated on an underlying filter,
188 // typically the epsilon filter. Which matcher is the lookahead
189 // matcher is determined by the template argument MT unless it is
190 // MATCH_BOTH. In that case, both matcher arguments must be lookahead
191 // matchers of the same type and one will be selected by
192 // LookAheadMatchType() based on their capability.
193 template <class F,
194 class M1 = LookAheadMatcher<typename F::FST1>,
195 class M2 = M1,
196 MatchType MT = MATCH_BOTH>
197 class LookAheadComposeFilter {
198 public:
199 typedef typename F::FST1 FST1;
200 typedef typename F::FST2 FST2;
201 typedef typename F::Arc Arc;
202 typedef typename F::Matcher1 Matcher1;
203 typedef typename F::Matcher2 Matcher2;
204 typedef typename F::FilterState FilterState;
205 typedef LookAheadComposeFilter<F, M1, M2, MT> Filter;
206
207 typedef typename Arc::StateId StateId;
208 typedef typename Arc::Label Label;
209 typedef typename Arc::Weight Weight;
210
LookAheadComposeFilter(const FST1 & fst1,const FST2 & fst2,M1 * matcher1,M2 * matcher2)211 LookAheadComposeFilter(const FST1 &fst1, const FST2 &fst2,
212 M1 *matcher1, M2 *matcher2)
213 : filter_(fst1, fst2, matcher1, matcher2),
214 lookahead_type_(MT == MATCH_BOTH ?
215 LookAheadMatchType(*filter_.GetMatcher1(),
216 *filter_.GetMatcher2()) : MT),
217 selector_(filter_.GetMatcher1(), filter_.GetMatcher2(),
218 lookahead_type_),
219 flags_(lookahead_type_ == MATCH_OUTPUT ?
220 filter_.GetMatcher1()->Flags() :
221 filter_.GetMatcher2()->Flags()) {
222 if (lookahead_type_ == MATCH_NONE) {
223 FSTERROR() << "LookAheadComposeFilter: 1st argument cannot "
224 << "match/look-ahead on output labels and 2nd argument "
225 << "cannot match/look-ahead on input labels.";
226 }
227 selector_.GetMatcher()->InitLookAheadFst(selector_.GetFst());
228 }
229
230 LookAheadComposeFilter(const LookAheadComposeFilter<F, M1, M2, MT> &filter,
231 bool safe = false)
232 : filter_(filter.filter_, safe),
233 lookahead_type_(filter.lookahead_type_),
234 selector_(filter_.GetMatcher1(), filter_.GetMatcher2(),
235 lookahead_type_),
236 flags_(filter.flags_) {
237 selector_.GetMatcher()->InitLookAheadFst(selector_.GetFst(), true);
238 }
239
Start()240 FilterState Start() const {
241 return filter_.Start();
242 }
243
SetState(StateId s1,StateId s2,const FilterState & f)244 void SetState(StateId s1, StateId s2, const FilterState &f) {
245 filter_.SetState(s1, s2, f);
246 }
247
FilterArc(Arc * arc1,Arc * arc2)248 FilterState FilterArc(Arc *arc1, Arc *arc2) const {
249 lookahead_arc_ = false;
250
251 const FilterState &f = filter_.FilterArc(arc1, arc2);
252 if (f == FilterState::NoState())
253 return FilterState::NoState();
254
255 return LookAheadOutput() ? LookAheadFilterArc(arc1, arc2, f) :
256 LookAheadFilterArc(arc2, arc1, f);
257 }
258
FilterFinal(Weight * weight1,Weight * weight2)259 void FilterFinal(Weight *weight1, Weight *weight2) const {
260 filter_.FilterFinal(weight1, weight2);
261 }
262
263 // Return resp matchers. Ownership stays with filter.
GetMatcher1()264 Matcher1 *GetMatcher1() { return filter_.GetMatcher1(); }
GetMatcher2()265 Matcher2 *GetMatcher2() { return filter_.GetMatcher2(); }
266
Selector()267 const LookAheadSelector<Matcher1, Matcher2, MT> &Selector() const {
268 return selector_;
269 }
270
Properties(uint64 inprops)271 uint64 Properties(uint64 inprops) const {
272 uint64 outprops = filter_.Properties(inprops);
273 if (lookahead_type_ == MATCH_NONE)
274 outprops |= kError;
275 return outprops;
276 }
277
LookAheadFlags()278 uint32 LookAheadFlags() const { return flags_; }
279
LookAheadArc()280 bool LookAheadArc() const { return lookahead_arc_; }
281
LookAheadOutput()282 bool LookAheadOutput() const {
283 if (MT == MATCH_OUTPUT)
284 return true;
285 else if (MT == MATCH_INPUT)
286 return false;
287 else if (lookahead_type_ == MATCH_OUTPUT)
288 return true;
289 else
290 return false;
291 }
292
293 private:
LookAheadFilterArc(Arc * arca,Arc * arcb,const FilterState & f)294 FilterState LookAheadFilterArc(Arc *arca, Arc *arcb,
295 const FilterState &f) const {
296 Label &labela = LookAheadOutput() ? arca->olabel : arca->ilabel;
297
298 if (labela != 0 && !(flags_ & kLookAheadNonEpsilons))
299 return f;
300 if (labela == 0 && !(flags_ & kLookAheadEpsilons))
301 return f;
302
303 lookahead_arc_ = true;
304 selector_.GetMatcher()->SetState(arca->nextstate);
305
306 return selector_.GetMatcher()->LookAheadFst(selector_.GetFst(),
307 arcb->nextstate) ? f :
308 FilterState::NoState();
309 }
310
311 F filter_; // Underlying filter
312 MatchType lookahead_type_; // Lookahead match type
313 LookAheadSelector<Matcher1, Matcher2, MT> selector_;
314 uint32 flags_; // Lookahead flags
315 mutable bool lookahead_arc_; // Look-ahead performed at last FilterArc()?
316
317 void operator=(const LookAheadComposeFilter<F, M1, M2> &); // disallow
318 };
319
320
321 // This filter adds weight-pushing to a lookahead composition filter
322 // using the LookAheadWeight() method of matcher argument. It is
323 // templated on an underlying lookahead filter, typically the basic
324 // lookahead filter. Weight-pushing in composition brings weights
325 // forward as much as possible based on the lookahead information.
326 template <class F,
327 class M1 = LookAheadMatcher<typename F::FST1>,
328 class M2 = M1,
329 MatchType MT = MATCH_BOTH>
330 class PushWeightsComposeFilter {
331 public:
332 typedef typename F::FST1 FST1;
333 typedef typename F::FST2 FST2;
334 typedef typename F::Arc Arc;
335 typedef typename F::Matcher1 Matcher1;
336 typedef typename F::Matcher2 Matcher2;
337 typedef typename F::FilterState FilterState1;
338 typedef WeightFilterState<typename Arc::Weight> FilterState2;
339 typedef PairFilterState<FilterState1, FilterState2> FilterState;
340
341 typedef typename Arc::StateId StateId;
342 typedef typename Arc::Label Label;
343 typedef typename Arc::Weight Weight;
344
PushWeightsComposeFilter(const FST1 & fst1,const FST2 & fst2,M1 * matcher1,M2 * matcher2)345 PushWeightsComposeFilter(const FST1 &fst1, const FST2 &fst2,
346 M1 *matcher1, M2 *matcher2)
347 : filter_(fst1, fst2, matcher1, matcher2),
348 f_(FilterState::NoState()) {}
349
350 PushWeightsComposeFilter(const PushWeightsComposeFilter<F, M1, M2, MT>
351 &filter,
352 bool safe = false)
353 : filter_(filter.filter_, safe),
354 f_(FilterState::NoState()) {}
355
Start()356 FilterState Start() const {
357 return FilterState(filter_.Start(), FilterState2(Weight::One()));
358 }
359
SetState(StateId s1,StateId s2,const FilterState & f)360 void SetState(StateId s1, StateId s2, const FilterState &f) {
361 f_ = f;
362 filter_.SetState(s1, s2, f.GetState1());
363 }
364
FilterArc(Arc * arc1,Arc * arc2)365 FilterState FilterArc(Arc *arc1, Arc *arc2) const {
366 const FilterState1 &f1 = filter_.FilterArc(arc1, arc2);
367 if (f1 == FilterState1::NoState())
368 return FilterState::NoState();
369
370 if (!(LookAheadFlags() & kLookAheadWeight))
371 return FilterState(f1, FilterState2(Weight::One()));
372
373 const Weight &lweight = filter_.LookAheadArc() ?
374 Selector().GetMatcher()->LookAheadWeight() : Weight::One();
375 const FilterState2 &f2 = f_.GetState2();
376 const Weight &fweight = f2.GetWeight();
377
378 arc2->weight = Divide(Times(arc2->weight, lweight), fweight);
379 return FilterState(f1, FilterState2(lweight));
380 }
381
FilterFinal(Weight * weight1,Weight * weight2)382 void FilterFinal(Weight *weight1, Weight *weight2) const {
383 filter_.FilterFinal(weight1, weight2);
384 if (!(LookAheadFlags() & kLookAheadWeight) || *weight1 == Weight::Zero())
385 return;
386
387 const FilterState2 &f2 = f_.GetState2();
388 const Weight &fweight = f2.GetWeight();
389 *weight1 = Divide(*weight1, fweight);
390 }
391 // Return resp matchers. Ownership states with filter.
GetMatcher1()392 Matcher1 *GetMatcher1() { return filter_.GetMatcher1(); }
GetMatcher2()393 Matcher2 *GetMatcher2() { return filter_.GetMatcher2(); }
394
Selector()395 const LookAheadSelector<Matcher1, Matcher2, MT> &Selector() const {
396 return filter_.Selector();
397 }
398
LookAheadFlags()399 uint32 LookAheadFlags() const { return filter_.LookAheadFlags(); }
LookAheadArc()400 bool LookAheadArc() const { return filter_.LookAheadArc(); }
LookAheadOutput()401 bool LookAheadOutput() const { return filter_.LookAheadOutput(); }
402
Properties(uint64 props)403 uint64 Properties(uint64 props) const {
404 return filter_.Properties(props) & kWeightInvariantProperties;
405 }
406
407 private:
408 F filter_; // Underlying filter
409 FilterState f_; // Current filter state
410
411 void operator=(const PushWeightsComposeFilter<F, M1, M2, MT> &); // disallow
412 };
413
414 // This filter adds label-pushing to a lookahead composition filter
415 // using the LookAheadPrefix() method of the matcher argument. It is
416 // templated on an underlying filter, typically the basic lookahead
417 // or weight-pushing lookahead filter. Label-pushing in composition
418 // matches labels as early as possible based on the lookahead
419 // information.
420 template <class F,
421 class M1 = LookAheadMatcher<typename F::FST1>,
422 class M2 = M1,
423 MatchType MT = MATCH_BOTH>
424 class PushLabelsComposeFilter {
425 public:
426 typedef typename F::FST1 FST1;
427 typedef typename F::FST2 FST2;
428 typedef typename F::Arc Arc;
429 typedef typename Arc::StateId StateId;
430 typedef typename Arc::Label Label;
431 typedef typename Arc::Weight Weight;
432
433 typedef MultiEpsMatcher<typename F::Matcher1> Matcher1;
434 typedef MultiEpsMatcher<typename F::Matcher2> Matcher2;
435 typedef typename F::FilterState FilterState1;
436 typedef IntegerFilterState<typename Arc::Label> FilterState2;
437 typedef PairFilterState<FilterState1, FilterState2> FilterState;
438
PushLabelsComposeFilter(const FST1 & fst1,const FST2 & fst2,M1 * matcher1,M2 * matcher2)439 PushLabelsComposeFilter(const FST1 &fst1, const FST2 &fst2,
440 M1 *matcher1, M2 *matcher2)
441 : filter_(fst1, fst2, matcher1, matcher2),
442 f_(FilterState::NoState()),
443 fst1_(filter_.GetMatcher1()->GetFst()),
444 fst2_(filter_.GetMatcher2()->GetFst()),
445 matcher1_(fst1_, MATCH_OUTPUT,
446 filter_.LookAheadOutput() ? kMultiEpsList : kMultiEpsLoop,
447 filter_.GetMatcher1(),
448 false),
449 matcher2_(fst2_, MATCH_INPUT,
450 filter_.LookAheadOutput() ? kMultiEpsLoop : kMultiEpsList,
451 filter_.GetMatcher2(),
452 false) {}
453
454 PushLabelsComposeFilter(const PushLabelsComposeFilter<F, M1, M2, MT> &filter,
455 bool safe = false)
456 : filter_(filter.filter_, safe),
457 f_(FilterState::NoState()),
458 fst1_(filter_.GetMatcher1()->GetFst()),
459 fst2_(filter_.GetMatcher2()->GetFst()),
460 matcher1_(fst1_, MATCH_OUTPUT,
461 filter_.LookAheadOutput() ? kMultiEpsList : kMultiEpsLoop,
462 filter_.GetMatcher1(),
463 false),
464 matcher2_(fst2_, MATCH_INPUT,
465 filter_.LookAheadOutput() ? kMultiEpsLoop : kMultiEpsList,
466 filter_.GetMatcher2(),
467 false) {
468 }
469
Start()470 FilterState Start() const {
471 return FilterState(filter_.Start(), FilterState2(kNoLabel));
472 }
473
SetState(StateId s1,StateId s2,const FilterState & f)474 void SetState(StateId s1, StateId s2, const FilterState &f) {
475 f_ = f;
476 filter_.SetState(s1, s2, f.GetState1());
477 if (!(LookAheadFlags() & kLookAheadPrefix))
478 return;
479
480 narcsa_ = LookAheadOutput() ? internal::NumArcs(fst1_, s1)
481 : internal::NumArcs(fst2_, s2);
482
483 const FilterState2 &f2 = f_.GetState2();
484 const Label &flabel = f2.GetState();
485
486 GetMatcher1()->ClearMultiEpsLabels();
487 GetMatcher2()->ClearMultiEpsLabels();
488 if (flabel != kNoLabel) { // Have a lookahead label?
489 GetMatcher1()->AddMultiEpsLabel(flabel); // Yes, make it a multi-epsilon
490 GetMatcher2()->AddMultiEpsLabel(flabel); // label so that it matches the
491 } // implicit epsilon arc to be
492 } // modified below when pushing.
493
FilterArc(Arc * arc1,Arc * arc2)494 FilterState FilterArc(Arc *arc1, Arc *arc2) const {
495 if (!(LookAheadFlags() & kLookAheadPrefix))
496 return FilterState(filter_.FilterArc(arc1, arc2),
497 FilterState2(kNoLabel));
498
499 const FilterState2 &f2 = f_.GetState2();
500 const Label &flabel = f2.GetState();
501 if (flabel != kNoLabel) // Have a lookahead label?
502 return LookAheadOutput() ? PushedLabelFilterArc(arc1, arc2, flabel) :
503 PushedLabelFilterArc(arc2, arc1, flabel);
504
505 const FilterState1 &f1 = filter_.FilterArc(arc1, arc2);
506 if (f1 == FilterState1::NoState())
507 return FilterState::NoState();
508
509 if (!filter_.LookAheadArc())
510 return FilterState(f1, FilterState2(kNoLabel));
511
512 return LookAheadOutput() ? PushLabelFilterArc(arc1, arc2, f1) :
513 PushLabelFilterArc(arc2, arc1, f1);
514 }
515
FilterFinal(Weight * weight1,Weight * weight2)516 void FilterFinal(Weight *weight1, Weight *weight2) const {
517 filter_.FilterFinal(weight1, weight2);
518 if (!(LookAheadFlags() & kLookAheadPrefix) ||
519 *weight1 == Weight::Zero())
520 return;
521
522 const FilterState2 &f2 = f_.GetState2();
523 const Label &flabel = f2.GetState();
524 if (flabel != kNoLabel)
525 *weight1 = Weight::Zero();
526 }
527
528 // Return resp matchers. Ownership states with filter.
GetMatcher1()529 Matcher1 *GetMatcher1() { return &matcher1_; }
GetMatcher2()530 Matcher2 *GetMatcher2() { return &matcher2_; }
531
Properties(uint64 iprops)532 uint64 Properties(uint64 iprops) const {
533 uint64 oprops = filter_.Properties(iprops);
534 if (LookAheadOutput())
535 return oprops & kOLabelInvariantProperties;
536 else
537 return oprops & kILabelInvariantProperties;
538 }
539
540 private:
541 const LookAheadSelector<typename F::Matcher1, typename F::Matcher2, MT>
Selector()542 &Selector() const {
543 return filter_.Selector();
544 }
545
546 // Consumes an already pushed label.
PushedLabelFilterArc(Arc * arca,Arc * arcb,Label flabel)547 FilterState PushedLabelFilterArc(Arc *arca, Arc *arcb,
548 Label flabel) const {
549 Label &labela = LookAheadOutput() ? arca->olabel : arca->ilabel;
550 const Label &labelb = LookAheadOutput() ? arcb->ilabel : arcb->olabel;
551
552 if (labelb != kNoLabel) {
553 return FilterState::NoState(); // Block non- (multi-) epsilon label
554 } else if (labela == flabel) {
555 labela = 0; // Convert match to multi-eps to eps
556 return Start();
557 } else if (labela == 0) {
558 if (narcsa_ == 1)
559 return f_; // Take eps; keep state w/ label
560 Selector().GetMatcher()->SetState(arca->nextstate);
561 if (Selector().GetMatcher()->LookAheadLabel(flabel))
562 return f_; // Take eps; keep state w/ label
563 else
564 return FilterState::NoState(); // Block non-coaccessible path
565 } else {
566 return FilterState::NoState(); // Block mismatch to multi-eps label
567 }
568 }
569
570 // Pushes a label forward when possible.
PushLabelFilterArc(Arc * arca,Arc * arcb,const FilterState1 & f1)571 FilterState PushLabelFilterArc(Arc *arca, Arc *arcb,
572 const FilterState1 &f1) const {
573 Label &labela = LookAheadOutput() ? arca->olabel : arca->ilabel;
574 const Label &labelb = LookAheadOutput() ? arcb->olabel : arcb->ilabel;
575
576 if (labelb != 0) // No place to push.
577 return FilterState(f1, FilterState2(kNoLabel));
578 if (labela != 0 && // Wrong lookahead prefix type?
579 LookAheadFlags() & kLookAheadNonEpsilonPrefix)
580 return FilterState(f1, FilterState2(kNoLabel));
581
582 Arc larc(kNoLabel, kNoLabel, Weight::Zero(), kNoStateId);
583
584 if (Selector().GetMatcher()->LookAheadPrefix(&larc)) { // Have prefix arc?
585 labela = LookAheadOutput() ? larc.ilabel : larc.olabel;
586 arcb->ilabel = larc.ilabel; // Yes, go forward on that arc,
587 arcb->olabel = larc.olabel; // thus pushing the label.
588 arcb->weight = Times(arcb->weight, larc.weight);
589 arcb->nextstate = larc.nextstate;
590 return FilterState(f1, FilterState2(labela));
591 } else {
592 return FilterState(f1, FilterState2(kNoLabel));
593 }
594 }
595
LookAheadFlags()596 uint32 LookAheadFlags() const { return filter_.LookAheadFlags(); }
LookAheadArc()597 bool LookAheadArc() const { return filter_.LookAheadArc(); }
LookAheadOutput()598 bool LookAheadOutput() const { return filter_.LookAheadOutput(); }
599
600 F filter_; // Underlying filter
601 FilterState f_ ; // Current filter state
602 const FST1 &fst1_;
603 const FST2 &fst2_;
604 Matcher1 matcher1_; // Multi-epsilon matcher for fst1
605 Matcher2 matcher2_; // Multi-epsilon matcher for fst2
606 ssize_t narcsa_; // Number of arcs leaving look-ahead match FST
607
608 void operator=(const PushLabelsComposeFilter<F, M1, M2, MT> &); // disallow
609 };
610
611 //
612 // CONVENIENCE CLASS useful for setting up composition with a default
613 // look-ahead matcher and filter.
614 //
615
616 template <class A, MatchType type> // MATCH_NONE
617 class DefaultLookAhead {
618 public:
619 typedef Matcher< Fst<A> > M;
620 typedef SequenceComposeFilter<M> ComposeFilter;
621 typedef M FstMatcher;
622 };
623
624 // Specializes for MATCH_INPUT to allow lookahead.
625 template <class A>
626 class DefaultLookAhead<A, MATCH_INPUT> {
627 public:
628 typedef LookAheadMatcher< Fst<A> > M;
629 typedef SequenceComposeFilter<M> SF;
630 typedef LookAheadComposeFilter<SF, M> ComposeFilter;
631 typedef M FstMatcher;
632 };
633
634 // Specializes for MATCH_OUTPUT to allow lookahead.
635 template <class A>
636 class DefaultLookAhead<A, MATCH_OUTPUT> {
637 public:
638 typedef LookAheadMatcher< Fst<A> > M;
639 typedef AltSequenceComposeFilter<M> SF;
640 typedef LookAheadComposeFilter<SF, M> ComposeFilter;
641 typedef M FstMatcher;
642 };
643
644 // Specializes for StdArc to allow weight and label pushing.
645 template <>
646 class DefaultLookAhead<StdArc, MATCH_INPUT> {
647 public:
648 typedef StdArc A;
649 typedef LookAheadMatcher< Fst<A> > M;
650 typedef SequenceComposeFilter<M> SF;
651 typedef LookAheadComposeFilter<SF, M> LF;
652 typedef PushWeightsComposeFilter<LF, M> WF;
653 typedef PushLabelsComposeFilter<WF, M> ComposeFilter;
654 typedef M FstMatcher;
655 };
656
657 // Specializes for StdArc to allow weight and label pushing.
658 template <>
659 class DefaultLookAhead<StdArc, MATCH_OUTPUT> {
660 public:
661 typedef StdArc A;
662 typedef LookAheadMatcher< Fst<A> > M;
663 typedef AltSequenceComposeFilter<M> SF;
664 typedef LookAheadComposeFilter<SF, M> LF;
665 typedef PushWeightsComposeFilter<LF, M> WF;
666 typedef PushLabelsComposeFilter<WF, M> ComposeFilter;
667 typedef M FstMatcher;
668 };
669
670 // Specializes for LogArc to allow weight and label pushing.
671 template <>
672 class DefaultLookAhead<LogArc, MATCH_INPUT> {
673 public:
674 typedef LogArc A;
675 typedef LookAheadMatcher< Fst<A> > M;
676 typedef SequenceComposeFilter<M> SF;
677 typedef LookAheadComposeFilter<SF, M> LF;
678 typedef PushWeightsComposeFilter<LF, M> WF;
679 typedef PushLabelsComposeFilter<WF, M> ComposeFilter;
680 typedef M FstMatcher;
681 };
682
683 // Specializes for LogArc to allow weight and label pushing.
684 template <>
685 class DefaultLookAhead<LogArc, MATCH_OUTPUT> {
686 public:
687 typedef LogArc A;
688 typedef LookAheadMatcher< Fst<A> > M;
689 typedef AltSequenceComposeFilter<M> SF;
690 typedef LookAheadComposeFilter<SF, M> LF;
691 typedef PushWeightsComposeFilter<LF, M> WF;
692 typedef PushLabelsComposeFilter<WF, M> ComposeFilter;
693 typedef M FstMatcher;
694 };
695
696 } // namespace fst
697
698 #endif // FST_LIB_LOOKAHEAD_FILTER_H__
699