arc.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2
1bb481f882093fb738d2bb15610c79364bada5496Jia Liu// arc.h 2972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes 3972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// Licensed under the Apache License, Version 2.0 (the "License"); 4972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// you may not use this file except in compliance with the License. 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// You may obtain a copy of the License at 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 7972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// http://www.apache.org/licenses/LICENSE-2.0 84552c9a3b34ad9b2085635266348d0d9b95514a6Akira Hatanaka// 9972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// Unless required by applicable law or agreed to in writing, software 106f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman// distributed under the License is distributed on an "AS IS" BASIS, 11972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124552c9a3b34ad9b2085635266348d0d9b95514a6Akira Hatanaka// See the License for the specific language governing permissions and 13972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// limitations under the License. 14972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// 15972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// Copyright 2005-2010 Google, Inc. 16972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// Author: riley@google.com (Michael Riley) 1743d526d162c69f29a1cc6734014576eade49529bBruno Cardoso Lopes// 186f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman// \file 1973f50d9bc3bd46cc0abeba9bb0d46977ba1aea42Evan Cheng// 2073f50d9bc3bd46cc0abeba9bb0d46977ba1aea42Evan Cheng// Commonly used Fst arc types. 2173f50d9bc3bd46cc0abeba9bb0d46977ba1aea42Evan Cheng 22972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes#ifndef FST_LIB_ARC_H__ 23972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes#define FST_LIB_ARC_H__ 2443d526d162c69f29a1cc6734014576eade49529bBruno Cardoso Lopes 25972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes#include <string> 26972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes 27972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes 28972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes#include <fst/expectation-weight.h> 2943d526d162c69f29a1cc6734014576eade49529bBruno Cardoso Lopes#include <fst/float-weight.h> 30972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes#include <fst/lexicographic-weight.h> 3181092dc20abe5253a5b4d48a75997baa84dde196Bruno Cardoso Lopes#include <fst/power-weight.h> 3243d526d162c69f29a1cc6734014576eade49529bBruno Cardoso Lopes#include <fst/product-weight.h> 33972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes#include <fst/signed-log-weight.h> 3451195af45f4142035f23c7d58d1311face3900a4Bruno Cardoso Lopes#include <fst/sparse-power-weight.h> 3551195af45f4142035f23c7d58d1311face3900a4Bruno Cardoso Lopes#include <iostream> 3651195af45f4142035f23c7d58d1311face3900a4Bruno Cardoso Lopes#include <fstream> 3751195af45f4142035f23c7d58d1311face3900a4Bruno Cardoso Lopes#include <fst/string-weight.h> 3843d526d162c69f29a1cc6734014576eade49529bBruno Cardoso Lopes 39a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman 4043d526d162c69f29a1cc6734014576eade49529bBruno Cardoso Lopesnamespace fst { 41bbe51362d53a532942997903a49faa7b5b50ad1fBruno Cardoso Lopes 42bbe51362d53a532942997903a49faa7b5b50ad1fBruno Cardoso Lopestemplate <class W> 43bbe51362d53a532942997903a49faa7b5b50ad1fBruno Cardoso Lopesclass ArcTpl { 44972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes public: 45015f228861ef9b337366f92f637d4e8d624bb006Craig Topper typedef W Weight; 46b2930b92d3e9734ced6679844666799648ebbd7aAkira Hatanaka typedef int Label; 47972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes typedef int StateId; 48972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes 49972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes ArcTpl(Label i, Label o, const Weight& w, StateId s) 5081a424b3c5e7be03d66d5c7fd241f2aac47d1a2cAkira Hatanaka : ilabel(i), olabel(o), weight(w), nextstate(s) {} 5181a424b3c5e7be03d66d5c7fd241f2aac47d1a2cAkira Hatanaka 526a8c7bf8e72338e55f0f9583e1828f62da165d4aPreston Gurd ArcTpl() {} 536a8c7bf8e72338e55f0f9583e1828f62da165d4aPreston Gurd 54972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes static const string &Type(void) { 55972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes static const string type = 56972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes (Weight::Type() == "tropical") ? "standard" : Weight::Type(); 57972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes return type; 5851195af45f4142035f23c7d58d1311face3900a4Bruno Cardoso Lopes } 59fcb4a8ead3cd8d9540d5eaa448af5d14a0ee341aJim Grosbach 60fcb4a8ead3cd8d9540d5eaa448af5d14a0ee341aJim Grosbach Label ilabel; 61972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes Label olabel; 62972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes Weight weight; 63972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes StateId nextstate; 6451195af45f4142035f23c7d58d1311face3900a4Bruno Cardoso Lopes}; 65b9c2fd964ee7dd7823ac71db8443055e4d0f1c15David Greene 66972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopestypedef ArcTpl<TropicalWeight> StdArc; 6751195af45f4142035f23c7d58d1311face3900a4Bruno Cardoso Lopestypedef ArcTpl<LogWeight> LogArc; 68972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopestypedef ArcTpl<Log64Weight> Log64Arc; 69972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopestypedef ArcTpl<SignedLogWeight> SignedLogArc; 70972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopestypedef ArcTpl<SignedLog64Weight> SignedLog64Arc; 71972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopestypedef ArcTpl<MinMaxWeight> MinMaxArc; 72972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes 73972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes 74972f5896e417d8e81cf400083fab15a37b6d4277Bruno Cardoso Lopes// Arc with integer labels and state Ids and string weights. 75template <StringType S = STRING_LEFT> 76class StringArc { 77 public: 78 typedef int Label; 79 typedef StringWeight<int, S> Weight; 80 typedef int StateId; 81 82 StringArc(Label i, Label o, Weight w, StateId s) 83 : ilabel(i), olabel(o), weight(w), nextstate(s) {} 84 85 StringArc() {} 86 87 static const string &Type() { // Arc type name 88 static const string type = 89 S == STRING_LEFT ? "standard_string" : 90 (S == STRING_RIGHT ? "right_standard_string" : 91 (S == STRING_LEFT_RESTRICT ? "restricted_string" : 92 "right_restricted_string")); 93 return type; 94 } 95 96 Label ilabel; // Transition input label 97 Label olabel; // Transition output label 98 Weight weight; // Transition weight 99 StateId nextstate; // Transition destination state 100}; 101 102 103// Arc with label and state Id type the same as template arg and with 104// weights over the Gallic semiring w.r.t the output labels and weights of A. 105template <class A, StringType S = STRING_LEFT> 106struct GallicArc { 107 typedef A Arc; 108 typedef typename A::Label Label; 109 typedef typename A::StateId StateId; 110 typedef GallicWeight<Label, typename A::Weight, S> Weight; 111 112 GallicArc() {} 113 114 GallicArc(Label i, Label o, Weight w, StateId s) 115 : ilabel(i), olabel(o), weight(w), nextstate(s) {} 116 117 GallicArc(const A &arc) 118 : ilabel(arc.ilabel), olabel(arc.ilabel), 119 weight(arc.olabel, arc.weight), nextstate(arc.nextstate) {} 120 121 static const string &Type() { // Arc type name 122 static const string type = 123 (S == STRING_LEFT ? "gallic_" : 124 (S == STRING_RIGHT ? "right_gallic_" : 125 (S == STRING_LEFT_RESTRICT ? "restricted_gallic_" : 126 "right_restricted_gallic_"))) + A::Type(); 127 return type; 128 } 129 130 Label ilabel; // Transition input label 131 Label olabel; // Transition output label 132 Weight weight; // Transition weight 133 StateId nextstate; // Transition destination state 134}; 135 136 137// Arc with the reverse of the weight found in its template arg. 138template <class A> struct ReverseArc { 139 typedef A Arc; 140 typedef typename A::Label Label; 141 typedef typename A::Weight AWeight; 142 typedef typename AWeight::ReverseWeight Weight; 143 typedef typename A::StateId StateId; 144 145 ReverseArc(Label i, Label o, Weight w, StateId s) 146 : ilabel(i), olabel(o), weight(w), nextstate(s) {} 147 148 ReverseArc() {} 149 150 static const string &Type() { // Arc type name 151 static const string type = "reverse_" + Arc::Type(); 152 return type; 153 } 154 155 Label ilabel; // Transition input label 156 Label olabel; // Transition output label 157 Weight weight; // Transition weight 158 StateId nextstate; // Transition destination state 159}; 160 161 162// Arc with integer labels and state Ids and lexicographic weights. 163template<class W1, class W2> 164struct LexicographicArc { 165 typedef int Label; 166 typedef LexicographicWeight<W1, W2> Weight; 167 typedef int StateId; 168 169 LexicographicArc(Label i, Label o, Weight w, StateId s) 170 : ilabel(i), olabel(o), weight(w), nextstate(s) {} 171 172 LexicographicArc() {} 173 174 static const string &Type() { // Arc type name 175 static const string type = Weight::Type(); 176 return type; 177 } 178 179 Label ilabel; // Transition input label 180 Label olabel; // Transition output label 181 Weight weight; // Transition weight 182 StateId nextstate; // Transition destination state 183}; 184 185 186// Arc with integer labels and state Ids and product weights. 187template<class W1, class W2> 188struct ProductArc { 189 typedef int Label; 190 typedef ProductWeight<W1, W2> Weight; 191 typedef int StateId; 192 193 ProductArc(Label i, Label o, Weight w, StateId s) 194 : ilabel(i), olabel(o), weight(w), nextstate(s) {} 195 196 ProductArc() {} 197 198 static const string &Type() { // Arc type name 199 static const string type = Weight::Type(); 200 return type; 201 } 202 203 Label ilabel; // Transition input label 204 Label olabel; // Transition output label 205 Weight weight; // Transition weight 206 StateId nextstate; // Transition destination state 207}; 208 209 210// Arc with label and state Id type the same as first template arg and with 211// weights over the n-th cartesian power of the weight type of the 212// template arg. 213template <class A, unsigned int n> 214struct PowerArc { 215 typedef A Arc; 216 typedef typename A::Label Label; 217 typedef typename A::StateId StateId; 218 typedef PowerWeight<typename A::Weight, n> Weight; 219 220 PowerArc() {} 221 222 PowerArc(Label i, Label o, Weight w, StateId s) 223 : ilabel(i), olabel(o), weight(w), nextstate(s) {} 224 225 static const string &Type() { // Arc type name 226 static string type; 227 if (type.empty()) { 228 string power; 229 Int64ToStr(n, &power); 230 type = A::Type() + "_^" + power; 231 } 232 return type; 233 } 234 235 Label ilabel; // Transition input label 236 Label olabel; // Transition output label 237 Weight weight; // Transition weight 238 StateId nextstate; // Transition destination state 239}; 240 241 242// Arc with label and state Id type the same as first template arg and with 243// weights over the arbitrary cartesian power of the weight type. 244template <class A, class K = int> 245struct SparsePowerArc { 246 typedef A Arc; 247 typedef typename A::Label Label; 248 typedef typename A::StateId StateId; 249 typedef SparsePowerWeight<typename A::Weight, K> Weight; 250 251 SparsePowerArc() {} 252 253 SparsePowerArc(Label i, Label o, Weight w, StateId s) 254 : ilabel(i), olabel(o), weight(w), nextstate(s) {} 255 256 static const string &Type() { // Arc type name 257 static string type; 258 if (type.empty()) { type = A::Type() + "_^n"; } 259 if(sizeof(K) != sizeof(uint32)) { 260 string size; 261 Int64ToStr(8 * sizeof(K), &size); 262 type += "_" + size; 263 } 264 return type; 265 } 266 267 Label ilabel; // Transition input label 268 Label olabel; // Transition output label 269 Weight weight; // Transition weight 270 StateId nextstate; // Transition destination state 271}; 272 273 274// Arc with label and state Id type the same as first template arg and with 275// expectation weight over the first template arg weight type and the 276// second template arg. 277template <class A, class X2> 278struct ExpectationArc { 279 typedef A Arc; 280 typedef typename A::Label Label; 281 typedef typename A::StateId StateId; 282 typedef typename A::Weight X1; 283 typedef ExpectationWeight<X1, X2> Weight; 284 285 ExpectationArc() {} 286 287 ExpectationArc(Label i, Label o, Weight w, StateId s) 288 : ilabel(i), olabel(o), weight(w), nextstate(s) {} 289 290 static const string &Type() { // Arc type name 291 static string type; 292 if (type.empty()) { 293 type = "expectation_" + A::Type() + "_" + X2::Type(); 294 } 295 return type; 296 } 297 298 Label ilabel; // Transition input label 299 Label olabel; // Transition output label 300 Weight weight; // Transition weight 301 StateId nextstate; // Transition destination state 302}; 303 304} // namespace fst 305 306#endif // FST_LIB_ARC_H__ 307