OpenFst Forum

KonstantinSelivanov - 11 Sep 2010 - 08:58

But it seems they have some distinctions. E.g. when I create language model using grmcount/grmake there are some arcs with weight "Infinity". I didn't see such weights in openfst library. Or maybe I'm doing something wrong?

MichaelRiley - 20 Oct 2010 - 18:00

FAST_LOG_PROB_ARC_SELECTOR

AMorenoDaniel - 08 Sep 2010 - 13:01

FAST_LOG_PROB_ARC_SELECTOR

My first compilation succeeded on Cygwin after I commented out that option. Cheers

BusyBeaver - 08 Sep 2010 - 13:27

CyrilAllauzen - 09 Sep 2010 - 11:40

MichaelRiley - 09 Sep 2010 - 17:11

Compiling 1.2.1 on Mac OSX

RichardSproat - 02 Sep 2010 - 17:09

g++ -DHAVE_CONFIG_H -I./../include -g -O2 -MT replace.lo -MD -MP -MF .deps/replace.Tpo -c replace.cc -fno-common -DPIC -o .libs/replace.o /usr/include/c++/4.0.0/tr1/hashtable: In member function 'typename std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::const_iterator std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::find(const Key&) const [with Key = int, Value = std::pair, Allocator = std::allocator<std::pair >, ExtractKey = Internal::extract1st<std::pair >, Equal = std::equal_to, H1 = std::tr1::hash, H2 = Internal::mod_range_hashing, H = Internal::default_ranged_hash, RehashPolicy = Internal::prime_rehash_policy, bool cache_hash_code = false, bool mutable_iterators = true, bool unique_keys = true]': ./../include/fst/replace.h:531: instantiated from 'bool fst::ReplaceFstImpl<A, T>::IsNonTerminal(typename A::Label) const [with A = fst::LogArc, T = fst::DefaultReplaceStateTable<fst::LogArc, ssize_t>]' ./../include/fst/replace.h:560: instantiated from 'size_t fst::ReplaceFstImpl<A, T>::NumInputEpsilons(typename A::StateId) [with A = fst::LogArc, T = fst::DefaultReplaceStateTable<fst::LogArc, ssize_t>]' ./../include/fst/fst.h:732: instantiated from 'size_t fst::ImplToFst<I, F>::NumInputEpsilons(typename I::Arc::StateId) const [with I = fst::ReplaceFstImpl<fst::LogArc, fst::DefaultReplaceStateTable<fst::LogArc, ssize_t> >, F = fst::Fst<fst::LogArc>]' replace.cc:43: instantiated from here /usr/include/c++/4.0.0/tr1/hashtable:1136: error: passing 'const std::tr1::hashtable<int, std::pair, std::allocator<std::pair >, Internal::extract1st<std::pair >, std::equal_to, std::tr1::hash, Internal::mod_range_hashing, Internal::default_ranged_hash, Internal::prime_rehash_policy, false, true, true>' as 'this' argument of 'typename std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::node* std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::find_node(Internal::hash_node<Value, cache_hash_code>*, const Key&, typename std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::hash_code_t) [with Key = int, Value = std::pair, Allocator = std::allocator<std::pair >, ExtractKey = Internal::extract1st<std::pair >, Equal = std::equal_to, H1 = std::tr1::hash, H2 = Internal::mod_range_hashing, H = Internal::default_ranged_hash, RehashPolicy = Internal::prime_rehash_policy, bool cache_hash_code = false, bool mutable_iterators = true, bool unique_keys = true]' discards qualifiers make[3]: * [replace.lo] Error 1

RichardSproat - 02 Sep 2010 - 19:01

http://openfst.cs.nyu.edu/twiki/bin/view/FST/CompilingOnMacOSX

did the relevant updates, and was fine compiling 1.1

CyrilAllauzen - 03 Sep 2010 - 11:56

CyrilAllauzen - 03 Sep 2010 - 16:50

Application of RTNs?

KennethRBeesley - 01 Sep 2010 - 13:16

CyrilAllauzen - 01 Sep 2010 - 15:38

Mindtuning for PDT?

KennethRBeesley - 01 Sep 2010 - 13:05

CyrilAllauzen - 01 Sep 2010 - 15:41

pre-determinization

WeiwenLeung - 30 Aug 2010 - 06:19

CyrilAllauzen - 01 Sep 2010 - 15:42

fstepsnormalize

WeiwenLeung - 27 Aug 2010 - 01:56

is there anyone encounter the same problem?

fstcompose output

AliAzimizadeh - 20 Aug 2010 - 16:47

AMorenoDaniel - 21 Aug 2010 - 15:04

AliAzimizadeh - 21 Aug 2010 - 16:34

BlueSky - 29 Oct 2010 - 05:15

Compiling openfst-1.2 on cygwin

AMorenoDaniel - 18 Aug 2010 - 17:48

./configure CXX=g++-4.exe CC=gcc-4.exe --prefix=$HOME/local
make
#make install  # <--- I haven't made it here though.

g++-4.exe -g -O2 -o fstarcsort.exe fstarcsort.o  -ldl ../lib/.libs/libfst.a ../script/.libs/libfstscript.a /usr/lib/gcc/i686-pc-cygwin/4.3.4/libstdc++.dll.a   -L/usr/lib/gcc/i686-pc-cygwin/4.3.4 -L/usr/lib/gcc/i686-pc-cygwin/4.3.4
../script/.libs/libfstscript.a(fst-class.o):fst-class.cc:(.text$_ZN3fst16CompatPropertiesEyy[fst::CompatProperties(unsigned long long, unsigned long long)]+0x143): undefined reference to `fst::PropertyNames'
~~~----ETCETERA----~~~
collect2: ld returned 1 exit status
make[3]: *** [fstarcsort.exe] Error 1
make[2]: *** [all-recursive] Error 1
make[1]: *** [all-recursive] Error 1
make: *** [all] Error 2

libtool: link: warning: undefined symbols not allowed in i686-pc-cygwin shared libraries

/bin/sh ../../libtool --tag=CXX   --mode=link g++-4.exe  -g -O2 -version-info 0:0:0  -o libfst.la -rpath /usr/local/lib compat.lo flags.lo fst.lo properties.lo symbol-table.lo util.lo

/bin/sh ../../libtool --tag=CXX   --mode=link g++-4.exe  -g -O2 -version-info 0:0:0  -o libfstscript.la -rpath /usr/local/lib arcsort.lo closure.lo compile.lo compose.lo concat.lo connect.lo convert.lo decode.lo determinize.lo difference.lo draw.lo encode.lo epsnormalize.lo equal.lo equivalent.lo fst-class.lo info.lo intersect.lo invert.lo map.lo minimize.lo print.lo project.lo prune.lo push.lo randequivalent.lo randgen.lo relabel.lo replace.lo reverse.lo reweight.lo rmepsilon.lo script-impl.lo shortest-distance.lo shortest-path.lo synchronize.lo text-io.lo topsort.lo union.lo weight-class.lo

DanielPovey - 19 Aug 2010 - 05:43

DanielPovey - 19 Aug 2010 - 06:06

AMorenoDaniel - 19 Aug 2010 - 11:37

DanielPovey - 19 Aug 2010 - 13:26

DanielPovey - 20 Aug 2010 - 05:09

PaulDixon - 21 Aug 2010 - 00:21

www.furui.cs.titech.ac.jp/~dixonp/openfstwin-1.2-210810.zip?

It includes prebuilt 32-bit binaries that should also work under cygwin. It's all 1.2 code the 1.1 directory name still needs to be changed.

DanielPovey - 21 Aug 2010 - 05:10

ReplaceFst? () and testing for CyclicDependencies?

KennethRBeesley - 17 Aug 2010 - 14:21

if (ReplaceFst<StdArc>(pairlabelfsts, slabel).CyclicDependencies()) { ...}

returns true, apparently detecting the cyclic dependencies correctly.

Question: Have I used the proper idioms for testing for cyclic dependencies and doing the actual replacement?

#include <fst/fstlib.h>
#include <iostream>

using namespace fst ;

int main() {
   std::cout << "Hello, world!\n" ;

   int a = 97 ;   // code point values
   int b = 98 ;

   // example with cyclic dependencies

   // StdVectorFst is a typedef for VectorFst<StdArc>
   StdVectorFst fst1, fst2, fst3 ;

   // define fst1, a subnetwork (will be arbitrarily associated with -1)
   fst1.AddState() ;     // return 0
   fst1.SetStart(0) ;
   fst1.AddState() ;   // returns 1
   fst1.AddState() ;   // returns 2
   fst1.SetFinal(2, StdArc::Weight::One()) ;
   fst1.AddArc(0, StdArc(a, a, StdArc::Weight::One(), 1)) ;
   // fst1 refers to fst2 (associated below with -2)
   fst1.AddArc(1, StdArc(0, -2, StdArc::Weight::One(), 2)) ;
   //         src        i  o          w             dest

   // define fst2, a subnetwork (will be arbitrarily associated with -2)
   fst2.AddState() ;   // return 0
   fst2.SetStart(0) ;
   fst2.AddState() ;   // return 1
   fst2.AddState() ;   // return 2
   fst2.SetFinal(2, StdArc::Weight::One()) ;
   fst2.AddArc(0, StdArc(b, b, StdArc::Weight::One(), 1)) ;
   // fst2 refers to fst1 (associated below with -1)
   fst2.AddArc(1, StdArc(0, -1, StdArc::Weight::One(), 2)) ;

   // define fst3, the base network (will be arbitrarily associated with -3)
   fst3.AddState() ;   // return 0
   fst3.SetStart(0) ;
   fst3.AddState() ;   // return 1
   fst3.AddState() ;   // return 2
   fst3.SetFinal(2, StdArc::Weight::One()) ;
   // add arcs with "references" to subnetworks
   // output-side -1 will be associated with fst1
   // output-side -2 will be associated with fst2
   // The label references to subnetworks are on the Output Side.
   // The corresponding Input-Side labels can be anything (here 0 for epsilon).
   fst3.AddArc(0, StdArc(0, -1, StdArc::Weight::One(), 1)) ;
   fst3.AddArc(1, StdArc(0, -2, StdArc::Weight::One(), 2)) ;
   //         src        i   o           w            dest

   // set up the vector associating arbitrary numbers with the three networks
   // -1 refers to fst1
   vector< pair< StdArc::Label, const Fst<StdArc> * > > pairlabelfsts ;
   pairlabelfsts.push_back(pair< StdArc::Label, const Fst<StdArc> *>(-1, &fst1) ) ;
   // -2 refers to fst2
   pairlabelfsts.push_back(pair< StdArc::Label, const Fst<StdArc> *>(-2, &fst2) ) ;
   // -3 is the base network
   pairlabelfsts.push_back(pair< StdArc::Label, const Fst<StdArc> *>(-3, &fst3) ) ;
   
   StdArc::Label slabel = -3 ;      // specifies the "base" Fst, which is fst3

   fst3.Write("before.fst") ;      // the network with references

   // Using delayed ReplaceFst
   if (ReplaceFst<StdArc>(pairlabelfsts, slabel).CyclicDependencies()) {
      std::cout << "Has cyclic dependencies.\n" ;
   } else {
      std::cout << "No cyclic dependencies.\n" ; 
      StdVectorFst expandedFst ;   // the result
      // slabel (here -3) is used to find the base Fst supplied in pairlabelfsts
      expandedFst = ReplaceFst<StdArc>(pairlabelfsts, slabel) ;
      expandedFst.Write("intermediate.fst") ;   // the network just after ReplaceFst()
      RmEpsilon(&expandedFst) ;
      expandedFst.Write("after.fst") ;   // the network after RmEpsilon()
   }

   std::cout << "Good-bye, world!\n" ;
}

CyrilAllauzen - 17 Aug 2010 - 15:52

Best, Cyril

Multithreading in OpenFST?

AlbertPark - 09 Jul 2010 - 18:30

I am currently using the OpenFST library, and I was thinking of multithreading my program, and I was curious as to whether the OpenFST library currently supports multithreading. Thank you!

Albert

AlbertPark - 21 Jul 2010 - 04:13

I've gone through looking at the implementation and from what I can tell the OpenFST library currently is not multithreading safe. I've resorted to doing a deep copy of FSTs for each thread. Unfortunately, doing a deep copy was not as straightforward as I thought it would be, or at least I couldn't figure out how to do it elegantly and quickly (The FST I am reading in is very large, and trying to read in the FST multiple times takes much longer than I want). I tried doing a deep copy using Map() with the IdentityMapper as mentioned in a previous post, but found that this only does deep copies of the arcs (given the copy constructor of the Arc and Weight do deep copies), and does a shallow copy of the symbol table, which creates problems for multithreading (when multiple threads try to access the symbol table at once).

I'm not sure if there is an easier way to do this, but here is what I did to change the OpenFST code to support deep copying of the symbol table. I added a new enum code in map.h to MAP_SYMBOLS_ACTION as well as a couple of lines of code for supporting symbol table deep copying, added a function to do a deep copy of the symbol table to symbol-table.h. Finally, I added a Mapper almost identical to the identity mapper, but returns the new enum code for InputSymbolsAction() and OutputSymbolsAction().

Hope this helps anybody trying to multithread!

MichaelRiley - 09 Aug 2010 - 20:42

MichaelRiley - 09 Aug 2010 - 20:44

memory problem in fstcompose

AliAzimizadeh - 07 Jul 2010 - 09:18

0 #_f0 1 #_m0_s2 2 #_m0_s3 3 #_m0_s4 4 #_m0_s5 5 #_m0_s6 6 e$_f0 7 e$_m1_s2 8 e$_m1_s3 9 e$_m1_s4 10 e$_m1_s5 11 e$_m1_s6 12 . . . ow_f6037 170654 s$_f6037 170655 k_f6037 170656 u_f6037 170657 i_f6037 170658 s_f6037 170659 v_f6037 170660 h_f6037 170661 c$_f6037 170662 j_f6037 170663 z$_f6037 170664

its size is about 2.5Mb. then i run the below command successfully:

fstcompile --isymbols=a.sym --osymbols=a.sym tmp1.fst fstcompile --isymbols=a.sym --osymbols=a.sym tmp2.fst

then i want to compose them and run this:

fstcompose tmp2.fst tmp3.fst tmp4.fst

when the symbol number is little the composition is done but in some symbol files the symbol number is very large, for example 170655. in this case, the memory is fulled rapidly and the CPU doesn't work any more. this is my system properties: CPU: Pentium 4 Dual core 2.26GHz Ram: 4G Swap: 15G OS: CentOS 5.3

could you please give me suggestions about the case? Thanks a lot -Ali

PaulDixon - 08 Jul 2010 - 21:52

fstarcsort -sort_type=olabel tmp2.fst > sort2.fst

fstarcsort -sort_type=ilabel tmp3.fst > sort3.fst

fstcompose sort2.fst sort3.fst > tmp4.fst

AliAzimizadeh - 09 Jul 2010 - 06:37

WeiwenLeung - 27 Aug 2010 - 01:33

did you figure out what the problem was ?

Composition and ShortestPath?

ChristopherKermorvant - 22 Apr 2010 - 12:20

I make a composition of 3 transducers F o G o H and I extract the ShortedPath on the resulting transducer. Is there a way to have access to the arcs in F, G and H corresponding to the arcs in the ShortestPath transducer ? I would like to have access to the output symbols of the arcs in F for example.

thank you,

-- Chris

DoganCan - 27 Apr 2010 - 09:59

There may be better solutions to your problem provided by the library but a quick solution is:

1. remove the weights of the shortestpath fst, S = shortest(F o G o H), and project it onto the input and output labels

fstmap -map_type=rmweight s.fst | fstproject > s.in.fst
fstmap -map_type=rmweight s.fst | fstproject -project_output > s.out.fst

2. compose shortest input with F and project the result onto the output labels to get the candidate paths in F

compose shortest output with H and project the result onto the input labels to get the candidate paths in H

fstcompose s.in.fst f.fst | fstproject -project_output > f.out.fst
fstcompose h.fst s.out.fst | fstproject > h.in.fst

3. compose the candidate paths with G (F_out o G o H_in) to obtain the paths in G that survive during the composition

fstcompose f.out.fst g.fst | fstcompose - h.in.fst > internal.fst

4. finally apply shortestpath to this fst to obtain the path in G internal to the shortest path in F o G o H

fstshortestpath internal.fst > shortest.internal.fst

This final transducer should provide the internal path you need. Note that the weights of this transducer are those obtained during the composition not the original weights of G.

Best, Dogan

RolandSchwarz - 13 May 2010 - 09:47

DoganCan - 14 May 2010 - 18:05

I am not entirely sure that I got your problem. I mean the internal path in G should be as complex as S.

Can you post a simple example where the above procedure fails?

Best, Dogan

RolandSchwarz - 15 May 2010 - 04:49

Roland

transducing phoneme lattices using WFSTs

BusyBeaver - 03 Apr 2010 - 11:38

I'd like to convert phoneme lattices into WFSTs and use a grammar transducer to obtain a word lattice out of it. The thing is, that I want to keep additional information e.g. time stamps, acoustic scores, etc. while doing so. Note, that I do not want to obtain any likelihoods on paths in the first place. Instead, I would traverse the final lattice using those accumulated values to determine a likelihood for each transition and user-defined scaling factors myself.

I see two possibilities to keep track on times/scores - by storing them on arcs or using the string semiring to push just arbitrary information in the weights. When I use the string semiring, I could simply push there as much as I want to,and do a composition with my grammar. But then I am somewhat restricted: composition is not supported, because the string semiring is not commutative. I was thinking to rewrite the weighted composition algorithm from the paper, just change the weighting part, since I do not care about the order of elements within my strings anyways. But maybe I could keep my input fst as log/tropical semiring type and attach my scores/time stamps in the arcs. Would it then be possible to use the existing composition algorithm and still copy my attached information into the resulting FST? Maybe it is all much easier than what I thought of here right now, then I'd be glad if you give me some hints Thanks a lot in advance, Stefan

Probabilities as weights

NoChips - 17 Mar 2010 - 16:35

As far as I know the default arcs StdArc is using Tropical weight. How can I change that into Probabilty weight, so that transition weights are multiplied and not summed up?

I was looking for something predefined, but couldn't find anything...

Thank you in advance!

PaulDixon - 18 Mar 2010 - 04:14

There is a counting utility that includes a real semiring implementation and arc registration with the standard command line tools [here][1]

[1]: http://www.furui.cs.titech.ac.jp/~dixonp/wfstcount.zip]

Deleting arcs in an Fst

KennethRBeesley - 05 Mar 2010 - 19:37

KennethRBeesley - 12 Mar 2010 - 16:46

CyrilAllauzen - 17 Aug 2010 - 15:56

JoachimChau - 01 Jun 2011 - 14:58

arcsum.h and arcmerge.h minor bug?

PhilSours - 05 Mar 2010 - 17:29

Memory footprint of an Fst

KennethRBeesley - 22 Feb 2010 - 15:16

hbka reference paper

NewestUser - 26 Jan 2010 - 05:05

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

and the figure for the minimization example, pg. 8, fig. 5(c) seems quite wrong. particularly the 'minimized' version is not equivalent to the original transducer. in the other reference

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

an identical transducer, albeit with different weights on a couple of the arcs, appears very differently in its minimized form.

i verified that the second version referenced in the latter link produces the expected output but it would be nice to confirm this, or alternatively to understand why they are different.

CyrilAllauzen - 26 Jan 2010 - 18:44

NewestUser - 26 Jan 2010 - 22:28

Problems with fstshortestpath

JoeWang - 15 Jan 2010 - 03:56

ERROR: FstMainRegister::GetMain: log-arc.so: cannot open shared object file: No such file or directory ERROR: fstshortestpath: Bad or unknown arc type "log" for this operation (ShortestPathMain)

I have checked my $LD_LIBRARY_PATH, it already includes /usr/local/lib, how come it still cannot find the shared object? Thanks in advance

CyrilAllauzen - 15 Jan 2010 - 13:41

The issue is that the shortest path algorithm does not work over the log semiring.

Hence support for LogArc is not compiled into the fstshortestpath utility and the code tries to locate a shared object containg the definition of that arc type.

Best, Cyril

Is it possible to use fstcompile to construct an acceptor instead of a transducer?

JoeWang - 12 Jan 2010 - 22:09

PaulDixon - 13 Jan 2010 - 00:46

JoeWang - 13 Jan 2010 - 02:43

Missing installation files for creating a user-defined arc type?

PaulDixon - 12 Jan 2010 - 01:11

For the shared object to be detected and loaded a name of the form arc-type.so worked but arc_type.so did not.

I put sample code for a real semiring arc type here

KeithPonting - 19 Nov 2010 - 07:41

CyrilAllauzen - 19 Nov 2010 - 11:22

The contain of my-arc.cc (the source for my-arc.so) should look like:

#include "nlp/fst/lib/fst-inl.h"
#include "nlp/fst/lib/const-fst-inl.h"
#include "nlp/fst/script/register.h"
#include "nlp/fst/script/fstscript.h"
#include "my-arc.h"
namespace fst {
namespace script {

REGISTER_FST(VectorFst, MyArc);
REGISTER_FST(ConstFst, MyArc);
REGISTER_FST_CLASSES(MyArc);

REGISTER_FST_OPERATIONS(MyArc);

}
}

Hope this will work for you.

Cyril

KeithPonting - 30 Nov 2010 - 05:17

CyrilAllauzen - 30 Nov 2010 - 15:36

#include <fst/fst.h>
#include <fst/const-fst.h>
#include <fst/script/register.h>
#include <fst/script/fstscript.h>

KeithPonting - 01 Dec 2010 - 05:39

Problems on Ubuntu Linux 9.10

JoeWang - 11 Jan 2010 - 04:40

CyrilAllauzen - 11 Jan 2010 - 12:05

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib

JoeWang - 12 Jan 2010 - 02:28

Relabel() and epsilon Properties

KennethRBeesley - 04 Jan 2010 - 15:50

vector < pair<StdArc::Label, StdArc::Label> > vect ; vect.push_back(pair<StdArc::Label, StdArc::Label> ( (StdArc::Label) 5, (StdArc::Label) 0 )) ; Relabel(fstp, vect, vect) ;

where fstp is a pointer to a StdVectorFst. ilabels and olabels originally labeled 5 are relabeled correctly as 0, possibly introducing input-side, output-side and double-sided epsilons; but (here's the problem) the Properties kIEpsilons, kNoIEpsilons, kOEpsilons, kNoOEpsilons, kEpsilons and kNoEpsilons are not updated.

At least that's what seems to be happening.

KennethRBeesley - 04 Jan 2010 - 18:03

Finding n-shortest paths

NewUser - 29 Dec 2009 - 16:44

The shortest path algorithm expands the whole transducer and memory usage goes up to 2 GB! (I did see a previous post about setting the option first_path to true, but i need the first 100 or 1000 best paths to be outputted).

It would be of great help if someone had ideas on how to proceed.

Thanks a lot in advance.

Why is 64bit determinization slower 100 times than 32bit determinization?

KyuwoongHwang - 13 Dec 2009 - 21:29

x32/fstdeterminize.exe --fst_default_cache_gc_limit=10000000000 in.fst out.fst ==> 292.40 secs.

x64/fstdeterminize.exe --fst_default_cache_gc_limit=10000000000 in.fst out.fst ==> 39034.45 secs.

NewestUser - 22 Dec 2009 - 04:32

CyrilAllauzen - 11 Jan 2010 - 12:21

Best, Cyril

Adding other properties to arcs

AlexeiIvanov - 22 Nov 2009 - 17:00

Thank you.

AlexeiIvanov - 24 Nov 2009 - 07:01

If anyone needs details please, write me to alexei_v_ivanov@ieee.org

k-closed semirings

RolandSchwarz - 20 Nov 2009 - 08:28

Or alternatively, am I totally mistaken? Can someone shed some light on my confusion?

Cheers,

Roland

CyrilAllauzen - 11 Jan 2010 - 12:17

We haven't implemented Floyd-Warshall. So there is no backup in case of a bad cycle, the algorithm would simply not converge.

Best, Cyril

ReWeight? : Working Example

NewestUser - 08 Nov 2009 - 04:11

CyrilAllauzen - 09 Nov 2009 - 11:45

fstshortestdistance a.fst > potentials.txt
fstreweight --to_initial a.fst potentials.txt > b.fst

fstpush --push_weights --to_initial a.fst > b.fst

read function causes problems

MichaelBerger - 30 Oct 2009 - 16:38

I am trying to read a fst into a simple C++ application, however, for some reason I am being told that certain symbols are undefined:

Ld build/Debug/fstprintallpaths normal x86_64
cd /.../fstprintallpaths
setenv MACOSX_DEPLOYMENT_TARGET 10.6
/Developer/usr/bin/g++-4.2 -arch x86_64 -isysroot /Developer/SDKs/MacOSX10.6.sdk -L/Users/michael/code/fstprintallpaths/build/Debug -L/usr/local/lib -L/usr/local/lib/Cabal-1.6.0.2 -L/usr/local/lib/ImageMagick-6.4.1 -L/usr/local/lib/pkgconfig -L/usr/local/lib/Cabal-1.6.0.2/ghc-6.10.4 -L/usr/local/lib/ImageMagick-6.4.1/config -L/usr/local/lib/ImageMagick-6.4.1/modules-Q16 -L/usr/local/lib/Cabal-1.6.0.2/ghc-6.10.4/Distribution -L/usr/local/lib/Cabal-1.6.0.2/ghc-6.10.4/Language -L/usr/local/lib/ImageMagick-6.4.1/modules-Q16/coders -L/usr/local/lib/ImageMagick-6.4.1/modules-Q16/filters -L/usr/local/lib/Cabal-1.6.0.2/ghc-6.10.4/Distribution/Compat -L/usr/local/lib/Cabal-1.6.0.2/ghc-6.10.4/Distribution/PackageDescription -L/usr/local/lib/Cabal-1.6.0.2/ghc-6.10.4/Distribution/Simple -L/usr/local/lib/Cabal-1.6.0.2/ghc-6.10.4/Language/Haskell -L/usr/local/lib/Cabal-1.6.0.2/ghc-6.10.4/Distribution/Simple/Build -L/usr/local/lib/Cabal-1.6.0.2/ghc-6.10.4/Distribution/Simple/GHC -L. -F/Users/michael/research/projects/lattice_parsing/code/fstprintallpaths/build/Debug -filelist /Users/michael/research/projects/lattice_parsing/code/fstprintallpaths/build/fstprintallpaths.build/Debug/fstprintallpaths.build/Objects-normal/x86_64/fstprintallpaths.LinkFileList -mmacosx-version-min=10.6 -o /Users/michael/research/projects/lattice_parsing/code/fstprintallpaths/build/Debug/fstprintallpaths

Undefined symbols:
  "fst::Int64ToStr(long long, std::basic_string<char, std::char_traits<char>, std::allocator<char> >*)", referenced from:
      fst::FloatWeightTpl<float>::GetPrecisionString()  in fstprintallpaths.o
  "fst::FstHeader::Read(std::basic_istream<char, std::char_traits<char> >&, std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool)", referenced from:
      fst::Fst<fst::ArcTpl<fst::TropicalWeightTpl<float> > >::Read(std::basic_istream<char, std::char_traits<char> >&, fst::FstReadOptions const&)in fstprintallpaths.o
ld: symbol(s) not found
collect2: ld returned 1 exit status



-----------------------------------------------------------------
fstprintallpaths.cpp:

#include "fstprintallpaths.h"

#include <iostream>
#include <vector>
#include <fst/fstlib.h>
#include <fst/fst-decl.h>
#include <fst/vector-fst.h>
#include <fst/weight.h>

using namespace fst;

int main (int argc, char * const argv[]) {
    // insert code here...
   std::cout << "Hello, World!\n";
   StdFst *input = StdFst::Read("blah.fst");
   //StdFst *model = StdFst::Read("blah.fst");
   //printAllStrings(&fst);
    return 0;
}

string itos(int i) { // convert int to string; from Bjarne Stroustrup's FAQ
   stringstream s;
   s << i;
   return s.str();
}

string vectorToString(vector<int> v) {
   if(v.size() == 0)
      return "<>";
   string result = "<" + itos(v[0]);
   for(int i = 1; i < v.size(); i++) {
      result + "," + itos(v[i]);
   }
   return result + ">";
}

void printAllStringsHelper(VectorFst<StdArc> &fst, int state, vector<int> str, TropicalWeight cost) {
   if(fst.Final(state) == TropicalWeight::Zero()) 
      cout << vectorToString(str) << " with cost " << (Times(cost,fst.Final(state))) << endl;
   for(ArcIterator <VectorFst <StdArc> > aiter(fst,state); ! aiter.Done(); aiter.Next()) {
      StdArc arc = aiter.Value();
      str.push_back(arc.ilabel);
      printAllStringsHelper(fst, arc.nextstate, str, Times(cost, arc.weight.Value()));
      str.pop_back();
   }
}

// a bad idea if there are loops :)
void printAllStrings(VectorFst<StdArc> &fst) {
   vector<int> str(0);
   TropicalWeight tw(TropicalWeight::One());
   printAllStringsHelper(fst, 0, str, tw);
}

-----------------------------------------------------------------

fstprintallpaths.h

/*
 *  fstprintallpaths.h
 *  fstprintallpaths
 *
 */

#include <iostream>
#include <vector>
#include <fst/fstlib.h>
#include <fst/fst-decl.h>
#include <fst/vector-fst.h>
#include <fst/weight.h>

using namespace fst;

int main(int argc, char * const argv[]);

string itos(int i);

string vectorToString(vector<int> v);

void printAllStringsHelper(VectorFst<StdArc> &fst, int state, vector<int> str, TropicalWeight cost);

void printAllStrings(VectorFst<StdArc> &fst);

MichaelBerger - 30 Oct 2009 - 16:57

$ g++ fstprintallpaths.cpp fstprintallpaths.h -I  /usr/local/include 
Undefined symbols:
  "fst::FstHeader::Read(std::basic_istream<char, std::char_traits<char> >&, std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool)", referenced from:
      fst::Fst<fst::ArcTpl<fst::TropicalWeightTpl<float> > >::Read(std::basic_istream<char, std::char_traits<char> >&, fst::FstReadOptions const&)in ccspqZtg.o
  "fst::Int64ToStr(long long, std::basic_string<char, std::char_traits<char>, std::allocator<char> >*)", referenced from:
      fst::FloatWeightTpl<float>::GetPrecisionString()  in ccspqZtg.o
ld: symbol(s) not found
collect2: ld returned 1 exit status

PaulDixon - 31 Oct 2009 - 08:19

Determinization increases size of FST

MichaelBerger - 25 Oct 2009 - 14:36

$ fstinfo a_binary.fst
fst type                                          vector
arc type                                          standard
input symbol table                                ia.txt
output symbol table                               oa.txt
# of states                                       24
# of arcs                                         9095
initial state                                     0
# of final states                                 4
# of input/output epsilons                        0
# of input epsilons                               0
# of output epsilons                              9095
# of accessible states                            24
# of coaccessible states                          24
# of connected states                             24
# of strongly conn components                     24
expanded                                          y
mutable                                           y
acceptor                                          n
input deterministic                               n
output deterministic                              n
input/output epsilons                             n
input epsilons                                    n
output epsilons                                   y
input label sorted                                n
output label sorted                               y
weighted                                          y
cyclic                                            n
cyclic at initial state                           n
top sorted                                        y
accessible                                        y
coaccessible                                      y
string                                            n


$ fstinfo a_rmeps.fst
fst type                                          vector
arc type                                          standard
input symbol table                                ia.txt
output symbol table                               oa.txt
# of states                                       24
# of arcs                                         645
initial state                                     0
# of final states                                 4
# of input/output epsilons                        0
# of input epsilons                               0
# of output epsilons                              645
# of accessible states                            24
# of coaccessible states                          24
# of connected states                             24
# of strongly conn components                     24
expanded                                          y
mutable                                           y
acceptor                                          n
input deterministic                               n
output deterministic                              n
input/output epsilons                             n
input epsilons                                    n
output epsilons                                   y
input label sorted                                n
output label sorted                               y
weighted                                          y
cyclic                                            n
cyclic at initial state                           n
top sorted                                        y
accessible                                        y
coaccessible                                      y
string                                            n


$ fstinfo a_determinized.fst 
fst type                                          vector
arc type                                          standard
input symbol table                                ia.txt
output symbol table                               oa.txt
# of states                                       1026
# of arcs                                         22054
initial state                                     0
# of final states                                 906
# of input/output epsilons                        0
# of input epsilons                               0
# of output epsilons                              22054
# of accessible states                            1026
# of coaccessible states                          1026
# of connected states                             1026
# of strongly conn components                     1026
expanded                                          y
mutable                                           y
acceptor                                          n
input deterministic                               y
output deterministic                              n
input/output epsilons                             n
input epsilons                                    n
output epsilons                                   y
input label sorted                                y
output label sorted                               y
weighted                                          y
cyclic                                            n
cyclic at initial state                           n
top sorted                                        y
accessible                                        y
coaccessible                                      y
string                                            n

MichaelBerger - 25 Oct 2009 - 14:38

Is this normal?

CyrilAllauzen - 02 Nov 2009 - 14:31

ArcSort? error with Mutable FSTs

JonathanB - 16 Oct 2009 - 16:45

My code is of the form:

#include "fst/fstlib.h"

using namespace std; using namespace fst;

int main() { StdVectorFst? fst1; StdVectorFst? fst2; StdVectorFst? fst3;

ArcSort? (fst1, StdOLabelCompare? ()); fst3 = ComposeFst? (fst1, fst2);

return 0; }

I posted this question as part of an old topic, but I am reposting it as a new topic because I am not sure whether old topics are still reviewed.

Thank you very much, Jonathan

JonathanB - 16 Oct 2009 - 16:48

#include "fst/fstlib.h"

using namespace std;
using namespace fst;

int main()
{
StdVectorFst fst1;
StdVectorFst fst2;
StdVectorFst fst3;

ArcSort(fst1, StdOLabelCompare());
fst3 = ComposeFst(fst1, fst2);
return 0;
}

PaulDixon - 16 Oct 2009 - 20:27

 
ArcSort(&fst1, StdOLabelCompare());
fst3 = StdComposeFst(fst1, fst2);

do we have a transition that encodes a fail transition?

CamilleChen - 15 Oct 2009 - 15:37

I know that an epsilon transition encodes an empty string. However, I'd like to compose two FSA. In case a label exists in one FSA, but not in another, do we have a fail transition, instead of the epsilon transition, can encode this?

Thanks very much!!

CyrilAllauzen - 15 Oct 2009 - 16:00

You want to use PhiMatcher (or maybe RhoMatcher, I'm not completely sure from your message). See the matcher documentation here.

Best, Cyril

CamilleChen - 15 Oct 2009 - 17:35

Best, Camille

regular expression compiler

FrancoisBarthelemy - 15 Oct 2009 - 05:10

Thanks

Traverse the FST to check if it accepts a string or not and give appropriate output

VipulMittal - 15 Oct 2009 - 02:09

Example FST for word : cat

0 1 c c 1 2 a a 2 3 t n,sg 3

VipulMittal - 15 Oct 2009 - 02:15

CyrilAllauzen - 15 Oct 2009 - 14:41

As for your original question, you want to use Composition.

compute weight automatically

CamilleChen - 14 Oct 2009 - 23:34

I have another question:

if we know the total cost of path1 and we know the total cost of path 2 and path 1 is part of path 2 (say path 1 has 1 arc, and path 2 has 2 arcs, and path2's 1st arc label is the same as the path1's arc's label.)

then, is there a way to automatically combine these two paths in a single fst, by keeping path1's cost as the 1st arc's cost, and subtracting the path1's total cost from path2's total cost, and assign it as the cost of the second arc?

thanks!

CamilleChen - 14 Oct 2009 - 23:36

if we know the total cost of path1

and we know the total cost of path 2

and path 1 is part of path 2 (say path 1 has 1 arc, and path 2 has 2 arcs, and path2's 1st arc label is the same as the path1's arc's label.)

CyrilAllauzen - 15 Oct 2009 - 16:02

This is still not very clear to me. Could you clarify further?

Best, Cyril

CamilleChen - 16 Oct 2009 - 19:18

Now I see how to solve my question. Actually I did not know hot to indicate a path's weight when writing this path into a fst format. After I can do that, I can use the commands to do the calculation, and now, I know how to indicate a path's weight, so, the question is solved!

Thanks!

Camille

how to remove a weighted FSA's weights?

CamilleChen - 13 Oct 2009 - 21:50

RolandSchwarz - 14 Oct 2009 - 03:49

RolandSchwarz - 14 Oct 2009 - 03:50

PaulDixon - 14 Oct 2009 - 19:00

fstmap --map_type=rmweight

CamilleChen - 14 Oct 2009 - 23:27

Performance issues?

RolandSchwarz - 09 Oct 2009 - 10:07

I'v been experimenting around with the openfst library lately and have the following problem: I'm trying to align sequences using a transducer (i.e. find the edit distance with specifics weights to indels and mismatches). The transducer has 4 states and some epsilon transitions to model indels (no double epsilon transitions tho). The sequences to be aligned are nucleotide sequences (alphabet of size 4) and about 1000 nucleotides long. Composition of two of these sequences with the alignment transducer (as in I o T o O, where I is the input and O the output sequence/acceptor) results in a 400mb fst file and takes approximately 3-4 minutes. Computation of the shortest path again another 2 minutes or so.

Now here's my question. It is somehow obvious, that the number of states explodes in composition (1000 * 4 * 1000 are at least 4 mill states), so maybe direct composition is not the way to go. But what can I honestly do to improve performance? I switched from the shell versions to the C library and tried lazy composition. Now composition is done in an instant, but the shortest path algorithm still seems to expand the whole transducer, as memory usage goes up to 500mb and it still takes about 4 minutes.

Is it simply such that the transducer approach to alignment is slow? Computing 200 of these pairwise alignments using traditional dynamic programming takes about 20 seconds. Or did I make a mistake somewhere? Does the shortest path algorithm neccessarily have to expand the full transducer, i.e. does lazy composition help at all in this case? I didn't even expect it to be competitive in terms of speed to dedicated tools, but I hoped it to be at least computationally feasible. I would really appreciate any kind of help.

Cheers,

Roland

CyrilAllauzen - 15 Oct 2009 - 15:51

The issue is indeed that computing the direct composition is not the way to go since it is rather expensive. Your idea of using lazy composition was good but as you noticed, ShortestPath expands the full machine by default. However, there is a way to avoid this behaviour: by using the shortest-first queue discipline and setting the option first_path to true.

ComposeFstOptions opts();
opts.gc_limit=0;  
// This disable the caching of the result of composition
// and should lower the memory usage at no computational cost since
// shortest-path should visit each state in the composed machine at most once.
ComposeFst<Arc> cfst(fst1, fst2, opt);

NaturalShortestFirstQueue<StateId, Weight> state_queue(distance);
ShortestPathOptions<Arc, NaturalShortestFirstQueue<StateId, Weight>,
AnyArcFilter<Arc> >
opts(&state_queue, AnyArcFilter<Arc>());
opts.first_path = true;
ShortestPath(cfst, ofst, &distance, opts);

This example assume composing two machines. In you case fst1 could be I o T (itself delayed or not, since it is a smaller machine both might be worth tryingboth) and fst2 could be O.

This should improve things a lot although it should still be slower than dedicated tools. I am very interested in this, so let me know how things turn out.

Best, Cyril

RolandSchwarz - 16 Oct 2009 - 05:56

All the best,

Roland

Label pushing - unexpected behavior?

JohnS - 02 Oct 2009 - 08:52

Assume we have an FST A as depicted below:

By label pushing FST A (to final state), e.g. by the command
fstpush --push_labels --to_final A.fst PA.fst,
one might expect the following FST:

But instead the result FST PA.fst is generated, depicted below:


Question 1. In many cases, as is the example, there is an obvious way of performing pushing of the output labels to a final state, without adding any new states to the FST. Can you explain this growth behavior – under what circumstances it is triggered and, possibly, how it can be avoided?

When an FST that has been label pushed, is label pushed again, one might expect it to stabilize. However, Applying Push() to the already Pushed FST A generates the following output.

Question 2. Why is not the OpenFst implementation of label pushing idempotent, (e.g. like weight pushing is) so that the result of Push(A) is identical to result of Push(Push(A)) ?
Thanks!
-John

CyrilAllauzen - 15 Oct 2009 - 16:29

The reason for this is that label-pushing is implemented by considering the input transducer as a weighted automaton over the string semiring and applying weight-pushing (over the string semiring). The result is then the following weighted automaton over the string semiring:

The issue is how to convert that weighted automaton over the string into a transducer. Currently, we use the second step of the epsilon-normalization algorithm to do this. This is also what the cause the operation to be non idempotent.

One way to partially avoid the problem, would be to first reverse the transducer, apply label-pushing towards the initial state and reverse again:

fstreverse A.fst | fstpush --push_labels | fstreverse > PA.fst

This would result in:

The extra epsilon transitions are due to the use of reverse.

Best, Cyril

JohnS - 23 Oct 2009 - 05:48

Thank you for taking your time to answer this question so thoroughly. I assume there exists, at least theoretically, a generic pushing algorithm to accomplish idempotent and “non-growing” label pushing. Do you agree on this? And if so, would you endorse such an algorithm to be included in any future version of OpenFST?

Best, John

Problem with Determinize and Minimize

VipulMittal - 01 Oct 2009 - 02:17

But the problem is when I determinize it, it gives an error that the FST is non-functional i.e. for a particulat input there are more than one possible outputs, which will be there in this case.

So can someone please help me with this ??

Thank you, Vipul

DoganCan - 01 Oct 2009 - 19:55

Best

Dogan Can

Constrains for the maximum size of the FSTs?

OanaNicolov - 30 Sep 2009 - 19:53

Could you please tell me an estimate of the maximum size (in terms of #states and/or #transitions) of the FSTs, the openfst toolkit can work with (let's say on a machine with 8G of memory)? Alternatively, what was the size of your largest FST you worked with?

Thank you. Oana

DoganCan - 01 Oct 2009 - 20:14

OpenFst is a very efficient library which scales well to large problems. The answer to your question depends on the properties of the fsts and what you would like to do with them. For instance, you may run the shortest path and pruning algorithms over very large fsts (several millions of states and transitions) while you may not be able to determinize them or compose them with other large machines. What you can do also depends on whether your input fsts are acyclic, epsilon free etc. Using lazy implementations may help if your particular task does nor require complete fsts to be loaded onto the memory upfront. In short, (in my opinion) your best bet is to try and see.

Best,

Dogan

CyrilAllauzen - 15 Oct 2009 - 14:58

There are two main concrete class in the library ConstFst and VectorFst.

For ConstFst, the memory requirement is 20 bytes per state. and 16 bytes per arc. For VectorFst, the per-state memory requirement is about twice as much due to the overhead introduced by STL data structures.

Doing the math, you will see that you can easily represent machines with hundred of millions of states and transitions in a few GB of RAM.

If memory usage is critical, the CompactFst class can also be used to provide more efficient memory representations.

This addresses the memory requirement for representing an FST in memory. But, as Dogan pointed out, your memory usage will also depends on which algorithms you want to use.

Best, Cyril

RmEpsilon? , AutoQueue? and Queue Disciplines

NewestUser - 11 Sep 2009 - 11:51

Also, are there any examples of employing specific queue disciplines with RmEpsilon? I've not been able to get this to work in practice.

NewestUser - 11 Sep 2009 - 23:59

a stand in symbol for any symbol; printing out the strings for FSA

AnasElghafari - 28 Aug 2009 - 12:32

Thank you for this great library; I am using it for my B.A. thesis project in C.L. I am using it through the shell from within my Java code.

I have a bit of difficulty with a few things. This is one of them:

- Is there a compact way to specify "any other symbol". As in: in state 0 transduce "a" to "b" and transduce any other symbol to "c"?

The problem specifically is that I am creating acceptors where the symbols are words rather than letters, in some cases I might have 1000 words in my isymbols list. I want to build a rational kernel (transducers to count sequences) to work with these acceptors. At some states I need to be able to map every non-explicitly-mentioned input symbol to epsilon with weight 1. How can I specify that? Do I really need to add a thousand arcs for each state?

AnasElghafari - 28 Aug 2009 - 12:34

CyrilAllauzen - 01 Sep 2009 - 11:46

For your second question, you will need to write your own function for this but it should be rather easy. Remember that the number of strings accepted by an acyclic automaton is in the worst case exponential in the size of the automaton.

Best, Cyril

det(L o G) becomes more complex than L o G

ZhijianOu - 25 Aug 2009 - 03:45

A Chinese lexicon L:
# of states                                       215371
# of arcs                                         303286

A Chinese bigram G:
# of states                                        87918
# of arcs                                       16822088

Run fstcompose to get
L o G 
# of states                                       391202
# of arcs                                       17125372

After determinization by running fstdeterminize,
det(L o G)
# of states                                      3479987
# of arcs                                       20071667
more complex !

I don't know why. I follows exactly the paper "Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley. Speech Recognition with Weighted Finite-State Transducers. In Handbook on Speech Processing and Speech Communication, 2008". The output word label in L is already placed on the initial transitions of the word.

The code is as follows:

fstarcsort.exe --sort_type=olabel  L.fst L.fst.sort
fstarcsort.exe --sort_type=ilabel  G.fst G.fst.sort
fstcompose.exe L.fst.sort G.fst.sort LG.fst
fstdeterminize.exe LG.fstb LG.fst.det
fstminimize.exe LG.fst.det LG.fst.min
Memory allocation failed

I run 64-bit openFST on windows 2003 server 64bit edition. The fstminimize.exe returns "Memory allocation failed" is a surprise. 64bit memory space is not sufficient?

Any suggestion that you could offer would be much appreciated.

Best, Zhijian

CyrilAllauzen - 30 Sep 2009 - 12:43

Best, Cyril

How to deal with < / s > label in constructing ngram model

ZhijianOu - 23 Aug 2009 - 23:08

As mentioned in the paper "Allauzen, Mohri and Roark, Generalized algorithms for constructing statistical language models, ACL 2003." , in constructing a ngram model, there are transitions labeled with the end symbol < / s >, that lead to the final state.

To compose L with G, I need to add a psuedo word as follows to the L.

r eh d #0 read
r eh d #1 read
...
#0 </s>
 

Am I correct?

(btw: if I replace the < / s > in G with < eps >, the G is not deterministic. This is not a good way. So I propose the above way.)

Thanks for your patience. Your help is greately appreciated.

Best, Zhijian

CyrilAllauzen - 01 Sep 2009 - 12:09

Best, Cyril

Switching weight pushing in the log semiring and in the tropical semiring

ZhijianOu - 23 Aug 2009 - 22:51

I built a transducer of a trigram, following the paper "Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley. Speech Recognition with Weighted Finite-State Transducers. In Handbook on Speech Processing and Speech Communication, 2008"

As we note, after we introduce the backoff state, the G is only an approximate representation, if there are such seen trigram that have lower probability than its backed-off bigram, i.e. p(z|x,y) < alph(x,y)*p(z|y). To my viewpoints, there are two solutions.

1) One is to splitting states before replacing failure-transition by eps-transition, as proposed in "Allauzen, Mohri and Roark, Generalized algorithms for constructing statistical language models, ACL 2003."

2) The other, as I think, is to create a backoff model from an interpolated algorithm (e.g. modified kn smoothing). Then we have p(z|x,y) > alph(x,y)*p(z|y) for all trigrams. And if we further work in the tropical semiring, the representation will be exact.

So I chose to construct G in the tropical semiring. Now the question comes. As we know, weight pushing in the tropical semiring is inferior to pusing in the log semiring. I'm not sure whether the following procedure is correct, and if it's correct, how to do it? The semiring info is embeded in the arc type. If I use shell command, how can I change the arc type?

1) Switch from representing G (or L o G) in the tropical semiring to representing in the log semiring

2) run fstminimize to get min(L o G)

3) Swtich back to representing min(L o G) in the tropical semiring.

Thanks for your patience. Your help is greately appreciated.

Best, Zhijian

DoganCan - 24 Aug 2009 - 21:08

VectorFst<StdArc> ifst;
VectorFst<StdArc> ofst;
VectorFst<LogArc> lfst;

Map(ifst,&lfst,StdToLogMapper());
Minimize(&lfst);
Map(lfst,&ofst,LogToStdMapper());

Best, Dogan

ZhijianOu - 25 Aug 2009 - 03:35

Sorry for the above lengthy question. To summarize, the main question is: when both lexicon L and grammar G are constructed in tropical semiring. Compared with directly run fstminimize.exe (i.e. in tropical semiring), is it better to switch to log semiring, run fstminimize.exe, and then switch back ?

Best, Zhijian

Compiling openfst-1.1 on cygwin

HenrikKinnemann - 11 Aug 2009 - 03:28

is there anybody who has compiled openfst-1.1 (latest version) on Cygwin successfully? Which "3rd-party" libs need to be available on Cygwin in advance?

Best regards, Henrik

PaulDixon - 11 Aug 2009 - 04:08

build 64bit openFST

ZhijianOu - 06 Aug 2009 - 10:19

I tried to run fstcompile.exe on a transducer with 23M states and 41M arcs, from AT&T FSM format text file. It terminates, saying that "Memory allocation failed". The 2G address space is not sufficent for compiling such a large transducer. Does the current openFST code support 64bit compile? Could you give me some instructions to build a 64bit openFST?

It is very appreciated that you could favor me with a reply. Thank you.

Zhijian

PaulDixon - 06 Aug 2009 - 23:10

ZhijianOu - 14 Aug 2009 - 00:03

It's very kind of you if you can add a 64bit profile to the Visual Studio solution.

Best regards, Zhijian

PaulDixon - 17 Aug 2009 - 08:47

ZhijianOu - 23 Aug 2009 - 22:53

valgrind complaints with Replace on openfst-1.1

GonzaloIglesias - 02 Aug 2009 - 13:36

    //Building 3 trivial fsts for fst replacement                                                                                                            
    VectorFst<StdArc> fst1,fst2,fst3;
    fst1.AddState();
    fst1.AddState();
    fst1.AddArc(0, StdArc(0, 123456789, StdArc::Weight::One(), 1));
    fst1.SetFinal(1,StdArc::Weight::One());
    fst1.SetStart(0);
    fst2.AddState();
    fst2.AddState();
    fst2.AddArc(0, StdArc(0, 1234567890, StdArc::Weight::One(), 1));
    fst2.SetFinal(1,StdArc::Weight::One());
    fst2.SetStart(0);
    fst3.AddState();
    fst3.AddState();
    fst3.AddState();
    fst3.SetFinal(2,StdArc::Weight::One());
    fst3.SetStart(0);
    fst3.AddArc(0,StdArc(0, 1000, StdArc::Weight::One(), 1));
    fst3.AddArc(1,StdArc(0, 2000, StdArc::Weight::One(), 2));
    vector< pair< StdArc::Label, const Fst<StdArc> * > > pairlabelfsts;
    pairlabelfsts.push_back(pair< StdArc::Label, const Fst<StdArc> * >(1000,&fst1) );
    pairlabelfsts.push_back(pair< StdArc::Label, const Fst<StdArc> * >(2000,&fst2) );
    pairlabelfsts.push_back(pair< StdArc::Label, const Fst<StdArc> * >(3000,&fst3) );
    VectorFst<StdArc> rulefst;
    StdArc::Label slabel=3000;

#ifndef USEOPENFSTBETA
    rulefst=ReplaceFst<StdArc>(pairlabelfsts,ReplaceFstOptions<StdArc>(slabel,false));
#else
    rulefst=ReplaceFst<StdArc>(pairlabelfsts,ReplaceFstOptions(slabel,false));
#endif
    RmEpsilon(&rulefst); //valgrind complains here
    rulefst.Write(some.fst); // and valgrind complains here too
    return 0;
}

(I may submit a link to a full example code)

Cheers!

CyrilAllauzen - 11 Aug 2009 - 10:09

Thanks for pointing this out! I'll look more deeply into this.

Best, Cyril

very slow delayed union on openfst 1.1

GonzaloIglesias - 02 Aug 2009 - 11:45

Hi,

Thanks for such a splendid tool as openfst! I'm a very happy user of the beta version for more than a year now.

I'm writing here because I have encountered a specific problem with the delayed union operation using openfst-1.1. library. Basically, I perform a delayed union of many fsts. Afterwards, I update by reinstancing to a VectorFst . I have isolated a particular case in which the version compiled with openfst-beta works things out very quickly (less than one minute), whilst it takes 40 minutes on openfst 1.1 to create the same fst. I have a small but full example including the necessary fsts to read from (~6MB) and perform union with. I don't understand this behaviour and it seems to me something could be wrong within version 1.1

Perhaps this is a known issue? May I post a link to a tar file containing the example? Please let me know how should I proceed.

Thanks in advance!

CyrilAllauzen - 11 Aug 2009 - 10:08

I've started to look into this and I think I found the reason for this inefficiency. We'll fix this for the next release.

Thanks a lot for your feedback!

Best, Cyril

CyrilAllauzen - 13 Aug 2009 - 16:11

UnionFst<A> *union = new UnionFst<A>(fsts[0], fsts[1]);
for (int i = 2; i < fsts.size(); ++i)
  Union(union, fsts[i]);

Cyril

Transforming a collection of strings

MadhuTherani - 29 Jul 2009 - 14:35

madhu

DoganCan - 30 Jul 2009 - 15:47

Say you have the string "x y z" in the set defined by the regex and the final string is "a b".

If you want the transduction "x y z" -> "a b a b a b", one possible solution is to create a simple transducer T in the form:

0 1 X a
1 2 <eps> b
2 0 <eps> <eps>
2

If you want the transduction "x y z" -> "a b" instead, then one possible solution is to create a transducer T in the form:

0 1 X <eps>
1 0 <eps> <eps>
1 2 <eps> a
2 3 <eps> b
3

You might achieve the same behaviour using sigma matcher in composition (At least I believe it is possible).

You might even try (for "x y z" -> "a b"):

• replace output labels of the regex with <eps> labels
• replace input labels of the final string with <eps> labels
• concat two transducers
• syncronize
• rmepsilon

Best, Dogan

AT&T FsmLib? vs openFST for exe ussage

ZhijianOu - 29 Jul 2009 - 11:20

1) How to easily get the command-line help in openFST's shell-level exe? You know, in FsmLib, an argument "-?" will print help information.

2) If exe is sufficient for my application, which one do you recommend to use? In particular, I have a special emphasis on the performance of acceptor optimization operations, e.g., determinize, minimize, remove-epsilon. As we see, minimizing a transducer is not supported at the command level.

Thanks in advance.

Best regards, ZhijianOu

PaulDixon - 29 Jul 2009 - 23:41

What semiring is the default in fstminimize, fstdeterminize ?

ZhijianOu - 29 Jul 2009 - 11:07

I'd like you to point out whether my following understandings are correct.

1) If the input is an acceptor, the implementation of fstminimize is first do weight pushing, and then do (unweighted) acceptor minimization.

2) If 1) is correct, then using different semirings will have different weight pushing results, and different minimization results.

3) In the description of fstminimize in openFST (or fsmminimize in fsmLib), there is no mention of the default semiring used. What semiring is the default?

4) For a deterministic transducer, P(I, x, y, F) contains only one path, using the notation in the paper - Mehryar Mohri, Fernando C. N. Pereira, and Michael Riley. Speech Recognition with Weighted Finite-State Transducers. In Handbook on Speech Processing and Speech Communication, Springer-Verlag, 2008.

5) fstdeterminize depends on the semiring ?

6) If we create binary fst from text file using fstcompile or fsmcompile, where to specify the semiring ?

It is very appreciated that you could favor me with a reply. Thank you.

Best regards, ZhijianOu

PaulDixon - 29 Jul 2009 - 20:42

For fsmcompile use the -s switch fsmcompile -t -s log test.txt > test.fst

DoganCan - 30 Jul 2009 - 16:22

1. Correct
2. Correct
3. No default semiring. Operation is performed in the semiring given by the arc type of the input fst.
4. Correct
5. Yes. Say there are distinct paths with the same labels in the input fst.
   • Tropical semiring: minimum of the path weights is assigned to the output path.
   • Log semiring: sum of the path weights is assigned to the output path.

ZhijianOu - 30 Jul 2009 - 22:04

The -s switch for fsmcompile is to give the states textual names.

The output from "fsmcompile -?" is
FSM Version 3.7
Copyright (C) 1998 AT&T Corp. All rights reserved.
Usage: fsmcompile [-opts] [fsm]
Options:
 -i symbols       input arc symbols
 -o symbols       output arc symbols
 -s symbols       state symbols
 -t               transducer
 -V file          input potentials file
 -F file          output FSM file
 -?               info/options

Continue with my question 3. 
In openFST, we can use --arc_type to specify the semiring. But we can run fstcompile without --arc_type, such as
fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst
The default --arc_type is "standard", which means tropical semiring. Am I right?

But in fsmLib, if we run fsmcompile as follow:
fsmcompile -t -i i.syms -o o.syms < T.txt > T.fst
It is not clear what semiring is used.

Thanks for your attention.

Best, ZhijianOu

PaulDixon - 30 Jul 2009 - 23:06

Yes, standard means tropical semiring (Explained in previous post "Why_is_TropicalWeight_considered_standard?")

problem with compiling openfst on Windows with Visual Studio 2008

ZhijianOu - 27 Jul 2009 - 10:49

As said in the openfstwin-1.1.zip's readme.txt, I open the solution file openfstwin.sln in Visual Studio 2008 and compile. But there are errors as follows:

1>Compiling... 1>fst.cc 1>d:\openfstwin-1.1\openfst-1.1\src\include\fst\unordered_set(19) : fatal error C1083: Cannot open include file: 'unordered_set': No such file or directory
1>properties.cc
1>d:\openfstwin-1.1\openfst-1.1\src\include\fst\unordered_map(19) : fatal error C1083: Cannot open include file: 'unordered_map': No such file or directory
1>Generating Code...
1>Build log was saved at "file://d:\openfstwin-1.1\openfstwin\openfstwinlib\Debug\BuildLog.htm"
1>openfstwinlib - 2 error(s), 0 warning(s)

It is very appreciated that you could favor me with a reply. Thank you.

Best regards, ZhijianOu

CyrilAllauzen - 27 Jul 2009 - 12:31

First, I'll make sure that you are using Visual Studio 2008 Service Pack 1 as mentioned here.

This looks like a missing TR1 issue. You might not have a working version of TR1 currently installed. As far as I know (I have never used VS2008), an implementation TR1 is included with SP1.

Best, Cyril

ZhijianOu - 29 Jul 2009 - 11:03

It works. Thank you. After installing VS2008 Service Pack1, I compiled openfstwin-1.1 successfully, though still with warnings, either warning C4396 or warning C4800. For example,

d:\openfstwin-1.1\openfst-1.1\src\include\fst/pair-weight.h(195) : warning C4396: 'fst::operator >>' : the inline specifier cannot be used when a friend declaration refers to a specialization of a function template
d:\openfstwin-1.1\openfst-1.1\src\include\fst/matcher.h(317) : warning C4800: 'uint64' : forcing value to bool 'true' or 'false' (performance warning)

Best regards, ZhijianOu

PaulDixon - 29 Jul 2009 - 20:40

If you think any of the warnings are bogus you can the warning number to the pragma statement at the top of config.h

HenrikKinnemann - 25 Aug 2009 - 05:02

my build of OpenFST-1.1 with Visual Studio 2008 SP1 was successful.

Now I would like to compile/link an example test application which is shipped together with OpenFST in file 'openfst-1.1\src\test\fst_test.cc'.

Visual Studio reports the following compile errors for fst_tes.cc:

1>------ Rebuild All started: Project: TestFst, Configuration: Debug Win32 ------ 1>Deleting intermediate and output files for project 'TestFst', configuration 'Debug|Win32' 1>Compiling... 1>stdafx.cpp 1>Compiling... 1>TestFst.cpp 1>d:\usr\local\include\fst\test-properties.h(24) : error C3083: 'tr1': the symbol to the left of a '::' must be a type 1>d:\usr\local\include\fst\test-properties.h(24) : error C2039: 'unordered_set' : is not a member of 'std' 1>d:\usr\local\include\fst\test-properties.h(24) : error C2873: 'unordered_set' : symbol cannot be used in a using-declaration 1>TestFst - 3 error(s), 1 warning(s)

What do I have to do in order to use 'unordered_set'?

Thanks in advance, Henrik

RolandZimbel - 01 Feb 2010 - 02:31

OpenFst? and AT&T FSM support UTF8 or Unicode Encoding?

AbbasMalik - 24 Jul 2009 - 15:23

Do OpenFst and AT&T FSM support UTF8 or Unicode Encoding?

Thank you in advance,

Best

CyrilAllauzen - 24 Jul 2009 - 16:45

This question was discussed previously in the forum: link.

Let me know if that answer your questions.

Best, Cyril

Pattern Matching using Mohri 1997 algorithm

PhilSours - 16 Jul 2009 - 16:58

I'm interested in pattern matching, i.e. finding occurrences of a set of strings within a text.

M. Mohri [1997] has described an algorithm to generate an efficient pattern search automaton based on failure functions in this paper:

Mohri, Mehryar. String-Matching with Automata. Nordic Journal of Computing, 4(2):217-231, Summer 1997. http://www.cs.nyu.edu/~mohri/postscript/njc.ps

This method has also been referred to by W. Skut [FSMNLP 2008].

Is there anyone who has submitted (or could submit) code implementing this algorithm that would be free for commercial use?

Thank you, Phil Sours

NewestUser - 18 Jul 2009 - 11:11

http://swtch.com/~rsc/regexp/regexp1.html

although it is very simple to implement, this algorithm generates transducers which are, in some cases, not terribly well-suited to further optimization or post-processing, especially epsilon removal. the following paper provides an overview of some more efficient ( but more complex ) alternatives which may be better suited to general or more complex inputs,

www.cs.nyu.edu/~mohri/postscript/glush.pdf

dunno if that is what you are looking for, and perhaps it's overkill, but depending on what you mean by 'match strings in a text' it seems like openfst itself might be overkill.

CyrilAllauzen - 20 Jul 2009 - 15:09

A version of this algorithm is implemented in the GRM library. The binaries are available for free for non-commercial use, no source code however.

Cyril

Pruning without changing state ID's.

DoganCan - 12 Jul 2009 - 13:32

I need to prune an fst while keeping the state ID's unchanged. I need this behaviour since I keep auxiliary information (i.e potentials) about the states of the input fst. Is there a convenient way of doing this?

Thanks, Dogan Can

NewestUser - 12 Jul 2009 - 21:08

DoganCan - 13 Jul 2009 - 16:55

CyrilAllauzen - 20 Jul 2009 - 15:19

Cyril

User-defined Flags

DoganCan - 12 Jul 2009 - 07:01

I noticed the following comment in the advanced usage section.

In a user-defined binary, the command line options processing will all also work if the user calls:

SetFlags(usage, &argc, &argv, true);

My problem is that when I add a new flag to a custom fst binary, I need to put its definition along with other flag definitions in <src/bin/main.cc> or in <src/lib/flags.cc> and rebuild the library, otherwise SetFlags method does not recognize it.

I have the generic OpenFst binary setup:

fstbinary.cc -- includes binary-main.h, calls SetFlags and Arc templated BinaryMain function

binary-main.h -- includes <fst/main.h>, declares a new flag using DECLARE_type(newflag) and defines BinaryMain function

Defining the new flag using DEFINE_type(newflag,default,help_message) in fstbinary.cc or binary-main.h allows me to use the newflag with its default value, however i cannot pass it from the command line.

Is it possible to to define and use new flags in a user-defined binary without modifying the library source code? If so, could you provide an example?

Many thanks, Dogan Can

PaulDixon - 13 Jul 2009 - 06:36

#include "test-main.h"

namespace fst 
{
        REGISTER_FST_MAIN(TestMain, StdArc);    
        REGISTER_FST_MAIN(TestMain, LogArc);
}  

DEFINE_double(myflag, 1234, "My Flag");
using fst::CallFstMain;
int main(int argc, char **argv) 
{
  string usage = "Test flags \n\n  Usage: ";
  usage += argv[0];
  usage += "  Flags: myflag\n";
  std::set_new_handler(FailedNewHandler);
  SetFlags(usage.c_str(), &argc, &argv, true);
  if (argc !=1)
  {
    ShowUsage();
    return 1;
  }
  return CallFstMain("TestMain", argc, argv, FLAGS_arc_type);
}

#ifndef TEST_MAIN_H__
#define TEST_MAIN_H__

#include <fst/main.h>
DECLARE_double(myflag);
DECLARE_string(arc_type);

namespace fst 
{

   template <class Arc>
   int TestMain(int argc, char **argv, istream&, const FstReadOptions&)
   {
     
      cerr << "myflag=" << FLAGS_myflag << endl;
        return 0;
   }
}  
#endif  

DoganCan - 13 Jul 2009 - 17:32

This is exactly what I tried before. Seems like there is a problem with my build settings. Thanks for your help.

DoganCan - 13 Jul 2009 - 19:21

After going through my build settings, I discovered that GCC_SYMBOLS_PRIVATE_EXTERN compiler flag was set to YES in default Release settings of XCode, and changing it to NO solved the problem. This flag sets symbol visibility and I suppose it makes flag definitions invisible to the flagregister.

auxiliary symbols and a speech recognition cascade

NewestUser - 10 Jul 2009 - 04:35

unfortunately, although I've now read through,

• "Speech Recognition with Weighted Finite State Transducers",
• "A Generalized Construction of Integrated Speech Recognition Transducers",
• "Generalized Optimization Algorithm for Speech Recognition Transducers", and
• "Integrated Context-Dependent Networks in Very Large Vocabulary Speech Recognition",

this one point still eludes me, and does not seem to be described or illustrated in any of these papers ( or any others that I was able to find ). Almost every other aspect of the transducer construction and cascade composition seems to be very clearly explained and usually illustrated with simple examples, but the trick with auxiliary phones and composition continues to elude me.

At present my approach consists of the following steps,

• construct G, a grammar transducer, which in my case happens to be determinizable. thus i perform no augmentation.
• construct L, the closure of a lexicon transducer derived from a pronunciation dictionary.
  • i automatically supplement this transducer with auxiliary symbols/phones as necessary, as described in the papers mentioned above
  • e.g., red r eh d #1, read r eh d #2, etc.
• construct C, an inverted, context-dependent, deterministic triphone transducer.
  • at present i am generating this transducer from a phoneme list which also includes the auxiliary symbols/phones so as to guarantee proper composition. i generate all possible logical triphones and rely on the composition process to weed out the superfluous combinations.
• perform the composition and optimization of the cascade ( i am not dealing with the H-level at present )

  •  min( det( *C* o det( *L* o *G* ) ) ) 

• replace all auxiliary triphones with the empty string, thus

   eh+d-#1 

  will be replaced with '-'

there are clearly a couple of problems with the last stage of my process. first, each auxiliary symbol at the context-independent level is being mapped to multiple different different auxiliary symbols at the context-dependent level. nevertheless the literature implies that this should not in fact be the case,

For further determinizations at the context-dependent phone level and distribution level, each auxiliary phone must be mapped to a distinct context-dependent phone. Thus, self-loops are added at each state of C mapping each auxiliary phone to a new auxiliary context-dependent phone. The augmented context-dependency transducer is denoted by C.

so i suppose that the mapping should be one-to-one, rather that one-to-many, which is what my current approach yields.

another clearly negative consequence of my current botched approach is that the final auxiliary-symbol removal step results in lost context wherever such auxiliary symbols appear. for example, the following transducer

0 1 SIL+r-eh red
1 2 r+eh-d -
2 3 eh+d-#2 -
3 4 d+#2-b -
4 5 #2+b-ah ball
5 6 b+ah-l -
...
...

defaults to,

0 1 SIL+r-eh red
1 2 r+eh-d -
2 3 - -
3 4 - -
4 5 - ball
5 6 b+ah-l -
...
...

which, although i can actually use it for recognition, is obviously wrong. so finally my question: are there any other papers which provide either diagrams of an augmented component context-dependent triphone transducer, or a more detailed description of the I(M) operation described in "Generalized Optimization...", For any transducer M, we also denote by I(M) the transducer augmented with extra transitions such that each new symbol on its input side is mapped to some new and distinct output symbol.

try as I might still don't quite get this. sorry if this seems a foolish question but im teaching this to myself and dont really know where else i might ask.

NewestUser - 10 Jul 2009 - 04:42

NewestUser - 11 Jul 2009 - 10:34

The most trivial, canonical example of a deterministic context-dependent triphone transducer.

The same example, inverted, and augmented with 2 auxiliary phones, #0, and #1

Assuming we have an example grammar transducer of the following form,

0 1 a testa
1 2 b -
2 3 #0 -
3 4 a testb
4 5 b -
5 6 #1 -
6

Then composition with the CD transducer yields,

where the auxiliary triphone symbols can now be safely replaced with epsilons, or short-pauses, or removed without any loss of information.

CyrilAllauzen - 14 Jul 2009 - 18:33

NewestUser - 14 Jul 2009 - 23:25

so, in contrast to the above examples where we have a list of monophones which includes auxiliary phones, 'a, b, #0, #1', which are all treated the same. and further in contrast to the self-loop approach, where we have two separate classes of symbols, monophones: 'a, b', and aux. symbols: '#0, #1' we instead of a selective combination depending on the structure of the lexicon transducer, e.g., monophones: 'a#0, b, a#1' which are all treated as normal monophones. this approach has an advantage in that there is no need to treat anything specially, and at the C-level ( assuming we've no need to worry about anything further down in the cascade ), there is no loss of information. instead of 'eps-a+b, #0c:, a-b+a' we get 'epse-a#0-b, a#0-b+a#1'. and instead of epsilon replacement, we have a simple symbol replacement.

this actually seems like a reasonable solution so long as, a. the degree of homophony is small, and b. there is no need to interact with lower levels in the cascade. if either a. or b. do not hold this alternative rapidly becomes intractable due to the increase in monophones and the increase in the size of the resulting C-level transducer.

CyrilAllauzen - 20 Jul 2009 - 15:16

However, I want to point out that the first approach does not really require to physically add the self-loops and can be achieved without increasing the size of C by using custom matchers? in composition.

Converting a "linearized transducer" into a true transducer FST

KennethRBeesley - 09 Jul 2009 - 12:17

a b c d e f

in which each even-numbered symbol (counting from 0) represents an Input symbol and each odd-numbered symbol represents an Output symbol. (This is the "linearized transducer".)

Question: Is there an easy way to turn this Acceptor (a kind of linearized transducer) into a real Transducer where each path like the one above is converted into a path of half the length, with these labels:

a:b c:d e:f

CyrilAllauzen - 20 Jul 2009 - 15:04

1) Use composition to turn a b c d e f into a:eps eps:b c:eps eps:d. This can easily be done using two two-state transducers T_1 and T_2 and computing T_1 o A o T_2. T_2 is the transducer erasing any symbol in odd position: for all a in the alphabet,

0 1 a eps
1 0 a a
1

T_1 is the inverse of the reverse of T_2

2) Apply Synchronize() followed by RmEpsilon().

Cyril

KennethRBeesley - 17 Aug 2010 - 12:27

A few small bugs

DoganCan - 08 Jul 2009 - 09:08

I noticed two small bugs/problems in the library and here are my fixes for them.

1. fstcompile does not give any error message when no input file is specified.

Solution: change line 00218 in <compile-main.h>

< if (!istrm) { 

> if (!*istrm) { 

2. <lexicographic-weight.h> defines pair weight type using "_<_" symbol between component weight types. However "<" symbol creates problems say when you want to register LexicographicArc for fst binaries since you can neither supply type1_<_type2 as an arc type nor create a dynamic shared object named type1_<_type2-arc.so.

Solution: change line 00075 in <lexicographic-weight.h>

< static const string type = W1::Type() + "_<_" + W2::Type(); 

> static const string type = W1::Type() + "_L_" + W2::Type(); 

Best, Dogan Can

CyrilAllauzen - 09 Jul 2009 - 11:00

Best, Cyril

OpenFST? vs. BOOST Graph Library for operations on language models

HenrikKinnemann - 18 Jun 2009 - 08:01

as a software developer of an OCR team I'm looking for a library which can

(a) represent certain kind of language models (e.g., OCR error correction rules, n-grams, word dictionaries, morphology and grammar rules for German language) in a unique way, for example, as weighted finite automata

and

(b) has some high-level operations already implemented to process the language models, e.g. functions like 'compose', 'minimize' and 'shortest-path-search'.

The BOOST Graph Library (http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/index.html) does also have weighted finite automata which could be used to represent language models and BOOST Graph offers lot's of functions on them.

My question: Where are the supposed differences between BOOST Graph and OpenFST in relation to my OCR application, and, what are the strenghts and weaknesses of both of them?

Best regards, Henrik

CyrilAllauzen - 19 Jun 2009 - 12:09

The Boost Graph Library focuses on directed and undirected graphs. As far as we know, it does not provide specific operations for weighted automata and transducers such as determinization, minimization or composition. You can probably use the BGL to represent language models, but you'll have to re-implement these algorithms. If you know otherwise, please point us to the relevant documents as there is no mention of automata-specific algorithms at the URL you provided.

The OpenFst library was especially designed for handling weighted automata and transducers. It provides a large selection of algorithms (including minimization and composition), some of them being implemented as on-the-fly (lazy) operations. The library also includes a general semiring framework. OpenFst provides some of the basic graph algorithms offered by the BGL such as generic visitors (depth-first, breadth-first, shortest-first, ...), generic shortest-path algorithms (Dijkstra, Bellman-Ford, ...), topological sort, strongly-connected components, ... However, OpenFst does not offer some other algorithms provided by BGL (spamming tree algorithms for instance).

The OpenFst library has been successful used by several natural language processing applications: speech recognition, speech synthesis, machine translation and OCR among others. It is for instance one of the core components of the speech recognition and speech synthesis efforts at Google. In that particular example, it is used among other things to represent (and combine) n-gram language models, word dictionaries and regular grammars.

To conclude, the Boost Graph library could provide a) but not b). The OpenFst library provides a) and b).

Best regards, Cyril

N-way Composition Support

GrahamNeubig - 25 May 2009 - 08:06

Are there any plans to support the three-way composition mentioned in the technical report "N-way composition of weighted finite-state transducers" (by Cyril Allauzen and Mehryar Mohri) in the near future? It would come in handy for one of my projects and I would be willing to help with the implementation if no-one is working on it, but if it's already being worked on I'll wait for the next release.

GregDhuse - 07 Jul 2010 - 12:27

Does anyone know of an existing implementation of the generalized n-way composition algorithm from that paper? I'm considering working on my own implementation if not.

Best regards, Greg

New behaviour of SetInputSymbols? /SetOutputSymbols ?

ChristopherKermorvant - 07 May 2009 - 08:04

I am working with the 1.1 version and it seems that there is a change in behavior of SetInputSymbols/SetOutputSymbols. As from version 1.1, it seems that these two functions make a deep copy of the SymbolTable given in argument. This is due to the addition of a copy constructor in symbol-table.h :

explicit SymbolTableImpl(const SymbolTableImpl& impl)
      : name_(impl.name_),
        available_key_(0),
        dense_key_limit_(0),
        check_sum_finalized_(false) {
    for (size_t i = 0; i < impl.symbols_.size(); ++i) {
      AddSymbol(impl.symbols_[i], impl.Find(impl.symbols_[i]));
    }
  } 

* if yes, i don't see the use of having a reference counting on a deep copy

* if yes, the following comment in symbol-table.h is not true anymore :

// SymbolTables are reference counted and can therefore be shared across
// multiple machines. For example a language model grammar G, with a
// SymbolTable for the words in the language model can share this symbol
// table with the lexical representation L o G.
 

CyrilAllauzen - 07 May 2009 - 11:14

This is inexact. SetInputSymbols and SetOutputSymbols still do a shallow copy of the SymbolTable in 1.1. They both call SymbolTable::Copy that in turn calls the copy constructor of SymbolTable:

  SymbolTable(const SymbolTable& table) : impl_(table.impl_) {
    impl_->IncrRefCount();
  }

Best, Cyril

Sat vocabulary building software

AllenSam - 05 May 2009 - 06:34

Off-topic post deleted.
MichaelRiley .

Mindtuning for the Encode/Determinize/Decode workaround

KennethRBeesley - 06 Apr 2009 - 17:22

Back on 14 August 2007, you wrote:

"The library currently only supports the determinization of functional transducers (if two successful paths have the same input label, they need to also have the same output label). The reason for that is that we use the weighted automata determinization algorithm viewing the output labels as weights in the string semiring ....

A workaround is to use Encode/Decode to view the transducer as an acceptor, considering the pair (ilabel, olabel) as one symbol.

1. Encode: EncodeMapper encoder(kEncodeLabels, ENCODE); Encode(fst, &encoder);

2. Determinize.

3. Decode: Decode(fst, encoder);

*** End of Quotation ***

I need a bit of mind-tuning.

Question: Is the Encode/Determinize/Decode workaround recommended ONLY when determinizing a NON-functional Fst? If so, what's the best way to determine if an Fst candidate for determization is functional or not?

Background: In my application, Fsts are created from arbitrarily complex regular expressions, and the resulting Fsts may be functional or non-functional. Without the workaround, statements like

$v = a | a:b ;

currently cause a crash when the result Fst is determinized (without the Encode/Decode workaround), because the Fst maps "a" to "a" and to "b"--i.e. in this case the Fst is not functional.

Thanks,

Ken

MichaelRiley - 08 Apr 2009 - 00:01

config.h

PaulDixon - 17 Mar 2009 - 08:14

After following the INSTALL instructions using the defaults settings and using the library in my own program as described in the README file. The compiler gives and error looking for config.h (included compat.h). Is config.h copied as part of the installation? Everything compiles fine if I add another include path to the location where the configure script was run from.

MichaelRiley - 21 Mar 2009 - 11:45

Minor bug in assignment operator

DanEgnor - 16 Mar 2009 - 04:29

Recommended fix: add an operator=(const MutableFst &fst) method that simply calls the existing (abstract virtual) assignment operator, via static_cast or something. I can submit a diff if this isn't clear.

CyrilAllauzen - 16 Mar 2009 - 11:17

Indeed, we found out about this bug and fixed it a while back. The latest release of the library (version 1.0) included that fix.

Best, Cyril

DanEgnor - 17 Mar 2009 - 22:00

When is it safe to RmEpsilon(), Determinize(), Minimize() When is it safe to automatically RmEpsilon? (), Determinize() and/or Minimize()

KennethRBeesley - 03 Mar 2009 - 16:59

$myfst  =   a* b+ ((c|d|e|f) - (m|n|d)){2} ((dog|cat|rat) & (elephant|dog|pig))? ;

After the regular expression is parsed, the interpreter walks the parse tree and makes multiple calls to OpenFst library functions--Closure, Compose, Concat, Difference, Intersect, etc--building many intermediate Fsts and combining them using the various operations until the final Fst is created and (in this case) bound to the variable $myfst. Obviously, all this processing gets done automatically, without human intervention. The user is interested only in the final result, $myfst, which then might get used in subsequent regular expressions.

Ideally, the final result would be automatically determinized and minimized.

I understand, with help from Cyril , that if an Fst is tested and found to be 1) acyclic, or 2) both (unweighted AND an Acceptor) then it can be safely Determinized and Minimized. (Corrections would be welcome.) So after each intermediate or final Fst is created by the Kleene interpreter, it might be sent to the following clean-up function

// first-draft pseudo-code
if ( the fst is acyclic || (the fst is unweighted &&  the fst is an acceptor) ) {
      RmEpsilon()
      Determinize()
      Minimize()
} else {
      // this is questionable, see below
      RmEpsilon()
}

However, I'm aware that this could still be problematic. In a response on this forum, Cyril stated

"Indeed, in some situations you cannot remove epsilons because it will lead to a space blow up. In that case, you might still want to optimize the machine with epsilons [i.e. without first invoking RmEpsilon] using determinization and minimization."

In another response, Cyril stated

"Indeed, union introduces epsilon-transitions and epsilon-transitions will slow down composition. Non-determinism will also slow down composition. So, I would recommend you first epsilon-remove and then determinize your fst. However, there is always a risk with determinization (it might blow up or even not terminate). Hence, if what I suggest does not work better, you should investigate using determinize only, or rmepsilon only or determinize followed by rmepsilon."

This puts in question the 'else' clause in the pseudo-code above, where RmEpsilon() is automatically called on Fsts that don't satisfy the requirements for safe determinization and minimization.

Question: Assuming my Kleene scenario, where regular expressions are being interpreted and many Fsts (intermediate and final) are being created automatically, when can RmEpsilon(), Determinize() and Minimize() be safely invoked automatically? I want the interpreter to do all the optimizations that are mathematically safe, but to attempt nothing more.

We can assume that the interpreter can interrogate various features of the candidate Fst (cyclic vs. acyclic, weighted vs. unweighted, acceptor vs. transducer, etc.). The interpreter also knows exactly which operation has just been performed to produce the Fst in question (Union, Concat, Closure, etc.).

Thanks,

Ken

CyrilAllauzen - 03 Mar 2009 - 17:27

To clarify, when talking about determinization:

• safe means a condition under which the algorithm will always terminate assuming you have enough memory and wait long enough;
• unsafe means the algorithm might not terminate ever.

Assuming this definition of safe/unsafe, determinization is safe for acyclic FSTs and for unweighted acceptors and rmepsilon and minimization are always safe.

However, safe does not guarantee that the algorithms will terminate on your machine because you have a finite amount of memory and don't want to wait more than x minutes.

The complexity of determinization in the safe case is in the worst case exponential in the size of the input machine, and quadratic in the size of the result (see DeterminizeDoc).

The complexity of epsilon removal is in the worst case quadratic in the size of the input (see RmEpsilonDoc).

There is no way you can ensure these algorithms will never blowup of memory. However, you can ensure that for most "reasonable" input they will behave "reasonnably".

Due to potentially large cost of these algorithms, it is always recommended you try to reduce the size of the input Fst before hand. This is why I would recommend first optimizing the machine with epsilon, applying epsilon-removal and then optimizing the machine without epsilons, Hence, the "safest" optimization function would be:

// first-draft pseudo-code
if ( the fst is acyclic || (the fst is unweighted &&  the fst is an acceptor) ) {
      Determinize()
      Minimize()
      RmEpsilon()
      Determinize()
      Minimize()
} else {
      // this is questionable, see below
      RmEpsilon()
}

Compiling openfst-1.0 on cygwin

PaulDixon - 26 Feb 2009 - 18:17

#include <ctime>

I should also have Visual Studio build instructions ready soon.

Paul

PaulDixon - 17 Mar 2009 - 19:37

# of states                     42980
# of arcs                       183468
# of final states               923
# of input/output epsilons      43867

# of states                     1180
# of arcs                       2424
# of final states               1
# of input/output epsilons      1

0 1  1 1 0 2  1 2 1 1  2 3 1 3  3 5 2 2  2 4 2 3  4 6 3 

int32 magic_number = 2125659606;
string fst_type = "vector";
string arc_type = "standard";
int32 file_version = 2; /* file format version */
int32 flags; /* bitfield: HAS_ISYMBOLS = 1, HAS_OSYMBOLS = 2 */
uint64 properties; /* bitfield, defined in fst/lib/properties.h */
int64 start; /* start state ID */
int64 num_states;
int64 num_arcs;

/* input symbol table, if flags & HAVE_ISYMBOLS */
int32 magic_number = 2125658996;
string name;
int64 next_available_key; /* Next available key (number) */
int64 size;
struct {
    string symbol;
    int64 key;
} symbols[size];

/* output symbol table, if flags & HAVE_OSYMBOLS - see above... */

/* states and arcs */
struct {
    float final_weight;
    int64 num_arcs;
    struct {
        int ilabel;
        int olabel;
        float weight;
        int next_state;
    } arcs[num_arcs];
} states[num_states];

patch -p1 -E < ../toautotools_openfst_20080422_20081227.diff
autoreconf --install --force
./configure --prefix=$HOME/busr CPPFLAGS="-I/opt/local/include" LDFLAGS="-L/opt/local/lib"
make
make check
make install

template <class Arc>
void Determinize(MutableFst<Arc> *fst) {
  *fst = DeterminizeFst<Arc>(*fst, 
                             DeterminizeFstOptions(CacheOptions(true, 0)));
}

for (StateIterator<StdFst> siter(fst); !siter.Done(); siter.Next()) {
     StateId state_id = siter.Value() ;
     ...
}

ComposeFst<Arc>(fst1, fst2, ComposeFstOptions<COMPOSE_FST1_PHI>())

ComposeFst<Arc>(fst1, fst2, ComposeFstOptions<COMPOSE_FST2_PHI>())