OpenFst Forum 2013 Archive

When I've eliminated these checks, the speed of my application has been increased for 5%.

PaulDixon - 29 Aug 2013 - 22:32

AlexZatv - 11 Sep 2013 - 15:15

Which optimization is applied to OpenFst 1.3.3 ?

JihoonKim - 18 Aug 2013 - 21:28

OpenFst 1.3.3 is much faster than OpenFst 1.3.1. While fstdeterminize of 1.3.1 takes about 1 hour, that of 1.3.3 takes only less than 1 minute! How can 1.3.3 be this faster? Could anyone explain the reason?

Thanks.

AlexZatv - 19 Aug 2013 - 09:56

JihoonKim - 20 Aug 2013 - 04:16

Can I get OpenFst 1.3.3 Visual Studio Project

JihoonKim - 15 Aug 2013 - 04:47

I have to build OpenFst in Windows. In the download page, Visual Studio project is just for 1.1 and 1.3.1. It seems that latest version 1.3.3 is much faster than 1.3.1 so I need 1.3.3 to be built in Windows.

Is there anyone who has 1.3.3 for windows ?

PaulDixon - 15 Aug 2013 - 19:12

PaulDixon - 15 Aug 2013 - 19:14

https://dl.dropbox.com/u/321851/openfst-1.3.3.zip

The memory map FSTs compile but aren't tested. The ngram FSTs aren't finished that why I never uploaded to the contrib section. Also includes VS2012 solutions.

JihoonKim - 16 Aug 2013 - 01:15

Merging symbol tables

PrashantMathur - 26 Jul 2013 - 10:28

I am a newbie to openfst, so this can sound stupid.

Is there a function which can merge two SymbolTables? I was using A->AddTable(SymbolTable* B) , where I want to merge B in A. function to merge two symbol tables. But I believe AddTable function just appends table B with A and starts indexing with the maximum key. ( I don't know if I am correct).

A 0 a 1 b 2 c 3

B 0 d 1 a 2 b 3

C - Resulting Table 0 a 1 b 2 c 3 d 4

My code needs to do this operation several times, so I thought I better ask first.

Thanks!

PrashantMathur - 26 Jul 2013 - 10:30

C 0 a 1 b 2 c 3 d 4

PrashantMathur - 26 Jul 2013 - 11:10

Is there a function which can merge two SymbolTables?
I was using A->AddTable(SymbolTable* B) , where I want to merge B in A.
But I believe AddTable function just appends table B with A and starts indexing with the maximum key. ( I don't know if I am correct).
A
eps 0
a 1
b 2
c 3

B
eps 0
d 1
a 2
b 3

C - Resulting Table
eps 0
a 1
b 2
c 3
d 4

My code needs to do this operation several times, so I thought I better ask first.
Thanks!

PaulDixon - 27 Jul 2013 - 05:15

I/O error for large FSTs

SamS - 08 Jul 2013 - 14:49

   SymbolTable * syms = new SymbolTable;
   syms->AddSymbol("<eps>");
   syms->AddSymbol("a");

   StdVectorFst res;
   for (int s = 0; s < big_number; s++) {
        res.AddState();
        TropicalWeight final = -log(0.5);
        res.SetFinal(s, final);
        for (int dest = 0; dest < big_number; dest++) {
            res.AddArc(s, StdArc(1, 1, TropicalWeight(-log(0.2)), dest));
        }
    }

    res.SetStart(0);
    res.SetInputSymbols(syms);
    res.SetOutputSymbols(syms);

    res.Write("badfile.fst");
    StdVectorFst* loaded = StdVectorFst::Read("badfile.fst");

    return 0;

For me, the big number seems to be too big at around 923. The printed error message is:

ERROR: VectorFst::Read: read failed: badfile.fst

Any insight into what's going on and how to get around this issue would be appreciated. Thanks!

SamS - 08 Jul 2013 - 16:39

MikySu - 12 Jul 2013 - 12:54

MikySu - 12 Jul 2013 - 13:16

PaulDixon - 13 Jul 2013 - 04:23

Making an FST with C++: How to define strings as labels?

DennisRitter - 19 Jun 2013 - 10:30

Would be glad if someone could point out that to me.

PS Is it even effective to make it all in the C++-editor (I am using Eclipse)?

PaulDixon - 20 Jun 2013 - 02:11

DennisRitter - 20 Jun 2013 - 10:26

SymbolTable* isyms;
   isyms = new SymbolTable("isyms.txt");
   SymbolTable* osyms;
   osyms = new SymbolTable("osyms.txt");

   isyms->AddSymbol("a");
   isyms->AddSymbol("b");
   isyms->AddSymbol("c");

   osyms->AddSymbol("x");
   osyms->AddSymbol("y");
   osyms->AddSymbol("z");

   fst.SetInputSymbols(isyms);
   fst.SetOutputSymbols(osyms);

   // Adds state 0 to the initially empty FST and make it the start state.
   fst.AddState(); // 1st state will be state 0 (returned by AddState)
   fst.SetStart(0); // arg is state ID

   // Adds two arcs exiting state 0.
   // Arc constructor args: ilabel, olabel, weight, dest state ID.
   fst.AddArc(0, StdArc(isyms->Find("a"), osyms->Find("x"), 0.5, 1)); // 1st arg is src state ID
   fst.AddArc(0, StdArc(isyms->Find("b"), osyms->Find("y"), 1.5, 1));

   // Adds state 1 and its arc.
   fst.AddState();
   fst.AddArc(1, StdArc(isyms->Find("c"), osyms->Find("z"), 2.5, 2));

   // Adds state 2 and set its final weight.
   fst.AddState();
   fst.SetFinal(2, 3.5); // 1st arg is state ID, 2nd arg weight

   fst.Write("example.fst");

PaulDixon - 20 Jun 2013 - 19:59

AddSymbol returns the id if the key already exists. So you can remove all the AddSymbol lines (except for the epsilon) and do this instead

fst.AddArc(0, StdArc(isyms->AddSymbol("a"), osyms- >AddSymbol("x"), 0.5, 1));

From memory in this case I think you would need to add the Symbol tables after adding all the arcs. Internally I think it will make a copy when you use SetInputSymbols method so might also need to delete the SymbolTables also.

DennisRitter - 21 Jun 2013 - 05:01

PS You now helped me the third time, first time as Edobashira on your old blog :). I was DreeDrunk at that time. Shall I mark my thread with something like a SOLVED-tag?

PaulDixon - 23 Jun 2013 - 16:50

GenericRegister::GetEntry : lookup failed in shared object

MarkusD - 12 May 2013 - 20:01

But I'm getting the runtime error:

ERROR: GenericRegister::GetEntry : lookup failed in shared object: expectation-arc.so FATAL: No operation found for "CompileFst" on arc type expectation

How can I fix this?

The register call in my code looks like this (my arc is called MDExpectationArc):

#include <fst/const-fst.h> #include <fst/edit-fst.h> #include <fst/vector-fst.h> #include <fst/script/register.h> #include <fst/script/fstscript.h> namespace fst { namespace script { REGISTER_FST(VectorFst, MDExpectationArc); REGISTER_FST(ConstFst, MDExpectationArc); REGISTER_FST(EditFst, MDExpectationArc); REGISTER_FST_CLASSES(MDExpectationArc); REGISTER_FST_OPERATIONS(MDExpectationArc); }}

Here is how I compile: /usr/bin/c++ -fPIC -O2 -shared -o expectation-arc.so expectation-arc-inline.cc.o /c01_data/mdreyer/software/openfst-1.3.3/lib/libfst.so

or this, gives the same error: /usr/bin/c++ -fPIC -O2 -shared -Wl,-soname,expectation-arc.so -o expectation-arc.so expectation-arc-inline.cc.o openfst-1.3.3/lib/libfst.so -ldl -Wl,-rpath,openfst-1.3.3/lib

It used to work for me with an old openfst version, but I'm getting this error now with openfst 1.3.3.

MarkusD - 12 May 2013 - 20:07

fstcompile --arc-type=expectation

where it loads the expectation-arc.so file that I created using the c++ commands above.

PaulDixon - 13 May 2013 - 08:10

how to use fstreplace tool

HuanliangWang - 09 May 2013 - 21:54

Thanks,

Huanliang Wang

Regex to FST

RaihanRasool - 07 May 2013 - 12:56

Using OpenFst library we can create FST for a given regular expression. But is there any way I could develop a generic RegEx to FST converter that takes 'any' regular expression and build FST ?

PaulDixon - 09 May 2013 - 00:09

http://stackoverflow.com/questions/11819185/steps-to-creating-an-nfa-from-a-regular-expression

MarkusD - 12 May 2013 - 19:55

http://www.openfst.org/twiki/bin/view/GRM/Thrax

KennethRBeesley - 2017-01-26 - 22:58

Coordinate Descent Solution for Rational Kernels

AbielRoche - 01 May 2013 - 13:59

“FATAL: StringWeight::Plus: unequal arguments” when running fstdeterminize.

JiaP - 31 Mar 2013 - 21:51

When I ran fstdeterminize on this transducer, the command line tool exited with following error message: FATAL: StringWeight::Plus: unequal arguments (non-functional FST?) w1 = 1 w2 = 2

I will try to construct such transducer directly using C++ API. Mean while, I’d appreciate any suggestion.

Jia

PaulDixon - 01 Apr 2013 - 01:59

http://www.cs.nyu.edu/~mohri/pub/hbka.pdf

EricLebigot - 03 Apr 2013 - 22:37

@PaulDixon

Composition result too large: how to make smaller?

EricLebigot - 25 Mar 2013 - 22:27

I am trying to calculate a kernel of the form T∘T^-1 from a transducer T, but the calculation uses up a lot of memory and I have to stop it before it converges (I stopped at 25 GB of swap). What could I try to do in order to calculate the composition result? (My ultimate goal is to calculate a kernel between acceptors A and B through the A∘T∘T^-1∘B composition and getting the (log) total weight between the starting and final states. A difficulty is that A∘T can produce a huge number of paths, and I was hoping that calculating T∘T^-1 could help solve this difficulty.)

I tried to first optimize transducer T, but this failed (a first epsilon removal yields a fatal error about StringWeight::Plus being given unequal arguments, as does determinization).

Here are some characteristics of transducer T, if they matter:

- About 15 nodes and 200k arcs.

- Accommodates input strings of any size through the use of internal loops.

If necessary, I can remove all loops, or some loops (because I know in advance how big the input strings can be); this would multiply the number of nodes and arcs by maybe 100 or 600 (depending on which loops I remove). Could removing loops significantly with the "too much memory used for composition" problem?

I could also limit the number of arcs, but this would make the transducer less expressive, so I would like to avoid this. However, if this is the best way of speeding up the calculation of T∘T^-1 and limiting its memory requirement, I am ready to do that.

What would you suggest, so that T∘T^-1 can really be calculated?

PaulDixon - 26 Mar 2013 - 05:35

I don't think epsilon removal uses the StringWeight are your weights in the log/tropical semiring? Another problem could be negative weighted epsilon cycles.

EricLebigot - 26 Mar 2013 - 10:02

Transducer T can produce many epsilons (in about half of the 200k arcs) before reaching a final state (and T^-1 therefore can consume many epsilons). This produces a huge number of possible outputs, and I was hoping that OpenFST could somehow "magically" calculate T∘T^-1 despite this. This epsilon production cannot be removed, because it is one of the main purposes of transducer T to remove parts of the input strings.

The weights are in the log semiring. There are cycles that produce epsilon (in T), with a weight of LogWeight(0.69…) (corresponding to 0.5 in real space).

With these precisions, what do you think is the best way to speed up the composition? reducing the number of arcs (I can do this by reducing the number of recognized "letters")?

PaulDixon - 01 Apr 2013 - 07:10

EricLebigot - 01 Apr 2013 - 23:56

@PaulDixon

http://www.normalesup.org/~lebigot/special/transducer.pdf

DoganCan - 02 Apr 2013 - 06:09

The problem is that transducer T can produce infinitely many consecutive epsilons (when it is not restricted by input A) and similarly transducer T^-1 can consume infinitely many consecutive epsilons (when it is not restricted by output B). Naturally, composition does not terminate. You will have to avoid "all" epsilon loops on the output side of T if you want to compute ToT^-1, i.e. limiting the number of output-epsilon arcs won't help. Unfortunately there is no such magic hidden in openfst

Cheers, Dogan

EricLebigot - 02 Apr 2013 - 09:32

@DoganCan

EricLebigot - 02 Apr 2013 - 09:46

http://www.normalesup.org/~lebigot/special/

DoganCan - 03 Apr 2013 - 04:19

It looks like my initial assessment was incorrect. I thought composition would somehow force enumeration of all possible matches between the epsilon cycles on the output side of T and the epsilon cycles on the input of T^-1. Instead, what happens is composition simply creates paths which first generate possibly infinitely many epsilons and then consume possibly infinitely many epsilons. The composition output for the small transducer is correct as far as I can tell.

I think the blow-up in composition is caused by the self-loops on states A_CAT_V_KEPT and B_CAT_V_KEPT. More explicitly, since T maps each input symbol on these arcs to "Wild" and T^-1 maps "Wild" back to these symbols, composition output has a mapping between each input symbol pair. If the big transducer is following the same pattern, there will be around 10K x 10K = 100M self loops in the output of composition for each of these two states.

Cheers, Dogan

EricLebigot - 03 Apr 2013 - 05:31

Thank you for following up! Your remarks are very useful. The structure of the input data is such that the Wild labels can be specialized, so that the number of possible matches is reduced (PCP_123:Wild is now PCP_123:PCP_Wild, etc., so that only similar categories match through Wild). The result is that calculating kernel elements is much faster, thank you!

Maybe will the calculation of T∘T^-1 require less memory, too…

Best, EOL

Double delete bug in fst far reader

DoganCan - 05 Mar 2013 - 04:14

I came across a double delete bug in the implementation of FstFarReader class. ReadFst method deletes the current fst before reading a new one, however if there is no more fst to read then the current fst pointer is left dangling. That leads to a segfault when the class destructor is called. You might trigger the error with

farequal fst1 fst2

I fixed the problem by moving the pointer deletion after the check for whether there is more fst to read.

This error is not triggered by other far utilities reading from an fst archive (farprintstrings, farinfo and farextract) since these tools, unlike farequal, do not delete the far reader pointer after they are done with it. It might be a good idea to fix that as well.

Cheers, Dogan

Get the Arcs whose nextstate is equal to a given q

JuanMiguelCejuela - 04 Mar 2013 - 08:31

DoganCan - 05 Mar 2013 - 04:50

Cheers, Dogan

AlexZatv - 05 Mar 2013 - 07:10

Testing an FST for epsilon cycles

KennethRBeesley - 24 Jan 2013 - 00:41

KennethRBeesley - 22 Feb 2013 - 12:16

bool isInputEpsilonCycleFree(StdVectorFst * fstp) {

   set<StateId> stateSet ;   // reuse this set of "visited states"
   // if the machine has no cycles at all, then it's epsilon-cycle-free
   if (fstp->Properties(kAcyclic, true))
      return true ;

   // loop through the states, looking for input epsilon cycles
   for (StateIterator<StdVectorFst> siter(*fstp) ;
      !siter.Done() ;
      siter.Next()) {
      stateSet.clear() ;
      if (findInputEpsilonCycle(fstp, siter.Value(), stateSet))
         return false ;
   }
   // no input epsilon cycles found
   return true ;
}

bool findInputEpsilonCycle(StdVectorFst *fstp, StateId s, set<StateId> &stateSet) {
   // try to find an input epsilon cycle from state s back
   // to itself, or any other input epsilon cycle found during the search
   
        // stateSet is the set of states previously visited during the search from s
   if (stateSet.find(s) != stateSet.end()) 
      // found a loop
      return true ;
   // remember state s as "visited"
   stateSet.insert(s) ;
   for (ArcIterator<StdVectorFst> aiter(*fstp, s) ;
      !aiter.Done() ;
      aiter.Next()) {
      StdArc arc = aiter.Value() ;
      // deal only with arcs with epsilon on the input side
      if (arc.ilabel != 0)     // 0 (zero) is wired in as epsilon in OpenFst
         continue ;
      // here the ilabel is 0 (epsilon)
      // recursively look for an input epsilon loop from arc.nextstate
      if (findInputEpsilonCycle(fstp, arc.nextstate, stateSet))
            return true ;
   }
   return false ;
}

PaulDixon - 23 Feb 2013 - 05:48

Using the OpenFst visitor to find a topological order on the epsilon input subgraph should work.

template<class Arc>
bool HasInputEpsilonCycle(const Fst<Arc>& fst) {
  vector<typename Arc::StateId> order;
  bool acyclic = false;
  TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic);
  DfsVisit(fst, &top_order_visitor, InputEpsilonArcFilter<Arc>());
  return !acyclic;
}

KennethRBeesley - 21 Mar 2013 - 15:30

Example of k-closed semiring that is non-idempotent

KonstantinSelivanov - 10 Jan 2013 - 04:30

could you give an example k-close semiring that is not idempotent.

Thanks!

CyrilAllauzen - 18 Jan 2013 - 20:46

(Mohri, 2002)

-- Michael Riley - 2018-05-30

Comments