reverse.h revision 4a68b3365c8c50aa93505e99ead2565ab73dcdb0
1a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// reverse.h 2a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// 3a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// Licensed under the Apache License, Version 2.0 (the "License"); 4a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// you may not use this file except in compliance with the License. 5a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// You may obtain a copy of the License at 6a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// 7a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// http://www.apache.org/licenses/LICENSE-2.0 8a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// 9a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// Unless required by applicable law or agreed to in writing, software 10a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar// distributed under the License is distributed on an "AS IS" BASIS, 11ddf6bdde44287b5b559bc403a02ff971e15e8303Chris Lattner// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby// See the License for the specific language governing permissions and 13484291c27319668ad99cb87def000254357736fbRafael Espindola// limitations under the License. 14d79d9dce47d505369662ae5111dba24f9ccdef68Chris Lattner// 1558bc4dd4a91443ddd3120b0a2f1801ad4d6aae1cChris Lattner// 1658bc4dd4a91443ddd3120b0a2f1801ad4d6aae1cChris Lattner// \file 173580dea910d622f2a6dbb72e97f5f7d0ef979542Chris Lattner// Functions and classes to sort arcs in an FST. 18a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar 19a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar#ifndef FST_LIB_REVERSE_H__ 201674b0b0e4972b844833f253286cbf99a6e99d6eBenjamin Kramer#define FST_LIB_REVERSE_H__ 211674b0b0e4972b844833f253286cbf99a6e99d6eBenjamin Kramer 22a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar#include "fst/lib/cache.h" 23a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar 24a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbarnamespace fst { 25a11af531ec48ad84f790b9511f003ac5c934a999Daniel Dunbar 26ddf6bdde44287b5b559bc403a02ff971e15e8303Chris Lattner// Reverses an FST. The reversed result is written to an output 27d79d9dce47d505369662ae5111dba24f9ccdef68Chris Lattner// MutableFst. If A transduces string x to y with weight a, then the 28d79d9dce47d505369662ae5111dba24f9ccdef68Chris Lattner// reverse of A transduces the reverse of x to the reverse of y with 29d79d9dce47d505369662ae5111dba24f9ccdef68Chris Lattner// weight a.Reverse(). 30d79d9dce47d505369662ae5111dba24f9ccdef68Chris Lattner// 31d79d9dce47d505369662ae5111dba24f9ccdef68Chris Lattner// Typically, a = a.Reverse() and Arc = RevArc (e.g. for 32d79d9dce47d505369662ae5111dba24f9ccdef68Chris Lattner// TropicalWeight or LogWeight). In general, e.g. when the weights 3332ae3fe0ba469240753e2342e36485f7c9acfb5cChris Lattner// only form a left or right semiring, the output arc type must match 3432ae3fe0ba469240753e2342e36485f7c9acfb5cChris Lattner// the input arc type except having the reversed Weight type. 3532ae3fe0ba469240753e2342e36485f7c9acfb5cChris Lattnertemplate<class Arc, class RevArc> 3632ae3fe0ba469240753e2342e36485f7c9acfb5cChris Lattnervoid Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst) { 3732ae3fe0ba469240753e2342e36485f7c9acfb5cChris Lattner typedef typename Arc::StateId StateId; 3832ae3fe0ba469240753e2342e36485f7c9acfb5cChris Lattner typedef typename Arc::Weight Weight; 3932ae3fe0ba469240753e2342e36485f7c9acfb5cChris Lattner typedef typename RevArc::Weight RevWeight; 40c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby 41c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby ofst->DeleteStates(); 42c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby ofst->SetInputSymbols(ifst.InputSymbols()); 43c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby ofst->SetOutputSymbols(ifst.OutputSymbols()); 44c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby StateId istart = ifst.Start(); 45c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby StateId ostart = ofst->AddState(); 46c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby ofst->SetStart(ostart); 47c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby 48c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby for (StateIterator< Fst<Arc> > siter(ifst); 49c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby !siter.Done(); 50c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby siter.Next()) { 51c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby StateId is = siter.Value(); 52c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby StateId os = is + 1; 53c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby while (ofst->NumStates() <= os) 54c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby ofst->AddState(); 55c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby if (is == istart) 56c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby ofst->SetFinal(os, RevWeight::One()); 57c095793b4ab027181605c79c9808df12afe45d63Kevin Enderby 586cde3e6e993126df756e3be5b9ef43540b904644Chris Lattner Weight final = ifst.Final(is); 596cde3e6e993126df756e3be5b9ef43540b904644Chris Lattner if (final != Weight::Zero()) { 606cde3e6e993126df756e3be5b9ef43540b904644Chris Lattner RevArc oarc(0, 0, final.Reverse(), os); 616cde3e6e993126df756e3be5b9ef43540b904644Chris Lattner ofst->AddArc(0, oarc); 626cde3e6e993126df756e3be5b9ef43540b904644Chris Lattner } 63ddf6bdde44287b5b559bc403a02ff971e15e8303Chris Lattner 64ddf6bdde44287b5b559bc403a02ff971e15e8303Chris Lattner for (ArcIterator< Fst<Arc> > aiter(ifst, is); 65aaec205b87637cd0d59d4f11630db603686eb73dChris Lattner !aiter.Done(); 66aaec205b87637cd0d59d4f11630db603686eb73dChris Lattner aiter.Next()) { 67ddf6bdde44287b5b559bc403a02ff971e15e8303Chris Lattner const Arc &iarc = aiter.Value(); 68ddf6bdde44287b5b559bc403a02ff971e15e8303Chris Lattner RevArc oarc(iarc.ilabel, iarc.olabel, iarc.weight.Reverse(), os); 69aaec205b87637cd0d59d4f11630db603686eb73dChris Lattner StateId nos = iarc.nextstate + 1; 70ddf6bdde44287b5b559bc403a02ff971e15e8303Chris Lattner while (ofst->NumStates() <= nos) 7191bead790518fcf5cb26019fb1ebf2372e8a5b3fChris Lattner ofst->AddState(); 72ab3b3651add0915a5a051b177029ad117a877f52Matt Fleming ofst->AddArc(nos, oarc); 7391bead790518fcf5cb26019fb1ebf2372e8a5b3fChris Lattner } 7491bead790518fcf5cb26019fb1ebf2372e8a5b3fChris Lattner } 7591bead790518fcf5cb26019fb1ebf2372e8a5b3fChris Lattner uint64 iprops = ifst.Properties(kCopyProperties, false); 7691bead790518fcf5cb26019fb1ebf2372e8a5b3fChris Lattner uint64 oprops = ofst->Properties(kFstProperties, false); 7791bead790518fcf5cb26019fb1ebf2372e8a5b3fChris Lattner ofst->SetProperties(ReverseProperties(iprops) | oprops, kFstProperties); 7891bead790518fcf5cb26019fb1ebf2372e8a5b3fChris Lattner} 7991bead790518fcf5cb26019fb1ebf2372e8a5b3fChris Lattner 8058bc4dd4a91443ddd3120b0a2f1801ad4d6aae1cChris Lattner} // namespace fst 8158bc4dd4a91443ddd3120b0a2f1801ad4d6aae1cChris Lattner 8258bc4dd4a91443ddd3120b0a2f1801ad4d6aae1cChris Lattner#endif // FST_LIB_REVERSE_H__ 8358bc4dd4a91443ddd3120b0a2f1801ad4d6aae1cChris Lattner