From 96a32415ab43377cf1575bd3f4f2980f58028209 Mon Sep 17 00:00:00 2001 From: Determinant Date: Fri, 14 Aug 2015 11:51:42 +0800 Subject: add implementation for kaldi io (by ymz) --- .../src/tools/openfst/include/fst/accumulator.h | 745 ++++++++++ kaldi_io/src/tools/openfst/include/fst/add-on.h | 306 +++++ kaldi_io/src/tools/openfst/include/fst/arc-map.h | 1146 +++++++++++++++ kaldi_io/src/tools/openfst/include/fst/arc.h | 307 +++++ kaldi_io/src/tools/openfst/include/fst/arcfilter.h | 99 ++ kaldi_io/src/tools/openfst/include/fst/arcsort.h | 217 +++ kaldi_io/src/tools/openfst/include/fst/bi-table.h | 532 +++++++ kaldi_io/src/tools/openfst/include/fst/cache.h | 861 ++++++++++++ kaldi_io/src/tools/openfst/include/fst/closure.h | 155 +++ .../src/tools/openfst/include/fst/compact-fst.h | 1438 +++++++++++++++++++ kaldi_io/src/tools/openfst/include/fst/compat.h | 131 ++ .../src/tools/openfst/include/fst/complement.h | 338 +++++ .../src/tools/openfst/include/fst/compose-filter.h | 542 ++++++++ kaldi_io/src/tools/openfst/include/fst/compose.h | 728 ++++++++++ kaldi_io/src/tools/openfst/include/fst/concat.h | 246 ++++ kaldi_io/src/tools/openfst/include/fst/config.h | 12 + kaldi_io/src/tools/openfst/include/fst/connect.h | 319 +++++ kaldi_io/src/tools/openfst/include/fst/const-fst.h | 497 +++++++ .../src/tools/openfst/include/fst/determinize.h | 1015 ++++++++++++++ kaldi_io/src/tools/openfst/include/fst/dfs-visit.h | 205 +++ .../src/tools/openfst/include/fst/difference.h | 189 +++ kaldi_io/src/tools/openfst/include/fst/edit-fst.h | 779 +++++++++++ kaldi_io/src/tools/openfst/include/fst/encode.h | 599 ++++++++ .../src/tools/openfst/include/fst/epsnormalize.h | 73 + kaldi_io/src/tools/openfst/include/fst/equal.h | 124 ++ .../src/tools/openfst/include/fst/equivalent.h | 275 ++++ .../src/tools/openfst/include/fst/expanded-fst.h | 189 +++ .../tools/openfst/include/fst/expectation-weight.h | 142 ++ .../include/fst/extensions/far/compile-strings.h | 304 ++++ .../openfst/include/fst/extensions/far/create.h | 87 ++ .../openfst/include/fst/extensions/far/equal.h | 99 ++ .../openfst/include/fst/extensions/far/extract.h | 140 ++ .../tools/openfst/include/fst/extensions/far/far.h | 532 +++++++ .../openfst/include/fst/extensions/far/farlib.h | 31 + .../openfst/include/fst/extensions/far/farscript.h | 273 ++++ .../openfst/include/fst/extensions/far/info.h | 128 ++ .../openfst/include/fst/extensions/far/main.h | 43 + .../include/fst/extensions/far/print-strings.h | 138 ++ .../openfst/include/fst/extensions/far/stlist.h | 305 ++++ .../openfst/include/fst/extensions/far/sttable.h | 371 +++++ .../include/fst/extensions/ngram/bitmap-index.h | 183 +++ .../include/fst/extensions/ngram/ngram-fst.h | 934 +++++++++++++ .../openfst/include/fst/extensions/ngram/nthbit.h | 46 + .../src/tools/openfst/include/fst/factor-weight.h | 475 +++++++ kaldi_io/src/tools/openfst/include/fst/flags.h | 242 ++++ .../src/tools/openfst/include/fst/float-weight.h | 601 ++++++++ kaldi_io/src/tools/openfst/include/fst/fst-decl.h | 124 ++ kaldi_io/src/tools/openfst/include/fst/fst.h | 949 +++++++++++++ kaldi_io/src/tools/openfst/include/fst/fstlib.h | 153 +++ .../tools/openfst/include/fst/generic-register.h | 159 +++ kaldi_io/src/tools/openfst/include/fst/heap.h | 206 +++ kaldi_io/src/tools/openfst/include/fst/icu.h | 116 ++ kaldi_io/src/tools/openfst/include/fst/intersect.h | 172 +++ .../src/tools/openfst/include/fst/interval-set.h | 381 +++++ kaldi_io/src/tools/openfst/include/fst/invert.h | 125 ++ .../tools/openfst/include/fst/label-reachable.h | 565 ++++++++ .../openfst/include/fst/lexicographic-weight.h | 151 ++ kaldi_io/src/tools/openfst/include/fst/lock.h | 100 ++ kaldi_io/src/tools/openfst/include/fst/log.h | 66 + .../tools/openfst/include/fst/lookahead-filter.h | 698 ++++++++++ .../tools/openfst/include/fst/lookahead-matcher.h | 812 +++++++++++ kaldi_io/src/tools/openfst/include/fst/map.h | 121 ++ .../src/tools/openfst/include/fst/mapped-file.h | 83 ++ .../src/tools/openfst/include/fst/matcher-fst.h | 359 +++++ kaldi_io/src/tools/openfst/include/fst/matcher.h | 1205 ++++++++++++++++ kaldi_io/src/tools/openfst/include/fst/minimize.h | 591 ++++++++ .../src/tools/openfst/include/fst/mutable-fst.h | 378 +++++ .../src/tools/openfst/include/fst/pair-weight.h | 280 ++++ kaldi_io/src/tools/openfst/include/fst/partition.h | 305 ++++ .../src/tools/openfst/include/fst/power-weight.h | 159 +++ .../src/tools/openfst/include/fst/product-weight.h | 115 ++ kaldi_io/src/tools/openfst/include/fst/project.h | 148 ++ .../src/tools/openfst/include/fst/properties.h | 460 +++++++ kaldi_io/src/tools/openfst/include/fst/prune.h | 339 +++++ kaldi_io/src/tools/openfst/include/fst/push.h | 175 +++ kaldi_io/src/tools/openfst/include/fst/queue.h | 938 +++++++++++++ .../src/tools/openfst/include/fst/randequivalent.h | 135 ++ kaldi_io/src/tools/openfst/include/fst/randgen.h | 712 ++++++++++ .../src/tools/openfst/include/fst/random-weight.h | 348 +++++ kaldi_io/src/tools/openfst/include/fst/rational.h | 330 +++++ kaldi_io/src/tools/openfst/include/fst/register.h | 133 ++ kaldi_io/src/tools/openfst/include/fst/relabel.h | 528 +++++++ .../src/tools/openfst/include/fst/replace-util.h | 550 ++++++++ kaldi_io/src/tools/openfst/include/fst/replace.h | 1453 ++++++++++++++++++++ kaldi_io/src/tools/openfst/include/fst/reverse.h | 91 ++ kaldi_io/src/tools/openfst/include/fst/reweight.h | 146 ++ kaldi_io/src/tools/openfst/include/fst/rmepsilon.h | 600 ++++++++ .../src/tools/openfst/include/fst/rmfinalepsilon.h | 107 ++ .../src/tools/openfst/include/fst/script/arcsort.h | 49 + .../tools/openfst/include/fst/script/arg-packs.h | 240 ++++ .../src/tools/openfst/include/fst/script/closure.h | 41 + .../openfst/include/fst/script/compile-impl.h | 216 +++ .../src/tools/openfst/include/fst/script/compile.h | 92 ++ .../src/tools/openfst/include/fst/script/compose.h | 63 + .../src/tools/openfst/include/fst/script/concat.h | 54 + .../src/tools/openfst/include/fst/script/connect.h | 45 + .../src/tools/openfst/include/fst/script/convert.h | 49 + .../src/tools/openfst/include/fst/script/decode.h | 46 + .../tools/openfst/include/fst/script/determinize.h | 68 + .../tools/openfst/include/fst/script/difference.h | 67 + .../openfst/include/fst/script/disambiguate.h | 68 + .../tools/openfst/include/fst/script/draw-impl.h | 234 ++++ .../src/tools/openfst/include/fst/script/draw.h | 114 ++ .../src/tools/openfst/include/fst/script/encode.h | 58 + .../openfst/include/fst/script/epsnormalize.h | 44 + .../src/tools/openfst/include/fst/script/equal.h | 45 + .../tools/openfst/include/fst/script/equivalent.h | 47 + .../tools/openfst/include/fst/script/fst-class.h | 382 +++++ .../openfst/include/fst/script/fstscript-decl.h | 35 + .../tools/openfst/include/fst/script/fstscript.h | 154 +++ .../tools/openfst/include/fst/script/info-impl.h | 325 +++++ .../src/tools/openfst/include/fst/script/info.h | 48 + .../tools/openfst/include/fst/script/intersect.h | 65 + .../src/tools/openfst/include/fst/script/invert.h | 43 + .../src/tools/openfst/include/fst/script/map.h | 123 ++ .../tools/openfst/include/fst/script/minimize.h | 45 + .../tools/openfst/include/fst/script/print-impl.h | 149 ++ .../src/tools/openfst/include/fst/script/print.h | 86 ++ .../src/tools/openfst/include/fst/script/project.h | 43 + .../src/tools/openfst/include/fst/script/prune.h | 153 +++ .../src/tools/openfst/include/fst/script/push.h | 70 + .../openfst/include/fst/script/randequivalent.h | 105 ++ .../src/tools/openfst/include/fst/script/randgen.h | 76 + .../tools/openfst/include/fst/script/register.h | 120 ++ .../src/tools/openfst/include/fst/script/relabel.h | 102 ++ .../src/tools/openfst/include/fst/script/replace.h | 62 + .../src/tools/openfst/include/fst/script/reverse.h | 42 + .../tools/openfst/include/fst/script/reweight.h | 53 + .../tools/openfst/include/fst/script/rmepsilon.h | 211 +++ .../tools/openfst/include/fst/script/script-impl.h | 206 +++ .../openfst/include/fst/script/shortest-distance.h | 250 ++++ .../openfst/include/fst/script/shortest-path.h | 190 +++ .../src/tools/openfst/include/fst/script/symbols.h | 20 + .../tools/openfst/include/fst/script/synchronize.h | 42 + .../src/tools/openfst/include/fst/script/text-io.h | 51 + .../src/tools/openfst/include/fst/script/topsort.h | 40 + .../src/tools/openfst/include/fst/script/union.h | 42 + .../src/tools/openfst/include/fst/script/verify.h | 40 + .../openfst/include/fst/script/weight-class.h | 223 +++ .../tools/openfst/include/fst/shortest-distance.h | 348 +++++ .../src/tools/openfst/include/fst/shortest-path.h | 501 +++++++ .../tools/openfst/include/fst/signed-log-weight.h | 367 +++++ kaldi_io/src/tools/openfst/include/fst/slist.h | 61 + .../openfst/include/fst/sparse-power-weight.h | 225 +++ .../openfst/include/fst/sparse-tuple-weight.h | 640 +++++++++ kaldi_io/src/tools/openfst/include/fst/state-map.h | 605 ++++++++ .../tools/openfst/include/fst/state-reachable.h | 198 +++ .../src/tools/openfst/include/fst/state-table.h | 481 +++++++ kaldi_io/src/tools/openfst/include/fst/statesort.h | 97 ++ .../src/tools/openfst/include/fst/string-weight.h | 560 ++++++++ kaldi_io/src/tools/openfst/include/fst/string.h | 271 ++++ .../tools/openfst/include/fst/symbol-table-ops.h | 91 ++ .../src/tools/openfst/include/fst/symbol-table.h | 537 ++++++++ .../src/tools/openfst/include/fst/synchronize.h | 457 ++++++ .../tools/openfst/include/fst/test-properties.h | 250 ++++ kaldi_io/src/tools/openfst/include/fst/topsort.h | 112 ++ .../src/tools/openfst/include/fst/tuple-weight.h | 332 +++++ kaldi_io/src/tools/openfst/include/fst/types.h | 38 + .../src/tools/openfst/include/fst/union-find.h | 110 ++ kaldi_io/src/tools/openfst/include/fst/union.h | 185 +++ kaldi_io/src/tools/openfst/include/fst/util.h | 437 ++++++ .../src/tools/openfst/include/fst/vector-fst.h | 731 ++++++++++ kaldi_io/src/tools/openfst/include/fst/verify.h | 126 ++ kaldi_io/src/tools/openfst/include/fst/visit.h | 284 ++++ kaldi_io/src/tools/openfst/include/fst/weight.h | 179 +++ 165 files changed, 46166 insertions(+) create mode 100644 kaldi_io/src/tools/openfst/include/fst/accumulator.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/add-on.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/arc-map.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/arc.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/arcfilter.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/arcsort.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/bi-table.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/cache.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/closure.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/compact-fst.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/compat.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/complement.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/compose-filter.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/compose.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/concat.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/config.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/connect.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/const-fst.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/determinize.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/dfs-visit.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/difference.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/edit-fst.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/encode.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/epsnormalize.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/equal.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/equivalent.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/expanded-fst.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/expectation-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/compile-strings.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/create.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/equal.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/extract.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/far.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/farlib.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/farscript.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/info.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/main.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/print-strings.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/stlist.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/far/sttable.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/ngram/bitmap-index.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/ngram/ngram-fst.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/extensions/ngram/nthbit.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/factor-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/flags.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/float-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/fst-decl.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/fst.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/fstlib.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/generic-register.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/heap.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/icu.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/intersect.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/interval-set.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/invert.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/label-reachable.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/lexicographic-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/lock.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/log.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/lookahead-filter.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/lookahead-matcher.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/map.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/mapped-file.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/matcher-fst.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/matcher.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/minimize.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/mutable-fst.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/pair-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/partition.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/power-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/product-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/project.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/properties.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/prune.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/push.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/queue.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/randequivalent.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/randgen.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/random-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/rational.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/register.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/relabel.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/replace-util.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/replace.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/reverse.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/reweight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/rmepsilon.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/rmfinalepsilon.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/arcsort.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/arg-packs.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/closure.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/compile-impl.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/compile.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/compose.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/concat.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/connect.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/convert.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/decode.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/determinize.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/difference.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/disambiguate.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/draw-impl.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/draw.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/encode.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/epsnormalize.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/equal.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/equivalent.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/fst-class.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/fstscript-decl.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/fstscript.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/info-impl.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/info.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/intersect.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/invert.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/map.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/minimize.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/print-impl.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/print.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/project.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/prune.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/push.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/randequivalent.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/randgen.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/register.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/relabel.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/replace.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/reverse.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/reweight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/rmepsilon.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/script-impl.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/shortest-distance.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/shortest-path.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/symbols.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/synchronize.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/text-io.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/topsort.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/union.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/verify.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/script/weight-class.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/shortest-distance.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/shortest-path.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/signed-log-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/slist.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/sparse-power-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/sparse-tuple-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/state-map.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/state-reachable.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/state-table.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/statesort.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/string-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/string.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/symbol-table-ops.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/symbol-table.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/synchronize.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/test-properties.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/topsort.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/tuple-weight.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/types.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/union-find.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/union.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/util.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/vector-fst.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/verify.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/visit.h create mode 100644 kaldi_io/src/tools/openfst/include/fst/weight.h (limited to 'kaldi_io/src/tools/openfst/include') diff --git a/kaldi_io/src/tools/openfst/include/fst/accumulator.h b/kaldi_io/src/tools/openfst/include/fst/accumulator.h new file mode 100644 index 0000000..81d1847 --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/accumulator.h @@ -0,0 +1,745 @@ +// accumulator.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. +// +// Copyright 2005-2010 Google, Inc. +// Author: riley@google.com (Michael Riley) +// +// \file +// Classes to accumulate arc weights. Useful for weight lookahead. + +#ifndef FST_LIB_ACCUMULATOR_H__ +#define FST_LIB_ACCUMULATOR_H__ + +#include +#include +#include +using std::tr1::unordered_map; +using std::tr1::unordered_multimap; +#include +using std::vector; + +#include +#include +#include +#include +#include + +namespace fst { + +// This class accumulates arc weights using the semiring Plus(). +template +class DefaultAccumulator { + public: + typedef A Arc; + typedef typename A::StateId StateId; + typedef typename A::Weight Weight; + + DefaultAccumulator() {} + + DefaultAccumulator(const DefaultAccumulator &acc) {} + + void Init(const Fst& fst, bool copy = false) {} + + void SetState(StateId) {} + + Weight Sum(Weight w, Weight v) { + return Plus(w, v); + } + + template + Weight Sum(Weight w, ArcIterator *aiter, ssize_t begin, + ssize_t end) { + Weight sum = w; + aiter->Seek(begin); + for (ssize_t pos = begin; pos < end; aiter->Next(), ++pos) + sum = Plus(sum, aiter->Value().weight); + return sum; + } + + bool Error() const { return false; } + + private: + void operator=(const DefaultAccumulator &); // Disallow +}; + + +// This class accumulates arc weights using the log semiring Plus() +// assuming an arc weight has a WeightConvert specialization to +// and from log64 weights. +template +class LogAccumulator { + public: + typedef A Arc; + typedef typename A::StateId StateId; + typedef typename A::Weight Weight; + + LogAccumulator() {} + + LogAccumulator(const LogAccumulator &acc) {} + + void Init(const Fst& fst, bool copy = false) {} + + void SetState(StateId) {} + + Weight Sum(Weight w, Weight v) { + return LogPlus(w, v); + } + + template + Weight Sum(Weight w, ArcIterator *aiter, ssize_t begin, + ssize_t end) { + Weight sum = w; + aiter->Seek(begin); + for (ssize_t pos = begin; pos < end; aiter->Next(), ++pos) + sum = LogPlus(sum, aiter->Value().weight); + return sum; + } + + bool Error() const { return false; } + + private: + double LogPosExp(double x) { return log(1.0F + exp(-x)); } + + Weight LogPlus(Weight w, Weight v) { + double f1 = to_log_weight_(w).Value(); + double f2 = to_log_weight_(v).Value(); + if (f1 > f2) + return to_weight_(f2 - LogPosExp(f1 - f2)); + else + return to_weight_(f1 - LogPosExp(f2 - f1)); + } + + WeightConvert to_log_weight_; + WeightConvert to_weight_; + + void operator=(const LogAccumulator &); // Disallow +}; + + +// Stores shareable data for fast log accumulator copies. +class FastLogAccumulatorData { + public: + FastLogAccumulatorData() {} + + vector *Weights() { return &weights_; } + vector *WeightPositions() { return &weight_positions_; } + double *WeightEnd() { return &(weights_[weights_.size() - 1]); }; + int RefCount() const { return ref_count_.count(); } + int IncrRefCount() { return ref_count_.Incr(); } + int DecrRefCount() { return ref_count_.Decr(); } + + private: + // Cummulative weight per state for all states s.t. # of arcs > + // arc_limit_ with arcs in order. Special first element per state + // being Log64Weight::Zero(); + vector weights_; + // Maps from state to corresponding beginning weight position in + // weights_. Position -1 means no pre-computed weights for that + // state. + vector weight_positions_; + RefCounter ref_count_; // Reference count. + + DISALLOW_COPY_AND_ASSIGN(FastLogAccumulatorData); +}; + + +// This class accumulates arc weights using the log semiring Plus() +// assuming an arc weight has a WeightConvert specialization to and +// from log64 weights. The member function Init(fst) has to be called +// to setup pre-computed weight information. +template +class FastLogAccumulator { + public: + typedef A Arc; + typedef typename A::StateId StateId; + typedef typename A::Weight Weight; + + explicit FastLogAccumulator(ssize_t arc_limit = 20, ssize_t arc_period = 10) + : arc_limit_(arc_limit), + arc_period_(arc_period), + data_(new FastLogAccumulatorData()), + error_(false) {} + + FastLogAccumulator(const FastLogAccumulator &acc) + : arc_limit_(acc.arc_limit_), + arc_period_(acc.arc_period_), + data_(acc.data_), + error_(acc.error_) { + data_->IncrRefCount(); + } + + ~FastLogAccumulator() { + if (!data_->DecrRefCount()) + delete data_; + } + + void SetState(StateId s) { + vector &weights = *data_->Weights(); + vector &weight_positions = *data_->WeightPositions(); + + if (weight_positions.size() <= s) { + FSTERROR() << "FastLogAccumulator::SetState: invalid state id."; + error_ = true; + return; + } + + ssize_t pos = weight_positions[s]; + if (pos >= 0) + state_weights_ = &(weights[pos]); + else + state_weights_ = 0; + } + + Weight Sum(Weight w, Weight v) { + return LogPlus(w, v); + } + + template + Weight Sum(Weight w, ArcIterator *aiter, ssize_t begin, + ssize_t end) { + if (error_) return Weight::NoWeight(); + Weight sum = w; + // Finds begin and end of pre-stored weights + ssize_t index_begin = -1, index_end = -1; + ssize_t stored_begin = end, stored_end = end; + if (state_weights_ != 0) { + index_begin = begin > 0 ? (begin - 1)/ arc_period_ + 1 : 0; + index_end = end / arc_period_; + stored_begin = index_begin * arc_period_; + stored_end = index_end * arc_period_; + } + // Computes sum before pre-stored weights + if (begin < stored_begin) { + ssize_t pos_end = min(stored_begin, end); + aiter->Seek(begin); + for (ssize_t pos = begin; pos < pos_end; aiter->Next(), ++pos) + sum = LogPlus(sum, aiter->Value().weight); + } + // Computes sum between pre-stored weights + if (stored_begin < stored_end) { + sum = LogPlus(sum, LogMinus(state_weights_[index_end], + state_weights_[index_begin])); + } + // Computes sum after pre-stored weights + if (stored_end < end) { + ssize_t pos_start = max(stored_begin, stored_end); + aiter->Seek(pos_start); + for (ssize_t pos = pos_start; pos < end; aiter->Next(), ++pos) + sum = LogPlus(sum, aiter->Value().weight); + } + return sum; + } + + template + void Init(const F &fst, bool copy = false) { + if (copy) + return; + vector &weights = *data_->Weights(); + vector &weight_positions = *data_->WeightPositions(); + if (!weights.empty() || arc_limit_ < arc_period_) { + FSTERROR() << "FastLogAccumulator: initialization error."; + error_ = true; + return; + } + weight_positions.reserve(CountStates(fst)); + + ssize_t weight_position = 0; + for(StateIterator siter(fst); !siter.Done(); siter.Next()) { + StateId s = siter.Value(); + if (fst.NumArcs(s) >= arc_limit_) { + double sum = FloatLimits::PosInfinity(); + weight_positions.push_back(weight_position); + weights.push_back(sum); + ++weight_position; + ssize_t narcs = 0; + for(ArcIterator aiter(fst, s); !aiter.Done(); aiter.Next()) { + const A &arc = aiter.Value(); + sum = LogPlus(sum, arc.weight); + // Stores cumulative weight distribution per arc_period_. + if (++narcs % arc_period_ == 0) { + weights.push_back(sum); + ++weight_position; + } + } + } else { + weight_positions.push_back(-1); + } + } + } + + bool Error() const { return error_; } + + private: + double LogPosExp(double x) { + return x == FloatLimits::PosInfinity() ? + 0.0 : log(1.0F + exp(-x)); + } + + double LogMinusExp(double x) { + return x == FloatLimits::PosInfinity() ? + 0.0 : log(1.0F - exp(-x)); + } + + Weight LogPlus(Weight w, Weight v) { + double f1 = to_log_weight_(w).Value(); + double f2 = to_log_weight_(v).Value(); + if (f1 > f2) + return to_weight_(f2 - LogPosExp(f1 - f2)); + else + return to_weight_(f1 - LogPosExp(f2 - f1)); + } + + double LogPlus(double f1, Weight v) { + double f2 = to_log_weight_(v).Value(); + if (f1 == FloatLimits::PosInfinity()) + return f2; + else if (f1 > f2) + return f2 - LogPosExp(f1 - f2); + else + return f1 - LogPosExp(f2 - f1); + } + + Weight LogMinus(double f1, double f2) { + if (f1 >= f2) { + FSTERROR() << "FastLogAcumulator::LogMinus: f1 >= f2 with f1 = " << f1 + << " and f2 = " << f2; + error_ = true; + return Weight::NoWeight(); + } + if (f2 == FloatLimits::PosInfinity()) + return to_weight_(f1); + else + return to_weight_(f1 - LogMinusExp(f2 - f1)); + } + + WeightConvert to_log_weight_; + WeightConvert to_weight_; + + ssize_t arc_limit_; // Minimum # of arcs to pre-compute state + ssize_t arc_period_; // Save cumulative weights per 'arc_period_'. + bool init_; // Cumulative weights initialized? + FastLogAccumulatorData *data_; + double *state_weights_; + bool error_; + + void operator=(const FastLogAccumulator &); // Disallow +}; + + +// Stores shareable data for cache log accumulator copies. +// All copies share the same cache. +template +class CacheLogAccumulatorData { + public: + typedef A Arc; + typedef typename A::StateId StateId; + typedef typename A::Weight Weight; + + CacheLogAccumulatorData(bool gc, size_t gc_limit) + : cache_gc_(gc), cache_limit_(gc_limit), cache_size_(0) {} + + ~CacheLogAccumulatorData() { + for(typename unordered_map::iterator it = cache_.begin(); + it != cache_.end(); + ++it) + delete it->second.weights; + } + + bool CacheDisabled() const { return cache_gc_ && cache_limit_ == 0; } + + vector *GetWeights(StateId s) { + typename unordered_map::iterator it = cache_.find(s); + if (it != cache_.end()) { + it->second.recent = true; + return it->second.weights; + } else { + return 0; + } + } + + void AddWeights(StateId s, vector *weights) { + if (cache_gc_ && cache_size_ >= cache_limit_) + GC(false); + cache_.insert(make_pair(s, CacheState(weights, true))); + if (cache_gc_) + cache_size_ += weights->capacity() * sizeof(double); + } + + int RefCount() const { return ref_count_.count(); } + int IncrRefCount() { return ref_count_.Incr(); } + int DecrRefCount() { return ref_count_.Decr(); } + + private: + // Cached information for a given state. + struct CacheState { + vector* weights; // Accumulated weights for this state. + bool recent; // Has this state been accessed since last GC? + + CacheState(vector *w, bool r) : weights(w), recent(r) {} + }; + + // Garbage collect: Delete from cache states that have not been + // accessed since the last GC ('free_recent = false') until + // 'cache_size_' is 2/3 of 'cache_limit_'. If it does not free enough + // memory, start deleting recently accessed states. + void GC(bool free_recent) { + size_t cache_target = (2 * cache_limit_)/3 + 1; + typename unordered_map::iterator it = cache_.begin(); + while (it != cache_.end() && cache_size_ > cache_target) { + CacheState &cs = it->second; + if (free_recent || !cs.recent) { + cache_size_ -= cs.weights->capacity() * sizeof(double); + delete cs.weights; + cache_.erase(it++); + } else { + cs.recent = false; + ++it; + } + } + if (!free_recent && cache_size_ > cache_target) + GC(true); + } + + unordered_map cache_; // Cache + bool cache_gc_; // Enable garbage collection + size_t cache_limit_; // # of bytes cached + size_t cache_size_; // # of bytes allowed before GC + RefCounter ref_count_; + + DISALLOW_COPY_AND_ASSIGN(CacheLogAccumulatorData); +}; + +// This class accumulates arc weights using the log semiring Plus() +// has a WeightConvert specialization to and from log64 weights. It +// is similar to the FastLogAccumator. However here, the accumulated +// weights are pre-computed and stored only for the states that are +// visited. The member function Init(fst) has to be called to setup +// this accumulator. +template +class CacheLogAccumulator { + public: + typedef A Arc; + typedef typename A::StateId StateId; + typedef typename A::Weight Weight; + + explicit CacheLogAccumulator(ssize_t arc_limit = 10, bool gc = false, + size_t gc_limit = 10 * 1024 * 1024) + : arc_limit_(arc_limit), fst_(0), data_( + new CacheLogAccumulatorData(gc, gc_limit)), s_(kNoStateId), + error_(false) {} + + CacheLogAccumulator(const CacheLogAccumulator &acc) + : arc_limit_(acc.arc_limit_), fst_(acc.fst_ ? acc.fst_->Copy() : 0), + data_(acc.data_), s_(kNoStateId), error_(acc.error_) { + data_->IncrRefCount(); + } + + ~CacheLogAccumulator() { + if (fst_) + delete fst_; + if (!data_->DecrRefCount()) + delete data_; + } + + // Arg 'arc_limit' specifies minimum # of arcs to pre-compute state. + void Init(const Fst &fst, bool copy = false) { + if (copy) { + delete fst_; + } else if (fst_) { + FSTERROR() << "CacheLogAccumulator: initialization error."; + error_ = true; + return; + } + fst_ = fst.Copy(); + } + + void SetState(StateId s, int depth = 0) { + if (s == s_) + return; + s_ = s; + + if (data_->CacheDisabled() || error_) { + weights_ = 0; + return; + } + + if (!fst_) { + FSTERROR() << "CacheLogAccumulator::SetState: incorrectly initialized."; + error_ = true; + weights_ = 0; + return; + } + + weights_ = data_->GetWeights(s); + if ((weights_ == 0) && (fst_->NumArcs(s) >= arc_limit_)) { + weights_ = new vector; + weights_->reserve(fst_->NumArcs(s) + 1); + weights_->push_back(FloatLimits::PosInfinity()); + data_->AddWeights(s, weights_); + } + } + + Weight Sum(Weight w, Weight v) { + return LogPlus(w, v); + } + + template + Weight Sum(Weight w, Iterator *aiter, ssize_t begin, + ssize_t end) { + if (weights_ == 0) { + Weight sum = w; + aiter->Seek(begin); + for (ssize_t pos = begin; pos < end; aiter->Next(), ++pos) + sum = LogPlus(sum, aiter->Value().weight); + return sum; + } else { + if (weights_->size() <= end) + for (aiter->Seek(weights_->size() - 1); + weights_->size() <= end; + aiter->Next()) + weights_->push_back(LogPlus(weights_->back(), + aiter->Value().weight)); + return LogPlus(w, LogMinus((*weights_)[end], (*weights_)[begin])); + } + } + + template + size_t LowerBound(double w, Iterator *aiter) { + if (weights_ != 0) { + return lower_bound(weights_->begin() + 1, + weights_->end(), + w, + std::greater()) + - weights_->begin() - 1; + } else { + size_t n = 0; + double x = FloatLimits::PosInfinity(); + for(aiter->Reset(); !aiter->Done(); aiter->Next(), ++n) { + x = LogPlus(x, aiter->Value().weight); + if (x < w) break; + } + return n; + } + } + + bool Error() const { return error_; } + + private: + double LogPosExp(double x) { + return x == FloatLimits::PosInfinity() ? + 0.0 : log(1.0F + exp(-x)); + } + + double LogMinusExp(double x) { + return x == FloatLimits::PosInfinity() ? + 0.0 : log(1.0F - exp(-x)); + } + + Weight LogPlus(Weight w, Weight v) { + double f1 = to_log_weight_(w).Value(); + double f2 = to_log_weight_(v).Value(); + if (f1 > f2) + return to_weight_(f2 - LogPosExp(f1 - f2)); + else + return to_weight_(f1 - LogPosExp(f2 - f1)); + } + + double LogPlus(double f1, Weight v) { + double f2 = to_log_weight_(v).Value(); + if (f1 == FloatLimits::PosInfinity()) + return f2; + else if (f1 > f2) + return f2 - LogPosExp(f1 - f2); + else + return f1 - LogPosExp(f2 - f1); + } + + Weight LogMinus(double f1, double f2) { + if (f1 >= f2) { + FSTERROR() << "CacheLogAcumulator::LogMinus: f1 >= f2 with f1 = " << f1 + << " and f2 = " << f2; + error_ = true; + return Weight::NoWeight(); + } + if (f2 == FloatLimits::PosInfinity()) + return to_weight_(f1); + else + return to_weight_(f1 - LogMinusExp(f2 - f1)); + } + + WeightConvert to_log_weight_; + WeightConvert to_weight_; + + ssize_t arc_limit_; // Minimum # of arcs to cache a state + vector *weights_; // Accumulated weights for cur. state + const Fst* fst_; // Input fst + CacheLogAccumulatorData *data_; // Cache data + StateId s_; // Current state + bool error_; + + void operator=(const CacheLogAccumulator &); // Disallow +}; + + +// Stores shareable data for replace accumulator copies. +template +class ReplaceAccumulatorData { + public: + typedef typename Accumulator::Arc Arc; + typedef typename Arc::StateId StateId; + typedef typename Arc::Label Label; + typedef T StateTable; + typedef typename T::StateTuple StateTuple; + + ReplaceAccumulatorData() : state_table_(0) {} + + ReplaceAccumulatorData(const vector &accumulators) + : state_table_(0), accumulators_(accumulators) {} + + ~ReplaceAccumulatorData() { + for (size_t i = 0; i < fst_array_.size(); ++i) + delete fst_array_[i]; + for (size_t i = 0; i < accumulators_.size(); ++i) + delete accumulators_[i]; + } + + void Init(const vector*> > &fst_tuples, + const StateTable *state_table) { + state_table_ = state_table; + accumulators_.resize(fst_tuples.size()); + for (size_t i = 0; i < accumulators_.size(); ++i) { + if (!accumulators_[i]) + accumulators_[i] = new Accumulator; + accumulators_[i]->Init(*(fst_tuples[i].second)); + fst_array_.push_back(fst_tuples[i].second->Copy()); + } + } + + const StateTuple &GetTuple(StateId s) const { + return state_table_->Tuple(s); + } + + Accumulator *GetAccumulator(size_t i) { return accumulators_[i]; } + + const Fst *GetFst(size_t i) const { return fst_array_[i]; } + + int RefCount() const { return ref_count_.count(); } + int IncrRefCount() { return ref_count_.Incr(); } + int DecrRefCount() { return ref_count_.Decr(); } + + private: + const T * state_table_; + vector accumulators_; + vector*> fst_array_; + RefCounter ref_count_; + + DISALLOW_COPY_AND_ASSIGN(ReplaceAccumulatorData); +}; + +// This class accumulates weights in a ReplaceFst. The 'Init' method +// takes as input the argument used to build the ReplaceFst and the +// ReplaceFst state table. It uses accumulators of type 'Accumulator' +// in the underlying FSTs. +template > +class ReplaceAccumulator { + public: + typedef typename Accumulator::Arc Arc; + typedef typename Arc::StateId StateId; + typedef typename Arc::Label Label; + typedef typename Arc::Weight Weight; + typedef T StateTable; + typedef typename T::StateTuple StateTuple; + + ReplaceAccumulator() + : init_(false), data_(new ReplaceAccumulatorData()), + error_(false) {} + + ReplaceAccumulator(const vector &accumulators) + : init_(false), + data_(new ReplaceAccumulatorData(accumulators)), + error_(false) {} + + ReplaceAccumulator(const ReplaceAccumulator &acc) + : init_(acc.init_), data_(acc.data_), error_(acc.error_) { + if (!init_) + FSTERROR() << "ReplaceAccumulator: can't copy unintialized accumulator"; + data_->IncrRefCount(); + } + + ~ReplaceAccumulator() { + if (!data_->DecrRefCount()) + delete data_; + } + + // Does not take ownership of the state table, the state table + // is own by the ReplaceFst + void Init(const vector*> > &fst_tuples, + const StateTable *state_table) { + init_ = true; + data_->Init(fst_tuples, state_table); + } + + void SetState(StateId s) { + if (!init_) { + FSTERROR() << "ReplaceAccumulator::SetState: incorrectly initialized."; + error_ = true; + return; + } + StateTuple tuple = data_->GetTuple(s); + fst_id_ = tuple.fst_id - 1; // Replace FST ID is 1-based + data_->GetAccumulator(fst_id_)->SetState(tuple.fst_state); + if ((tuple.prefix_id != 0) && + (data_->GetFst(fst_id_)->Final(tuple.fst_state) != Weight::Zero())) { + offset_ = 1; + offset_weight_ = data_->GetFst(fst_id_)->Final(tuple.fst_state); + } else { + offset_ = 0; + offset_weight_ = Weight::Zero(); + } + } + + Weight Sum(Weight w, Weight v) { + if (error_) return Weight::NoWeight(); + return data_->GetAccumulator(fst_id_)->Sum(w, v); + } + + template + Weight Sum(Weight w, ArcIterator *aiter, ssize_t begin, + ssize_t end) { + if (error_) return Weight::NoWeight(); + Weight sum = begin == end ? Weight::Zero() + : data_->GetAccumulator(fst_id_)->Sum( + w, aiter, begin ? begin - offset_ : 0, end - offset_); + if (begin == 0 && end != 0 && offset_ > 0) + sum = Sum(offset_weight_, sum); + return sum; + } + + bool Error() const { return error_; } + + private: + bool init_; + ReplaceAccumulatorData *data_; + Label fst_id_; + size_t offset_; + Weight offset_weight_; + bool error_; + + void operator=(const ReplaceAccumulator &); // Disallow +}; + +} // namespace fst + +#endif // FST_LIB_ACCUMULATOR_H__ diff --git a/kaldi_io/src/tools/openfst/include/fst/add-on.h b/kaldi_io/src/tools/openfst/include/fst/add-on.h new file mode 100644 index 0000000..ee21a93 --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/add-on.h @@ -0,0 +1,306 @@ +// add-on.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. +// +// Copyright 2005-2010 Google, Inc. +// Author: riley@google.com (Michael Riley) +// +// \file +// Fst implementation class to attach an arbitrary object with a +// read/write method to an FST and its file rep. The FST is given a +// new type name. + +#ifndef FST_LIB_ADD_ON_FST_H__ +#define FST_LIB_ADD_ON_FST_H__ + +#include +#include + +#include + + +namespace fst { + +// Identifies stream data as an add-on fst. +static const int32 kAddOnMagicNumber = 446681434; + + +// +// Some useful add-on objects. +// + +// Nothing to save. +class NullAddOn { + public: + NullAddOn() {} + + static NullAddOn *Read(istream &istrm) { + return new NullAddOn(); + }; + + bool Write(ostream &ostrm) const { return true; } + + int RefCount() const { return ref_count_.count(); } + int IncrRefCount() { return ref_count_.Incr(); } + int DecrRefCount() { return ref_count_.Decr(); } + + private: + RefCounter ref_count_; + + DISALLOW_COPY_AND_ASSIGN(NullAddOn); +}; + + +// Create a new add-on from a pair of add-ons. +template +class AddOnPair { + public: + // Argument reference count incremented. + AddOnPair(A1 *a1, A2 *a2) + : a1_(a1), a2_(a2) { + if (a1_) + a1_->IncrRefCount(); + if (a2_) + a2_->IncrRefCount(); + } + + ~AddOnPair() { + if (a1_ && !a1_->DecrRefCount()) + delete a1_; + if (a2_ && !a2_->DecrRefCount()) + delete a2_; + } + + A1 *First() const { return a1_; } + A2 *Second() const { return a2_; } + + static AddOnPair *Read(istream &istrm) { + A1 *a1 = 0; + bool have_addon1 = false; + ReadType(istrm, &have_addon1); + if (have_addon1) + a1 = A1::Read(istrm); + + A2 *a2 = 0; + bool have_addon2 = false; + ReadType(istrm, &have_addon2); + if (have_addon2) + a2 = A2::Read(istrm); + + AddOnPair *a = new AddOnPair(a1, a2); + if (a1) + a1->DecrRefCount(); + if (a2) + a2->DecrRefCount(); + return a; + }; + + bool Write(ostream &ostrm) const { + bool have_addon1 = a1_; + WriteType(ostrm, have_addon1); + if (have_addon1) + a1_->Write(ostrm); + bool have_addon2 = a2_; + WriteType(ostrm, have_addon2); + if (have_addon2) + a2_->Write(ostrm); + return true; + } + + int RefCount() const { return ref_count_.count(); } + + int IncrRefCount() { + return ref_count_.Incr(); + } + + int DecrRefCount() { + return ref_count_.Decr(); + } + + private: + A1 *a1_; + A2 *a2_; + RefCounter ref_count_; + + DISALLOW_COPY_AND_ASSIGN(AddOnPair); +}; + + +// Add to an Fst F a type T object. T must have a 'T* Read(istream &)', +// a 'bool Write(ostream &)' method, and 'int RecCount(), 'int IncrRefCount()' +// and 'int DecrRefCount()' methods (e.g. 'MatcherData' in matcher-fst.h). +// The result is a new Fst implemenation with type name 'type'. +template +class AddOnImpl : public FstImpl { + public: + typedef typename F::Arc Arc; + typedef typename Arc::Label Label; + typedef typename Arc::Weight Weight; + typedef typename Arc::StateId StateId; + + using FstImpl::SetType; + using FstImpl::SetProperties; + using FstImpl::WriteHeader; + + // If 't' is non-zero, its reference count is incremented. + AddOnImpl(const F &fst, const string &type, T *t = 0) + : fst_(fst), t_(t) { + SetType(type); + SetProperties(fst_.Properties(kFstProperties, false)); + if (t_) + t_->IncrRefCount(); + } + + // If 't' is non-zero, its reference count is incremented. + AddOnImpl(const Fst &fst, const string &type, T *t = 0) + : fst_(fst), t_(t) { + SetType(type); + SetProperties(fst_.Properties(kFstProperties, false)); + if (t_) + t_->IncrRefCount(); + } + + AddOnImpl(const AddOnImpl &impl) + : fst_(impl.fst_), t_(impl.t_) { + SetType(impl.Type()); + SetProperties(fst_.Properties(kCopyProperties, false)); + if (t_) + t_->IncrRefCount(); + } + + ~AddOnImpl() { + if (t_ && !t_->DecrRefCount()) + delete t_; + } + + StateId Start() const { return fst_.Start(); } + Weight Final(StateId s) const { return fst_.Final(s); } + size_t NumArcs(StateId s) const { return fst_.NumArcs(s); } + + size_t NumInputEpsilons(StateId s) const { + return fst_.NumInputEpsilons(s); + } + + size_t NumOutputEpsilons(StateId s) const { + return fst_.NumOutputEpsilons(s); + } + + size_t NumStates() const { return fst_.NumStates(); } + + static AddOnImpl *Read(istream &strm, const FstReadOptions &opts) { + FstReadOptions nopts(opts); + FstHeader hdr; + if (!nopts.header) { + hdr.Read(strm, nopts.source); + nopts.header = &hdr; + } + AddOnImpl *impl = new AddOnImpl(nopts.header->FstType()); + if (!impl->ReadHeader(strm, nopts, kMinFileVersion, &hdr)) + return 0; + delete impl; // Used here only for checking types. + + int32 magic_number = 0; + ReadType(strm, &magic_number); // Ensures this is an add-on Fst. + if (magic_number != kAddOnMagicNumber) { + LOG(ERROR) << "AddOnImpl::Read: Bad add-on header: " << nopts.source; + return 0; + } + + FstReadOptions fopts(opts); + fopts.header = 0; // Contained header was written out. + F *fst = F::Read(strm, fopts); + if (!fst) + return 0; + + T *t = 0; + bool have_addon = false; + ReadType(strm, &have_addon); + if (have_addon) { // Read add-on object if present. + t = T::Read(strm); + if (!t) + return 0; + } + impl = new AddOnImpl(*fst, nopts.header->FstType(), t); + delete fst; + if (t) + t->DecrRefCount(); + return impl; + } + + bool Write(ostream &strm, const FstWriteOptions &opts) const { + FstHeader hdr; + FstWriteOptions nopts(opts); + nopts.write_isymbols = false; // Let contained FST hold any symbols. + nopts.write_osymbols = false; + WriteHeader(strm, nopts, kFileVersion, &hdr); + WriteType(strm, kAddOnMagicNumber); // Ensures this is an add-on Fst. + FstWriteOptions fopts(opts); + fopts.write_header = true; // Force writing contained header. + if (!fst_.Write(strm, fopts)) + return false; + bool have_addon = t_; + WriteType(strm, have_addon); + if (have_addon) // Write add-on object if present. + t_->Write(strm); + return true; + } + + void InitStateIterator(StateIteratorData *data) const { + fst_.InitStateIterator(data); + } + + void InitArcIterator(StateId s, ArcIteratorData *data) const { + fst_.InitArcIterator(s, data); + } + + F &GetFst() { return fst_; } + + const F &GetFst() const { return fst_; } + + T *GetAddOn() const { return t_; } + + // If 't' is non-zero, its reference count is incremented. + void SetAddOn(T *t) { + if (t == t_) + return; + if (t_ && !t_->DecrRefCount()) + delete t_; + t_ = t; + if (t_) + t_->IncrRefCount(); + } + + private: + explicit AddOnImpl(const string &type) : t_(0) { + SetType(type); + SetProperties(kExpanded); + } + + // Current file format version + static const int kFileVersion = 1; + // Minimum file format version supported + static const int kMinFileVersion = 1; + + F fst_; + T *t_; + + void operator=(const AddOnImpl &fst); // Disallow +}; + +template const int AddOnImpl::kFileVersion; +template const int AddOnImpl::kMinFileVersion; + + +} // namespace fst + +#endif // FST_LIB_ADD_ON_FST_H__ diff --git a/kaldi_io/src/tools/openfst/include/fst/arc-map.h b/kaldi_io/src/tools/openfst/include/fst/arc-map.h new file mode 100644 index 0000000..914f81c --- /dev/null +++ b/kaldi_io/src/tools/openfst/include/fst/arc-map.h @@ -0,0 +1,1146 @@ +// arc-map.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. +// +// Copyright 2005-2010 Google, Inc. +// Author: riley@google.com (Michael Riley) +// +// \file +// Class to map over/transform arcs e.g., change semirings or +// implement project/invert. Consider using when operation does +// not change the number of arcs (except possibly superfinal arcs). + +#ifndef FST_LIB_ARC_MAP_H__ +#define FST_LIB_ARC_MAP_H__ + +#include +using std::tr1::unordered_map; +using std::tr1::unordered_multimap; +#include +#include +using std::pair; using std::make_pair; + +#include +#include + + +namespace fst { + +// This determines how final weights are mapped. +enum MapFinalAction { + // A final weight is mapped into a final weight. An error + // is raised if this is not possible. + MAP_NO_SUPERFINAL, + + // A final weight is mapped to an arc to the superfinal state + // when the result cannot be represented as a final weight. + // The superfinal state will be added only if it is needed. + MAP_ALLOW_SUPERFINAL, + + // A final weight is mapped to an arc to the superfinal state + // unless the result can be represented as a final weight of weight + // Zero(). The superfinal state is always added (if the input is + // not the empty Fst). + MAP_REQUIRE_SUPERFINAL +}; + +// This determines how symbol tables are mapped. +enum MapSymbolsAction { + // Symbols should be cleared in the result by the map. + MAP_CLEAR_SYMBOLS, + + // Symbols should be copied from the input FST by the map. + MAP_COPY_SYMBOLS, + + // Symbols should not be modified in the result by the map itself. + // (They may set by the mapper). + MAP_NOOP_SYMBOLS +}; + +// ArcMapper Interface - class determinies how arcs and final weights +// are mapped. Useful for implementing operations that do not change +// the number of arcs (expect possibly superfinal arcs). +// +// class ArcMapper { +// public: +// typedef A FromArc; +// typedef B ToArc; +// +// // Maps an arc type A to arc type B. +// B operator()(const A &arc); +// // Specifies final action the mapper requires (see above). +// // The mapper will be passed final weights as arcs of the +// // form A(0, 0, weight, kNoStateId). +// MapFinalAction FinalAction() const; +// // Specifies input symbol table action the mapper requires (see above). +// MapSymbolsAction InputSymbolsAction() const; +// // Specifies output symbol table action the mapper requires (see above). +// MapSymbolsAction OutputSymbolsAction() const; +// // This specifies the known properties of an Fst mapped by this +// // mapper. It takes as argument the input Fst's known properties. +// uint64 Properties(uint64 props) const; +// }; +// +// The ArcMap functions and classes below will use the FinalAction() +// method of the mapper to determine how to treat final weights, +// e.g. whether to add a superfinal state. They will use the Properties() +// method to set the result Fst properties. +// +// We include a various map versions below. One dimension of +// variation is whether the mapping mutates its input, writes to a +// new result Fst, or is an on-the-fly Fst. Another dimension is how +// we pass the mapper. We allow passing the mapper by pointer +// for cases that we need to change the state of the user's mapper. +// This is the case with the encode mapper, which is reused during +// decoding. We also include map versions that pass the mapper +// by value or const reference when this suffices. + + +// Maps an arc type A using a mapper function object C, passed +// by pointer. This version modifies its Fst input. +template +void ArcMap(MutableFst *fst, C* mapper) { + typedef typename A::StateId StateId; + typedef typename A::Weight Weight; + + if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS) + fst->SetInputSymbols(0); + + if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS) + fst->SetOutputSymbols(0); + + if (fst->Start() == kNoStateId) + return; + + uint64 props = fst->Properties(kFstProperties, false); + + MapFinalAction final_action = mapper->FinalAction(); + StateId superfinal = kNoStateId; + if (final_action == MAP_REQUIRE_SUPERFINAL) { + superfinal = fst->AddState(); + fst->SetFinal(superfinal, Weight::One()); + } + + for (StateId s = 0; s < fst->NumStates(); ++s) { + for (MutableArcIterator< MutableFst > aiter(fst, s); + !aiter.Done(); aiter.Next()) { + const A &arc = aiter.Value(); + aiter.SetValue((*mapper)(arc)); + } + + switch (final_action) { + case MAP_NO_SUPERFINAL: + default: { + A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + FSTERROR() << "ArcMap: non-zero arc labels for superfinal arc"; + fst->SetProperties(kError, kError); + } + + fst->SetFinal(s, final_arc.weight); + break; + } + case MAP_ALLOW_SUPERFINAL: { + if (s != superfinal) { + A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + // Add a superfinal state if not already done. + if (superfinal == kNoStateId) { + superfinal = fst->AddState(); + fst->SetFinal(superfinal, Weight::One()); + } + final_arc.nextstate = superfinal; + fst->AddArc(s, final_arc); + fst->SetFinal(s, Weight::Zero()); + } else { + fst->SetFinal(s, final_arc.weight); + } + break; + } + } + case MAP_REQUIRE_SUPERFINAL: { + if (s != superfinal) { + A final_arc = (*mapper)(A(0, 0, fst->Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0 || + final_arc.weight != Weight::Zero()) + fst->AddArc(s, A(final_arc.ilabel, final_arc.olabel, + final_arc.weight, superfinal)); + fst->SetFinal(s, Weight::Zero()); + } + break; + } + } + } + fst->SetProperties(mapper->Properties(props), kFstProperties); +} + + +// Maps an arc type A using a mapper function object C, passed +// by value. This version modifies its Fst input. +template +void ArcMap(MutableFst *fst, C mapper) { + ArcMap(fst, &mapper); +} + + +// Maps an arc type A to an arc type B using mapper function +// object C, passed by pointer. This version writes the mapped +// input Fst to an output MutableFst. +template +void ArcMap(const Fst &ifst, MutableFst *ofst, C* mapper) { + typedef typename A::StateId StateId; + typedef typename A::Weight Weight; + + ofst->DeleteStates(); + + if (mapper->InputSymbolsAction() == MAP_COPY_SYMBOLS) + ofst->SetInputSymbols(ifst.InputSymbols()); + else if (mapper->InputSymbolsAction() == MAP_CLEAR_SYMBOLS) + ofst->SetInputSymbols(0); + + if (mapper->OutputSymbolsAction() == MAP_COPY_SYMBOLS) + ofst->SetOutputSymbols(ifst.OutputSymbols()); + else if (mapper->OutputSymbolsAction() == MAP_CLEAR_SYMBOLS) + ofst->SetOutputSymbols(0); + + uint64 iprops = ifst.Properties(kCopyProperties, false); + + if (ifst.Start() == kNoStateId) { + if (iprops & kError) ofst->SetProperties(kError, kError); + return; + } + + MapFinalAction final_action = mapper->FinalAction(); + if (ifst.Properties(kExpanded, false)) { + ofst->ReserveStates(CountStates(ifst) + + final_action == MAP_NO_SUPERFINAL ? 0 : 1); + } + + // Add all states. + for (StateIterator< Fst > siter(ifst); !siter.Done(); siter.Next()) + ofst->AddState(); + + StateId superfinal = kNoStateId; + if (final_action == MAP_REQUIRE_SUPERFINAL) { + superfinal = ofst->AddState(); + ofst->SetFinal(superfinal, B::Weight::One()); + } + for (StateIterator< Fst > siter(ifst); !siter.Done(); siter.Next()) { + StateId s = siter.Value(); + if (s == ifst.Start()) + ofst->SetStart(s); + + ofst->ReserveArcs(s, ifst.NumArcs(s)); + for (ArcIterator< Fst > aiter(ifst, s); !aiter.Done(); aiter.Next()) + ofst->AddArc(s, (*mapper)(aiter.Value())); + + switch (final_action) { + case MAP_NO_SUPERFINAL: + default: { + B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + FSTERROR() << "ArcMap: non-zero arc labels for superfinal arc"; + ofst->SetProperties(kError, kError); + } + ofst->SetFinal(s, final_arc.weight); + break; + } + case MAP_ALLOW_SUPERFINAL: { + B final_arc = (*mapper)(A(0, 0, ifst.Final(s), kNoStateId)); + if (final_arc.ilabel != 0 || final_arc.olabel != 0) { + // Add a superfinal state if not already done. + if (superfinal == kNoStateId) { + superfinal = ofst->AddState(); + ofst->SetFinal(superfinal, B::Weight::One()); + } + final_arc.nextstate = superfinal; + ofst->AddArc(s, final_arc); + ofst->SetFinal(s, B::Weight::Zero()); + } else { + ofst->SetFinal(s, final_arc.wei