1 files changed, 0 insertions, 560 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/string-weight.h b/kaldi_io/src/tools/openfst/include/fst/string-weight.h
deleted file mode 100644
index 1beeb33..0000000
--- a/kaldi_io/src/tools/openfst/include/fst/string-weight.h
+++ /dev/null
@@ -1,560 +0,0 @@
-// string-weight.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: [email protected] (Michael Riley)
-//
-// \file
-// String weight set and associated semiring operation definitions.
-
-#ifndef FST_LIB_STRING_WEIGHT_H__
-#define FST_LIB_STRING_WEIGHT_H__
-
-#include <list>
-#include <string>
-
-#include <fst/product-weight.h>
-#include <fst/weight.h>
-
-namespace fst {
-
-const int kStringInfinity = -1; // Label for the infinite string
-const int kStringBad = -2; // Label for a non-string
-const char kStringSeparator = '_'; // Label separator in strings
-
-// Determines whether to use left or right string semiring. Includes
-// restricted versions that signal an error if proper prefixes
-// (suffixes) would otherwise be returned by Plus, useful with various
-// algorithms that require functional transducer input with the
-// string semirings.
-enum StringType { STRING_LEFT = 0, STRING_RIGHT = 1 ,
- STRING_LEFT_RESTRICT = 2, STRING_RIGHT_RESTRICT };
-
-#define REVERSE_STRING_TYPE(S) \
- ((S) == STRING_LEFT ? STRING_RIGHT : \
- ((S) == STRING_RIGHT ? STRING_LEFT : \
- ((S) == STRING_LEFT_RESTRICT ? STRING_RIGHT_RESTRICT : \
- STRING_LEFT_RESTRICT)))
-
-template <typename L, StringType S = STRING_LEFT>
-class StringWeight;
-
-template <typename L, StringType S = STRING_LEFT>
-class StringWeightIterator;
-
-template <typename L, StringType S = STRING_LEFT>
-class StringWeightReverseIterator;
-
-template <typename L, StringType S>
-bool operator==(const StringWeight<L, S> &, const StringWeight<L, S> &);
-
-
-// String semiring: (longest_common_prefix/suffix, ., Infinity, Epsilon)
-template <typename L, StringType S>
-class StringWeight {
- public:
- typedef L Label;
- typedef StringWeight<L, REVERSE_STRING_TYPE(S)> ReverseWeight;
-
- friend class StringWeightIterator<L, S>;
- friend class StringWeightReverseIterator<L, S>;
- friend bool operator==<>(const StringWeight<L, S> &,
- const StringWeight<L, S> &);
-
- StringWeight() { Init(); }
-
- template <typename Iter>
- StringWeight(const Iter &begin, const Iter &end) {
- Init();
- for (Iter iter = begin; iter != end; ++iter)
- PushBack(*iter);
- }
-
- explicit StringWeight(L l) { Init(); PushBack(l); }
-
- static const StringWeight<L, S> &Zero() {
- static const StringWeight<L, S> zero(kStringInfinity);
- return zero;
- }
-
- static const StringWeight<L, S> &One() {
- static const StringWeight<L, S> one;
- return one;
- }
-
- static const StringWeight<L, S> &NoWeight() {
- static const StringWeight<L, S> no_weight(kStringBad);
- return no_weight;
- }
-
- static const string &Type() {
- static const string type =
- S == STRING_LEFT ? "string" :
- (S == STRING_RIGHT ? "right_string" :
- (S == STRING_LEFT_RESTRICT ? "restricted_string" :
- "right_restricted_string"));
- return type;
- }
-
- bool Member() const;
-
- istream &Read(istream &strm);
-
- ostream &Write(ostream &strm) const;
-
- size_t Hash() const;
-
- StringWeight<L, S> Quantize(float delta = kDelta) const {
- return *this;
- }
-
- ReverseWeight Reverse() const;
-
- static uint64 Properties() {
- return (S == STRING_LEFT || S == STRING_LEFT_RESTRICT ?
- kLeftSemiring : kRightSemiring) | kIdempotent;
- }
-
- // NB: This needs to be uncommented only if default fails for this impl.
- // StringWeight<L, S> &operator=(const StringWeight<L, S> &w);
-
- // These operations combined with the StringWeightIterator and
- // StringWeightReverseIterator provide the access and mutation of
- // the string internal elements.
-
- // Common initializer among constructors.
- void Init() { first_ = 0; }
-
- // Clear existing StringWeight.
- void Clear() { first_ = 0; rest_.clear(); }
-
- size_t Size() const { return first_ ? rest_.size() + 1 : 0; }
-
- void PushFront(L l) {
- if (first_)
- rest_.push_front(first_);
- first_ = l;
- }
-
- void PushBack(L l) {
- if (!first_)
- first_ = l;
- else
- rest_.push_back(l);
- }
-
- private:
- L first_; // first label in string (0 if empty)
- list<L> rest_; // remaining labels in string
-};
-
-
-// Traverses string in forward direction.
-template <typename L, StringType S>
-class StringWeightIterator {
- public:
- explicit StringWeightIterator(const StringWeight<L, S>& w)
- : first_(w.first_), rest_(w.rest_), init_(true),
- iter_(rest_.begin()) {}
-
- bool Done() const {
- if (init_) return first_ == 0;
- else return iter_ == rest_.end();
- }
-
- const L& Value() const { return init_ ? first_ : *iter_; }
-
- void Next() {
- if (init_) init_ = false;
- else ++iter_;
- }
-
- void Reset() {
- init_ = true;
- iter_ = rest_.begin();
- }
-
- private:
- const L &first_;
- const list<L> &rest_;
- bool init_; // in the initialized state?
- typename list<L>::const_iterator iter_;
-
- DISALLOW_COPY_AND_ASSIGN(StringWeightIterator);
-};
-
-
-// Traverses string in backward direction.
-template <typename L, StringType S>
-class StringWeightReverseIterator {
- public:
- explicit StringWeightReverseIterator(const StringWeight<L, S>& w)
- : first_(w.first_), rest_(w.rest_), fin_(first_ == 0),
- iter_(rest_.rbegin()) {}
-
- bool Done() const { return fin_; }
-
- const L& Value() const { return iter_ == rest_.rend() ? first_ : *iter_; }
-
- void Next() {
- if (iter_ == rest_.rend()) fin_ = true;
- else ++iter_;
- }
-
- void Reset() {
- fin_ = false;
- iter_ = rest_.rbegin();
- }
-
- private:
- const L &first_;
- const list<L> &rest_;
- bool fin_; // in the final state?
- typename list<L>::const_reverse_iterator iter_;
-
- DISALLOW_COPY_AND_ASSIGN(StringWeightReverseIterator);
-};
-
-
-// StringWeight member functions follow that require
-// StringWeightIterator or StringWeightReverseIterator.
-
-template <typename L, StringType S>
-inline istream &StringWeight<L, S>::Read(istream &strm) {
- Clear();
- int32 size;
- ReadType(strm, &size);
- for (int i = 0; i < size; ++i) {
- L label;
- ReadType(strm, &label);
- PushBack(label);
- }
- return strm;
-}
-
-template <typename L, StringType S>
-inline ostream &StringWeight<L, S>::Write(ostream &strm) const {
- int32 size = Size();
- WriteType(strm, size);
- for (StringWeightIterator<L, S> iter(*this); !iter.Done(); iter.Next()) {
- L label = iter.Value();
- WriteType(strm, label);
- }
- return strm;
-}
-
-template <typename L, StringType S>
-inline bool StringWeight<L, S>::Member() const {
- if (Size() != 1)
- return true;
- StringWeightIterator<L, S> iter(*this);
- return iter.Value() != kStringBad;
-}
-
-template <typename L, StringType S>
-inline typename StringWeight<L, S>::ReverseWeight
-StringWeight<L, S>::Reverse() const {
- ReverseWeight rw;
- for (StringWeightIterator<L, S> iter(*this); !iter.Done(); iter.Next())
- rw.PushFront(iter.Value());
- return rw;
-}
-
-template <typename L, StringType S>
-inline size_t StringWeight<L, S>::Hash() const {
- size_t h = 0;
- for (StringWeightIterator<L, S> iter(*this); !iter.Done(); iter.Next())
- h ^= h<<1 ^ iter.Value();
- return h;
-}
-
-// NB: This needs to be uncommented only if default fails for this the impl.
-//
-// template <typename L, StringType S>
-// inline StringWeight<L, S>
-// &StringWeight<L, S>::operator=(const StringWeight<L, S> &w) {
-// if (this != &w) {
-// Clear();
-// for (StringWeightIterator<L, S> iter(w); !iter.Done(); iter.Next())
-// PushBack(iter.Value());
-// }
-// return *this;
-// }
-
-template <typename L, StringType S>
-inline bool operator==(const StringWeight<L, S> &w1,
- const StringWeight<L, S> &w2) {
- if (w1.Size() != w2.Size())
- return false;
-
- StringWeightIterator<L, S> iter1(w1);
- StringWeightIterator<L, S> iter2(w2);
-
- for (; !iter1.Done() ; iter1.Next(), iter2.Next())
- if (iter1.Value() != iter2.Value())
- return false;
-
- return true;
-}
-
-template <typename L, StringType S>
-inline bool operator!=(const StringWeight<L, S> &w1,
- const StringWeight<L, S> &w2) {
- return !(w1 == w2);
-}
-
-template <typename L, StringType S>
-inline bool ApproxEqual(const StringWeight<L, S> &w1,
- const StringWeight<L, S> &w2,
- float delta = kDelta) {
- return w1 == w2;
-}
-
-template <typename L, StringType S>
-inline ostream &operator<<(ostream &strm, const StringWeight<L, S> &w) {
- StringWeightIterator<L, S> iter(w);
- if (iter.Done())
- return strm << "Epsilon";
- else if (iter.Value() == kStringInfinity)
- return strm << "Infinity";
- else if (iter.Value() == kStringBad)
- return strm << "BadString";
- else
- for (size_t i = 0; !iter.Done(); ++i, iter.Next()) {
- if (i > 0)
- strm << kStringSeparator;
- strm << iter.Value();
- }
- return strm;
-}
-
-template <typename L, StringType S>
-inline istream &operator>>(istream &strm, StringWeight<L, S> &w) {
- string s;
- strm >> s;
- if (s == "Infinity") {
- w = StringWeight<L, S>::Zero();
- } else if (s == "Epsilon") {
- w = StringWeight<L, S>::One();
- } else {
- w.Clear();
- char *p = 0;
- for (const char *cs = s.c_str(); !p || *p != '\0'; cs = p + 1) {
- int l = strtoll(cs, &p, 10);
- if (p == cs || (*p != 0 && *p != kStringSeparator)) {
- strm.clear(std::ios::badbit);
- break;
- }
- w.PushBack(l);
- }
- }
- return strm;
-}
-
-
-// Default is for the restricted left and right semirings. String
-// equality is required (for non-Zero() input. This restriction
-// is used in e.g. Determinize to ensure functional input.
-template <typename L, StringType S> inline StringWeight<L, S>
-Plus(const StringWeight<L, S> &w1,
- const StringWeight<L, S> &w2) {
- if (!w1.Member() || !w2.Member())
- return StringWeight<L, S>::NoWeight();
- if (w1 == StringWeight<L, S>::Zero())
- return w2;
- if (w2 == StringWeight<L, S>::Zero())
- return w1;
-
- if (w1 != w2) {
- FSTERROR() << "StringWeight::Plus: unequal arguments "
- << "(non-functional FST?)"
- << " w1 = " << w1
- << " w2 = " << w2;
- return StringWeight<L, S>::NoWeight();
- }
-
- return w1;
-}
-
-
-// Longest common prefix for left string semiring.
-template <typename L> inline StringWeight<L, STRING_LEFT>
-Plus(const StringWeight<L, STRING_LEFT> &w1,
- const StringWeight<L, STRING_LEFT> &w2) {
- if (!w1.Member() || !w2.Member())
- return StringWeight<L, STRING_LEFT>::NoWeight();
- if (w1 == StringWeight<L, STRING_LEFT>::Zero())
- return w2;
- if (w2 == StringWeight<L, STRING_LEFT>::Zero())
- return w1;
-
- StringWeight<L, STRING_LEFT> sum;
- StringWeightIterator<L, STRING_LEFT> iter1(w1);
- StringWeightIterator<L, STRING_LEFT> iter2(w2);
- for (; !iter1.Done() && !iter2.Done() && iter1.Value() == iter2.Value();
- iter1.Next(), iter2.Next())
- sum.PushBack(iter1.Value());
- return sum;
-}
-
-
-// Longest common suffix for right string semiring.
-template <typename L> inline StringWeight<L, STRING_RIGHT>
-Plus(const StringWeight<L, STRING_RIGHT> &w1,
- const StringWeight<L, STRING_RIGHT> &w2) {
- if (!w1.Member() || !w2.Member())
- return StringWeight<L, STRING_RIGHT>::NoWeight();
- if (w1 == StringWeight<L, STRING_RIGHT>::Zero())
- return w2;
- if (w2 == StringWeight<L, STRING_RIGHT>::Zero())
- return w1;
-
- StringWeight<L, STRING_RIGHT> sum;
- StringWeightReverseIterator<L, STRING_RIGHT> iter1(w1);
- StringWeightReverseIterator<L, STRING_RIGHT> iter2(w2);
- for (; !iter1.Done() && !iter2.Done() && iter1.Value() == iter2.Value();
- iter1.Next(), iter2.Next())
- sum.PushFront(iter1.Value());
- return sum;
-}
-
-
-template <typename L, StringType S>
-inline StringWeight<L, S> Times(const StringWeight<L, S> &w1,
- const StringWeight<L, S> &w2) {
- if (!w1.Member() || !w2.Member())
- return StringWeight<L, S>::NoWeight();
- if (w1 == StringWeight<L, S>::Zero() || w2 == StringWeight<L, S>::Zero())
- return StringWeight<L, S>::Zero();
-
- StringWeight<L, S> prod(w1);
- for (StringWeightIterator<L, S> iter(w2); !iter.Done(); iter.Next())
- prod.PushBack(iter.Value());
-
- return prod;
-}
-
-
-// Default is for left division in the left string and the
-// left restricted string semirings.
-template <typename L, StringType S> inline StringWeight<L, S>
-Divide(const StringWeight<L, S> &w1,
- const StringWeight<L, S> &w2,
- DivideType typ) {
-
- if (typ != DIVIDE_LEFT) {
- FSTERROR() << "StringWeight::Divide: only left division is defined "
- << "for the " << StringWeight<L, S>::Type() << " semiring";
- return StringWeight<L, S>::NoWeight();
- }
-
- if (!w1.Member() || !w2.Member())
- return StringWeight<L, S>::NoWeight();
-
- if (w2 == StringWeight<L, S>::Zero())
- return StringWeight<L, S>(kStringBad);
- else if (w1 == StringWeight<L, S>::Zero())
- return StringWeight<L, S>::Zero();
-
- StringWeight<L, S> div;
- StringWeightIterator<L, S> iter(w1);
- for (int i = 0; !iter.Done(); iter.Next(), ++i) {
- if (i >= w2.Size())
- div.PushBack(iter.Value());
- }
- return div;
-}
-
-
-// Right division in the right string semiring.
-template <typename L> inline StringWeight<L, STRING_RIGHT>
-Divide(const StringWeight<L, STRING_RIGHT> &w1,
- const StringWeight<L, STRING_RIGHT> &w2,
- DivideType typ) {
-
- if (typ != DIVIDE_RIGHT) {
- FSTERROR() << "StringWeight::Divide: only right division is defined "
- << "for the right string semiring";
- return StringWeight<L, STRING_RIGHT>::NoWeight();
- }
-
- if (!w1.Member() || !w2.Member())
- return StringWeight<L, STRING_RIGHT>::NoWeight();
-
- if (w2 == StringWeight<L, STRING_RIGHT>::Zero())
- return StringWeight<L, STRING_RIGHT>(kStringBad);
- else if (w1 == StringWeight<L, STRING_RIGHT>::Zero())
- return StringWeight<L, STRING_RIGHT>::Zero();
-
- StringWeight<L, STRING_RIGHT> div;
- StringWeightReverseIterator<L, STRING_RIGHT> iter(w1);
- for (int i = 0; !iter.Done(); iter.Next(), ++i) {
- if (i >= w2.Size())
- div.PushFront(iter.Value());
- }
- return div;
-}
-
-
-// Right division in the right restricted string semiring.
-template <typename L> inline StringWeight<L, STRING_RIGHT_RESTRICT>
-Divide(const StringWeight<L, STRING_RIGHT_RESTRICT> &w1,
- const StringWeight<L, STRING_RIGHT_RESTRICT> &w2,
- DivideType typ) {
-
- if (typ != DIVIDE_RIGHT) {
- FSTERROR() << "StringWeight::Divide: only right division is defined "
- << "for the right restricted string semiring";
- return StringWeight<L, STRING_RIGHT_RESTRICT>::NoWeight();
- }
-
- if (!w1.Member() || !w2.Member())
- return StringWeight<L, STRING_RIGHT_RESTRICT>::NoWeight();
-
- if (w2 == StringWeight<L, STRING_RIGHT_RESTRICT>::Zero())
- return StringWeight<L, STRING_RIGHT_RESTRICT>(kStringBad);
- else if (w1 == StringWeight<L, STRING_RIGHT_RESTRICT>::Zero())
- return StringWeight<L, STRING_RIGHT_RESTRICT>::Zero();
-
- StringWeight<L, STRING_RIGHT_RESTRICT> div;
- StringWeightReverseIterator<L, STRING_RIGHT_RESTRICT> iter(w1);
- for (int i = 0; !iter.Done(); iter.Next(), ++i) {
- if (i >= w2.Size())
- div.PushFront(iter.Value());
- }
- return div;
-}
-
-
-// Product of string weight and an arbitray weight.
-template <class L, class W, StringType S = STRING_LEFT>
-struct GallicWeight : public ProductWeight<StringWeight<L, S>, W> {
- typedef GallicWeight<L, typename W::ReverseWeight, REVERSE_STRING_TYPE(S)>
- ReverseWeight;
-
- GallicWeight() {}
-
- GallicWeight(StringWeight<L, S> w1, W w2)
- : ProductWeight<StringWeight<L, S>, W>(w1, w2) {}
-
- explicit GallicWeight(const string &s, int *nread = 0)
- : ProductWeight<StringWeight<L, S>, W>(s, nread) {}
-
- GallicWeight(const ProductWeight<StringWeight<L, S>, W> &w)
- : ProductWeight<StringWeight<L, S>, W>(w) {}
-};
-
-} // namespace fst
-
-#endif // FST_LIB_STRING_WEIGHT_H__