(r2) FstForumArchive2012 < Forum

Forum Web>FstForum>FstForumArchive2012 (revision 2) (raw view)~~EditAttach~~
---+ [[FST.WebHome][OpenFst]] Forum 2012 Archive

%TOC{depth="2"}%

---++ Use .fst Files 
---+++ Main.LadyFumi - 07 Dec 2012 - 09:52
<noautolink>
Hello,

I would like to know how open a FST File, for example, I will use fstcompose (I use openfst in shell) and I would like to open the output file but when I try, it's not readble.

Is anyone help me? 

Thank you
</noautolink>


---+++ Main.AlexZatv - 10 Dec 2012 - 09:46
<noautolink>
Try call fstinfo on your file, generated by fstcompose. If this tool will print something like 
==========
fst type                                          vector
arc type                                          standard
input symbol table                                none
...etc
====
your fst is OK. Of course it may be empty(0 states and 0 arcs), but binary format is good. 
Otherwise the file is broken by unknown reason.
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ FST and Rational Kernels - Computational Biology 
---+++ Main.AbielRoche - 05 Dec 2012 - 14:49
<noautolink>
Is there any real biological dataset that has been used either in FST or Rational kernel as an example to follow and understand better the application of Finite-State transducers in Computational Biology? THNX 
</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ openfst version with glog and gflags 
---+++ Main.JuanPino - 06 Nov 2012 - 12:06
<noautolink>
I am trying to use glog(http://code.google.com/p/google-glog/), gflags(http://code.google.com/p/gflags) and openfst but since openfst has its own glog and gflags implementation, there are #define and extern conflicts. Is there a version of openfst that links to external glog/gflags ?
</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ Conflicting #define in <fst/string.h> 
---+++ Main.AnthonyJBentley - 11 Oct 2012 - 19:58
<noautolink>
On line 144 of fst/string.h from openfst-1.3.2:

enum TokenType { SYMBOL = 1, BYTE = 2, UTF8 = 3 };

This causes a compile error when building hfst. One of the local hfst include files used in its build:

#define SYMBOL 268

And the error which is the obvious result:

 /usr/local/include/fst/string.h:42: error: expected identifier before numeric constant

Can this be fixed by, say, using a different variable name instead of SYMBOL, which is extremely likely to be defined elsewhere? Thanks.
</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ 3-way composition 
---+++ Main.YanzhangHe - 10 Oct 2012 - 15:34
<noautolink>
Hi all,

I am going to raise again a question people asked here two or three years ago, checking if there is any progress on it: did someone or some available toolkit actually implement the efficient 3-way composition of WFSTs, based on the idea of the this paper: 

Cyril Allauzen and Mehryar Mohri. N-way composition of weighted finite-state transducers. International Journal of Foundations of Computer Science, 20(4):613-627, 2009. 

It seems to me it has not been implemented in the current release of OpenFst yet (please correct me if I am wrong). Thanks!

-Yanzhang
</noautolink>


---+++ Main.PaulDixon - 11 Oct 2012 - 04:41
<noautolink>
fsm2.0 has an implmentation 3 way composition
http://tagh.de/tom/wp-content/uploads/fsm2.6-Sources.zip
</noautolink>

---+++ Main.YanzhangHe - 28 Nov 2012 - 12:29
<noautolink>
Thanks, Paul. Good that fsm2.0 has implemented it. But its current implementation seems restricted to the case where the leftmost and rightmost are both acceptors instead of the more general transducers. Unfortunately my current problem is in the latter case. But I found a workaround for my problem. Thanks anyway! 
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ composition yields empty file 
---+++ Main.FatimaTalib - 04 Oct 2012 - 18:42
<noautolink>
Hi! I have an FST and input (fst) and trying to compose them to get the output fst but the result of the composition is an empty FST? What could be the reason? 
</noautolink>


---+++ Main.PaulDixon - 05 Oct 2012 - 00:20
<noautolink>
Do the FST and the input fst have valid start and final states? Otherwise does the FST definitely accept the input?
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ How to get possible paths of a word from the pre-built fst 
---+++ Main.MohammadSadeghRasooli - 04 Oct 2012 - 03:14
<noautolink>
Hi! I built a fsa and fst and then compose them together to build a morphological analyzer. Now I want a command to know all possible paths in the fst which is acceptable in it.
 For example:
Thinking:
Thin + king
Think + ing

Is there any command or tool for that?
</noautolink>


---+++ Main.AlexZatv - 09 Nov 2012 - 03:41
<noautolink>
if the word "Thinking" is on the output label of resulting transducer, you can create simple acceptor:
0 1 Thinking
1
And compose your transducer with it. You will receive new transducer which will contain all paths from your transducer, with "Thinking" output.
</noautolink>

---+++ Main.AlexZatv - 09 Nov 2012 - 03:41
<noautolink>
if the word "Thinking" is on the output label of resulting transducer, you can create simple acceptor:
0 1 Thinking
1
And compose your transducer with it. You will receive new transducer which will contain all paths from your transducer, with "Thinking" output.
</noautolink>

---+++ Main.MohammadSadeghRasooli - 11 Feb 2013 - 18:23
<noautolink>
I see. My question is that suppose we have a fst and we want every possible sequence in that fst. Is there any command or tool to do that?

For example:
>> command myfst.fst 
think*ing
thinking
thin*king
</noautolink>

---+++ Main.MohammadSadeghRasooli - 11 Feb 2013 - 18:23
<noautolink>
I see. My question is that suppose we have a fst and we want every possible sequence in that fst. Is there any command or tool to do that?

For example:
>> command myfst.fst 
think*ing
thinking
thin*king
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Extract all possible outputs 
---+++ Main.JohnLocke - 03 Oct 2012 - 13:45
<noautolink>
Hi! Is there any efficient way to extract all possible outputs from an FST?
</noautolink>


---+++ Main.PaulDixon - 04 Oct 2012 - 02:02
<noautolink>
In general no. For an acyclic tranducers you can enumerate all the paths, but this would only be practical for fairly small machine. There is an implementation earlier in an earlier the post titled "Natural code for printing all strings accepted by an FST" 

There is an another implementation here: http://code.google.com/p/openfst-tools/
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ ArcSort, Compose and transducers without start states 
---+++ Main.MiikkaSilfverberg - 21 Sep 2012 - 06:32
<noautolink>
<verbatim>
#include <fst/fstlib.h>

using namespace fst;

int main(void)
{
  StdVectorFst foo;
  foo.AddState();
  foo.AddArc(0,StdArc(2,2,0.0,0));
  foo.AddArc(0,StdArc(0,0,0.0,0));

  StdVectorFst bar;
  bar.AddState();
  bar.AddArc(0,StdArc(1,1,0.0,0));
  bar.AddArc(0,StdArc(0,0,0.0,0));

  ArcSort(&foo, OLabelCompare<StdArc>());
  ArcSort(&bar, ILabelCompare<StdArc>());

  StdVectorFst baz;
  Compose(foo, bar, &baz);

}
</verbatim>

When run, this code gives an error message

<verbatim>
FATAL: ComposeFst: 1st argument cannot match on output labels and 2nd argument cannot match on input labels (sort?).
</verbatim>

The reason the arcs aren't sorted, even though ArcSort was called, is clearly that the transducers don't have start states. Shouldn't the result simply be empty in this case? 

Any way, I think the error message was quite confusing, since Arcsort was called before Compose. Perhaps ArcSort should give a warning if the argument doesn't have a start state, or sort the arcs even when there is no start state.
</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ Version 1.3.1 not available 
---+++ Main.ErikAxelson - 24 Aug 2012 - 05:22
<noautolink>
Can you make OpenFst version 1.3.1 available in the download page? The newest version 1.3.2 doesn't work correctly with our software and before making the changes we would like to use the older version.
</noautolink>


---+++ Main.PaulDixon - 24 Aug 2012 - 18:52
<noautolink>
You can find the links to older versions in the attachments section at the bottom of the download page

http://www.openfst.org/twiki/pub/FST/FstDownload/openfst-1.3.1.tar.gz
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Newbie question about determinization in the log semiring 
---+++ Main.MarcDymetman - 23 Aug 2012 - 12:22
<noautolink>
I am a newbie to openfst, and am trying to use fstdeterminize with the log semiring. 

I ran the following example, where lozange.fst is composed of two paths of log weight 0 and both with labels ab: 

<verbatim>
cat lozange.txt

0 1 a 0.0
0 2 a 0.0
1 3 b 0.0
2 3 b 0.0
3

cat isymbs.txt

<eps> 0
a 1
b 2
c 3
d 4

fstcompile --acceptor --arc_type=log --isymbols=isymbs.txt lozange.txt | fstdeterminize | fstprint --acceptor --isymbols=isymbs.txt

0	1	a	-0.693147182
1	2	b	0.000212192535
2
</verbatim>

While the weight on 0-1 is correctly -log(2), I do not understand the (non negligible) weight on 1-2, which should be 0. 

This example is the simplest one I could make that is showing the problem. In other attempts at determinization in the log semiring, the resulting DA appeared to give unbounded positive weight to strings whose weight should be upper-bounded by 0.

Am I misunderstanding, or is my use of fstdeterminize not the right way to proceed?

Thanks for any help.

- Marc
</noautolink>


---+++ Main.CyrilAllauzen - 28 Sep 2012 - 11:34
<noautolink>
To ensure convergence, determinization and other algorithms assume that weights that differ by less than a delta (by default 0.000976562) are equal. So in your example, 0.000212192535 is considered equal to 0. You can use the =--delta= flag to change the value of this parameter.

For instance:
<verbatim>
 fstcompile --acceptor --arc_type=log --isymbols=isymbs.txt lozange.txt | fstdeterminize --delta=0.00000001 | fstprint --acceptor --isymbols=isymbs.txt
0	1	a	-0.693147182
1	2	b
2
</verbatim>

Cyril

</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ PDT intersection 
---+++ Main.RolandSchwarz - 18 Aug 2012 - 12:03
<noautolink>
Hi All,

Is there an equivalent to fstintersect for PDTs, i.e. is it possible to intersect two PDTs such that the result is a PDT that contains all strings contained in both input PDTs and weighted by the (abstract) product of their respective weights?

Cheers
</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ C++11 compatibility 
---+++ Main.DoganCan - 15 Aug 2012 - 07:28
<noautolink>
Hi,

I just wanted to bring this issue up once again -- see the post by VicentAlabau. The interval-set implementation confuses gcc when c++11 support is enabled. Replacing include/fst/interval-set.h with the one attached to this page -- thanks to Vicent Alabau -- seems to solve the problem.

Cheers,
Dogan 
</noautolink>


---+++ Main.HoYinChan - 02 Nov 2013 - 16:06
<noautolink>
The above attached patch has been applied in Kaldi speech recognition toolkit for the support of c++11 compilation
</noautolink>

---+++ Main.HoYinChan - 02 Nov 2013 - 16:13
<noautolink>
see *** interval-set.h part  in  https://sourceforge.net/p/kaldi/code/HEAD/tree/trunk/tools/openfst.patch
</noautolink>

---+++ Main.RicoSennrich - 28 Nov 2013 - 11:19
<noautolink>
Just wanted to point out that the issue remains unfixed in version 1.3.4. Here's an alternative, more minimal patch:

<verbatim>
---
 include/fst/interval-set.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/include/fst/interval-set.h b/include/fst/interval-set.h
index c4362f2..57a71b5 100644
--- a/include/fst/interval-set.h
+++ b/include/fst/interval-set.h
@@ -218,7 +218,7 @@ void IntervalSet<T>::Intersect(const IntervalSet<T> &iset,
       interval.end = min(it1->end, it2->end);
       ointervals->push_back(interval);
       oset->count_ += interval.end - interval.begin;
-      if (it1->end < it2->end)
+      if ((it1->end) < it2->end)
         ++it1;
       else
         ++it2;
@@ -240,14 +240,14 @@ void IntervalSet<T>::Complement(T maxval, IntervalSet<T> *oset) const {
        it != intervals_.end();
        ++it) {
     interval.end = min(it->begin, maxval);
-    if (interval.begin < interval.end) {
+    if ((interval.begin) < interval.end) {
       ointervals->push_back(interval);
       oset->count_ += interval.end - interval.begin;
     }
     interval.begin = it->end;
   }
   interval.end = maxval;
-  if (interval.begin < interval.end) {
+  if ((interval.begin) < interval.end) {
     ointervals->push_back(interval);
     oset->count_ += interval.end - interval.begin;
   }
@@ -348,7 +348,7 @@ bool IntervalSet<T>::Contains(const IntervalSet<T> &iset) const {
   while (it1 != intervals_.end() && it2 != intervals->end()) {
     if (it1->end <= it2->begin) {  // no overlap - it1 first
       ++it1;
-    } else if (it2->begin < it1->begin || it2->end > it1->end) {  // no C
+    } else if ((it2->begin) < it1->begin || (it2->end) > it1->end) {  // no C
       return false;
     } else if (it2->end == it1->end) {
       ++it1;
-- 
</verbatim>
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ dynamic PowerArc 
---+++ Main.MarkusFreitag - 14 Aug 2012 - 10:25
<noautolink>
Hi,

I am using several features for my fst with:
static const int amountFeatures_ = 18;
fst::VectorFst<fst::PowerArc<fst::StdArc,amountFeatures_> > fst

amountFeatures_ has to be defined before compiling.

Is it possible to create a dynamic PowerArc with a value for amountFeatures_ which is set during runtime?

Thanks for helping,

Markus
</noautolink>


---+++ Main.PaulDixon - 17 Aug 2012 - 02:26
<noautolink>
You might be able to use or modify the  component weight that is part of Kyfd

https://github.com/neubig/kyfd/blob/master/src/include/kyfd/component-weight.h
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ "Wildcard" (?, @) arcs? 
---+++ Main.DavidNemeskey - 10 Aug 2012 - 05:49
<noautolink>
Hi,

is there a way to define a "wildcard" arc (=?= or =@= in =xfst=/=foma=), i.e. an arc that is chosen when the input does not match any of the other arcs' input labels? Also, a "SetSink" method would be welcome.
</noautolink>


---+++ Main.PaulDixon - 11 Aug 2012 - 02:47
<noautolink>
Maybe the  [[http://www.openfst.org/twiki/bin/view/FST/FstAdvancedUsage#Matchers Matchers]] do you want. The sigma matcher will match any label and the phi matcher will matche when no other matching labels are found.
</noautolink>


---+++ Main.DennisRitter - 02 Sep 2013 - 06:28
<noautolink>
I want to add to all states the possibility of additional input (additional to the arc-input-symbols that already leave that specific state), which then should transduce to an epsilon.
So if "ab" is transduced to -> "x", then "*a*b*" -> x also.

Is there a way to insert this type of "matcher" via the console/terminal? I have no clue at the moment, how to do it in C++.

My alternative would be to insert into the text-FST to every state something like that:
example from above:
<verbatim>
1 2 a <eps>
2 3 b x
</verbatim>
with inputs only a,b,c and "*a*b*" -> x (I omit the last *):
<verbatim>
1 1 b <eps>
1 1 c <eps>
1 2 a <eps>
2 2 a <eps>
2 2 c <eps>
2 3 b x
</verbatim>
</noautolink>

---+++ Main.PaulDixon - 04 Sep 2013 - 06:59
<noautolink>
It's not possible to switch the Matchers via the console just the composition filter. You could use fstproject --project_output | fstrmepsilon to remove the unwanted transitions.
</noautolink>

---+++ Main.DennisRitter - 12 Sep 2013 - 03:58
<noautolink>
Thank you for fast answering my question! I am late because I couldn't organize to get an email if something new occurs here (at http://www.openfst.org/twiki/bin/view/Main/WebNotify I am not allowed to change anything and I wonder why).

I think I made myself quite unclear. There are no unwanted transitions for me, but transitions, for which I am in search for a good way to implement them.

A more elaborate example: I want the sequence
<verbatim>Open the door</verbatim>
equally accepted as the following ones
<verbatim>
open the door please
please open the door
open oh my good the door
open the blasted door now
</verbatim>.

So I want much more acceptance from my FST, even if someone tends to swear.

I appreciate any further help, thanks in advance :).
</noautolink>

---+++ Main.PaulDixon - 13 Sep 2013 - 07:43
<noautolink>
Maybe this does what you want using failure transitions


https://gist.github.com/edobashira/6549668

The first line of the input text file is the sequence ("Open the door") and the following lines are string to match. It doesn't do any text case matching, so Open != open

</noautolink>

---+++ Main.PaulDixon - 13 Sep 2013 - 07:45
<noautolink>
Should be "Open" does not equal "open"

Exclamation mark was removed
</noautolink>

---+++ Main.DennisRitter - 16 Sep 2013 - 10:08
<noautolink>
Thank you for your perpetual support!
The code looks promising, but I do have some more basic problems I think:
I did compile the code into "main", but now I want to apply the code to an fst. When I do something like <verbatim>./main source.fst result.fst</verbatim> in the terminal then I don't get anything.
I didn't understand what you mean by "first line of the input text file". Thanks for the info with case matching.

</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Change version numbering when updating downloads 
---+++ Main.TommiPirinen - 29 Jul 2012 - 10:36
<noautolink>
If it is not too much trouble, could you always change version numbers when changing the contents of downloadable packages? This will tremendously help upkeeping the packages in mac and linux distributions such as macports and gentoo linux. For reference see e.g. http://trac.macports.org/ticket/34996 and http://trac.macports.org/wiki/PortfileRecipes#stealth-updates.
</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ composition in sparse semiring time and memory issues 
---+++ Main.JuanPino - 17 Jul 2012 - 12:22
<noautolink>
Hello,

I am trying to use composition in a sparse semiring to use sparse features in translation.
The problem is that sometimes those features are not sparse and many of them can fire at the same time, resulting in time and memory problems during composition.
<br>
Here (http://mi.eng.cam.ac.uk/~jmp84/share/google.tar.gz) is an example where I show timing results for composition of lattices in standard and in sparse
semiring at different stages of pruning. It shows that even for an input lattice pruned with 1-shortestpath the composition in sparse semiring takes much longer than the  composition in standard semiring. The example also runs another two compositions with a 50-shortestpath and a 100-shortestpath. While standard composition takes roughly the same time in all three cases, it increases up to 10 times when using the sparse semiring.
For the full input lattice, memory blows up.
<br>
To run the example, you need modify the Makefile to point to the correct include path for openfst and modify README.sh to point to the correct openfst install directory.
<br>
I would be grateful if anyone could have a look and share any suggestions or ideas to tackle this issue.
<br>
Thank you very much,
<br>
Juan
</noautolink>


---+++ Main.PaulDixon - 18 Jul 2012 - 07:28
<noautolink>
Not sure this helps. I profiled composition with a small
program and it seems that the TropicalSparseTupleWeight Times operation and constructor take the most time. 

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 55.27      0.21     0.21     4469     0.05     0.05  fst::TropicalSparseTupleWeight<float> fst::Times<float>(fst::TropicalSparseTupleWeight<float> const&, fst::TropicalSparseT
upleWeight<float> const&)
 28.95      0.32     0.11    66546     0.00     0.00  fst::SparseTupleWeight<fst::TropicalWeightTpl<float>, int>::SparseTupleWeight(fst::SparseTupleWeight<fst::TropicalWeightTp
l<float>, int> const&)
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Determinization on functional FSTs 
---+++ Main.SarkisParadjanian - 28 Jun 2012 - 03:52
<noautolink>
Hello there,
I, obviously naïvely, thought that a functional FST could always be made deterministic.

However, while fiddling with the toolchain, I ran into a weird (to me) behavior.

I have an initial FST that I compress as follows:
<verbatim>
fstdeterminize initial_fst.fst | fstminimize - fst1.fst
</verbatim>

Now, if I add epsilon-removal before determinization, like so:
<verbatim>
fstrmepsilon initial_fst.fst | fstdeterminize - | fstminimize - fst2.fst
</verbatim>
The minimization step triggers an error: <verbatim>FATAL: FST is not deterministic</verbatim>.

So, either there is a bug in my understanding (I thought a functional FST could always made deterministic), or there is a bug in determinization.
Could anyone comment on this?

<br>
<br>

I may also add a side question: is it necessary (and does it make sense) to add epsilon-removal before determinization?

<br>
<br>

Thanks!

Sarkis.


Below are the files for building my test FST:
The transducer per se:
<verbatim>
0
1 0 <eps> <eps>
1 0 sil <eps>
0 3 <eps> ick
3 9 I <eps>
9 10 k <eps>
10 1 <eps> <eps>
10 1 * <eps>
0 11 <eps> oak
11 17 o <eps>
17 18 k <eps>
18 1 <eps> <eps>
18 1 * <eps>
0 19 <eps> o
19 1 o <eps>
</verbatim>

The input vocabulary:
<verbatim>
<eps> 0
sil 1
i 2
I 3
k 4
o 5
u 6
* 7
</verbatim>

The output vocabulary:
<verbatim>
<eps> 0
o 1
ee 2
ick 3
oak 4
</verbatim>

</noautolink>


---+++ Main.DoganCan - 03 Jul 2012 - 02:29
<noautolink>
This is indeed curious. It seems like there is a bug in the determinization algorithm. The input is unweighted and functional, hence the determinization operation runs without complaining as it should. 

However, if we apply epsilon-removal prior to determinization, the result is non-deterministic.

<verbatim>
fstrmepsilon input.fst | fstdeterminize > rmeps-det.fst       <== non-deterministic
fstminimize rmeps-det.fst > rmeps-det-min.fst
FATAL: FST is not deterministic
</verbatim>

Notice the two arcs coming out of state 3 with the label =&lt;eps&gt;:o=.

%ATTACHURL%/rmeps-det.jpg

If we first determinize the input and then apply these operations, then it is fine.

<verbatim>
fstdeterminize input.fst | fstrmepsilon | fstdeterminize > det-rmeps-det.fst       <== deterministic
fstminimize det-rmeps-det.fst > det-rmeps-det-min.fst
</verbatim>

Cheers,
Dogan
</noautolink>

---+++ Main.CyrilAllauzen - 09 Jul 2012 - 16:03
<noautolink>
This is the expected behaviour on such machine.

The issue come from the handling of epsilons. On one hand input epsilons are treated as regular symbols by determinization. But on the other hand, input-epsilon transitions ("subsequential" transitions) are created to materialize final outputs when determinizing a transducer.

State 3 in the machine above should be final with a final output of "o". This is done by creating a transition "<eps>:o" to a new final state 6. This transition then conflicts with the existing epsilon transition from 3 to 1.

The solution to guarantee that the result of determinizing a transducer is always to deterministic is to use a symbol that does not appear anywhere in the original symbol as input label of these "subsequential" transitions. On the command line, the =--subsequential_label= flag can be used to specify that symbol (the default is 0, i.e. epsilon).

Best,
Cyril
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Issues with using fstdraw on sample FST 
---+++ Main.JuliusGoth - 23 Jun 2012 - 07:48
<noautolink>
I was running fstdraw just to try out a sample FST.  GraphViz doesn't seem to like this produced .dot file.  Am I doing something wrong?

<verbatim>
digraph FST {
rankdir = LR;
size = "8.5,11";
label = "";
center = 1;
orientation = Landscape;
ranksep = "0.4";
nodesep = "0.25";
0 [label = "0", shape = circle, style = bold, fontsize = 14]
	0 -> 1 [label = "This:This", fontsize = 14];
1 [label = "1", shape = circle, style = solid, fontsize = 14]
	1 -> 2 [label = "cat:cat", fontsize = 14];
2 [label = "2", shape = circle, style = solid, fontsize = 14]
	2 -> 3 [label = "is:is", fontsize = 14];
3 [label = "3", shape = circle, style = solid, fontsize = 14]
	3 -> 4 [label = "purring:purring", fontsize = 14];
4 [label = "4", shape = doublecircle, style = solid, fontsize = 14]
}
</verbatim>
</noautolink>


---+++ Main.JuliusGoth - 23 Jun 2012 - 07:52
<noautolink>
FYI: by "not liking this file", what I mean to say is that GraphViz opens the file but no graph appears in the space.
</noautolink>

---+++ Main.DoganCan - 03 Jul 2012 - 01:38
<noautolink>
Hey Julius,

Try using the portrait mode.

<verbatim>
fstdraw --portrait sample.fst > sample.dot
</verbatim>

Cheers, Dogan
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ how to extract input and output symbols from fst file? 
---+++ Main.AlexZatv - 20 Jun 2012 - 12:46
<noautolink>
Hello! With "fstsymbols", I can integrate input and output symbols into .fst-file, but I don't find how to do the opposite: extract symbols from .fst-file. Of course I can make my own program to do it, but may be there is an easy way? Thank you!
</noautolink>


---+++ Main.DoganCan - 03 Jul 2012 - 01:34
<noautolink>
Hey Alex,

You can use fstprint to dump fst-internal symbol lists to files.

<verbatim>
fstprint --save_isymbols=isymbols.txt --save_osymbols=osymbols.txt &> /dev/null
</verbatim>

Cheers, Dogan
</noautolink>

---+++ Main.AlexZatv - 06 Jul 2012 - 02:40
<noautolink>
Thank you! It will solve my problem.
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ how to extract input and output symbols from fst file? 
---+++ Main.AlexZatv - 20 Jun 2012 - 12:46
<noautolink>
Hello! With "fstsymbols", I can integrate input and output symbols into .fst-file, but I don't find how to do the opposite: extract symbols from .fst-file. Of course I can make my own program to do it, but may be there is an easy way? Thank you!
</noautolink>


---+++ Main.AlexZatv - 20 Jun 2012 - 12:46
<noautolink>
Sorry for duplication:(
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ fstinfo on models created with opengrm 
---+++ Main.JohnSalatas - 15 Jun 2012 - 11:26
<noautolink>
Hi!

as part of my google summer of code project, I'm currently evaluating opengrm library for language modeling. I have generated a fst model as explained in my blog post http://jsalatas.ictpro.gr/using-opengrm-ngram-library-for-the-encoding-of-joint-multigram-language-models-as-wfst/ but trying to get info using fstinfo command I get the following errors

# fstinfo cmudict.fst 
ERROR: Verify: Fst weight of arc at position 0 of state 1376 is invalid
FATAL: FstInfo: Verify: FST not well-formed.
# 

is there something I'm missing here? I'm using openFST 1.3.2 and openGRM NGram 1.0.3 on opensuse 12.1x64 (gcc 4.6.2).

Thank you in advance for your time.

John Salatas


</noautolink>


---+++ Main.JohnSalatas - 15 Jun 2012 - 11:27
<noautolink>
Forgot to mention that ngraminfo command produces normal output (ie no errors)
</noautolink>

---+++ Main.AlexZatv - 20 Jun 2012 - 12:42
<noautolink>
fstverify on that file?
</noautolink>

---+++ Main.JohnSalatas - 24 Jun 2012 - 18:53
<noautolink>
Actually this is a verification error.

I did some further investigation on the issue and concluded that it there are cases in which a smoothing method (in my case kneser_ney) produces an arc <eps>:<eps> with a weight equal to zero, and thus the condition at line 85 of verify.h 

... if (!arc.weight.Member() || arc.weight == Weight::Zero())...

evaluates to true 
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ k-shortest path on PDT? 
---+++ Main.KeWu - 05 Jun 2012 - 18:47
<noautolink>
It appears the PDT version of ShortestPath does not support k-shortest path as the FST version. Is this an inherent limitation of the algorithm or is it just not implemented?
</noautolink>


---+++ Main.PaulDixon - 07 Jun 2012 - 16:07
<noautolink>
An alternate method to extract the k-best is to run pdtexpand followed by the standard fst shortestpath algorithm.
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Cannot link openfst in Ubuntu (3.0.0-19-server #33-Ubuntu, x86_64) with gcc 4.6.1 
---+++ Main.AngelM - 04 May 2012 - 11:03
<noautolink>
Hi,
Sorry if I just made some silly mistake, but I cannot link even the simplest program to libfst. Installation seems to work and binaries are created, even "make check"  tests pass.
I get the following errors:
<verbatim>
/tmp/cckzXjvg.o: In function `fst::CompatProperties(unsigned long, unsigned long)':
TestOpenFst.cpp:(.text._ZN3fst16CompatPropertiesEmm[fst::CompatProperties(unsigned long, unsigned long)]+0xda): undefined reference to `fst::PropertyNames'
/tmp/cckzXjvg.o: In function `fst::FloatWeightTpl<float>::GetPrecisionString()':
TestOpenFst.cpp:(.text._ZN3fst14FloatWeightTplIfE18GetPrecisionStringEv[fst::FloatWeightTpl<float>::GetPrecisionString()]+0x6b): undefined reference to `fst::Int64ToStr(long, std::basic_string<char, std::char_traits<char>, std::allocator<char> >*)'
/tmp/cckzXjvg.o: In function `fst::ImplToMutableFst<fst::VectorFstImpl<fst::ArcTpl<fst::TropicalWeightTpl<float> > >, fst::MutableFst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > >::operator=(fst::Fst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > const&)':
TestOpenFst.cpp:(.text._ZN3fst16ImplToMutableFstINS_13VectorFstImplINS_6ArcTplINS_17TropicalWeightTplIfEEEEEENS_10MutableFstIS5_EEEaSERKNS_3FstIS5_EE[fst::ImplToMutableFst<fst::VectorFstImpl<fst::ArcTpl<fst::TropicalWeightTpl<float> > >, fst::MutableFst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > >::operator=(fst::Fst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > const&)]+0x1c): undefined reference to `FLAGS_fst_error_fatal'
/tmp/cckzXjvg.o: In function `fst::ImplToExpandedFst<fst::VectorFstImpl<fst::ArcTpl<fst::TropicalWeightTpl<float> > >, fst::MutableFst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > >::operator=(fst::Fst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > const&)':
TestOpenFst.cpp:(.text._ZN3fst17ImplToExpandedFstINS_13VectorFstImplINS_6ArcTplINS_17TropicalWeightTplIfEEEEEENS_10MutableFstIS5_EEEaSERKNS_3FstIS5_EE[fst::ImplToExpandedFst<fst::VectorFstImpl<fst::ArcTpl<fst::TropicalWeightTpl<float> > >, fst::MutableFst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > >::operator=(fst::Fst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > const&)]+0x1c): undefined reference to `FLAGS_fst_error_fatal'
/tmp/cckzXjvg.o: In function `fst::ImplToFst<fst::VectorFstImpl<fst::ArcTpl<fst::TropicalWeightTpl<float> > >, fst::MutableFst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > >::operator=(fst::Fst<fst::ArcTpl<fst::TropicalWeightTpl<float> > > const&)':
</verbatim>
(...and goes on like this...)
The line I am using to compile is:
<verbatim>
g++ -I/usr/local/include/ -L/usr/local/lib/ -lfst TestOpenFst.cpp
</verbatim>
And the minimal program:
<verbatim>
#include <fst/fstlib.h>
using namespace fst;
int main(int argc, char *argv[]) {
  StdVectorFst* fst = new StdVectorFst();
  delete fst;
}
</verbatim>

Any help would be very appreciated...
</noautolink>


---+++ Main.PaulDixon - 05 May 2012 - 06:06
<noautolink>
How about if change the order of the options to


 g++ TestOpenFst.cpp -I/usr/local/include/ -L/usr/local/lib/ -lfst -ldl -o test

</noautolink>

---+++ Main.AngelM - 06 May 2012 - 14:34
<noautolink>
It did work! Thanks a lot
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ OpenFST 1.3 and Unicode 
---+++ Main.YoMa - 03 May 2012 - 08:34
<noautolink>
In the OpenFst - Release 1.3 news (http://www.openfst.org/twiki/bin/view/News/FstNews), it is written that "--with-icu configuration option no longer needed". Do that mean that OpenFSt? 1.3 can handle directly UTF8 characters without ICU library? 
</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ Adding arcs to a sorted fst 
---+++ Main.MichaElsner - 01 May 2012 - 11:00
<noautolink>
I am trying to build a vectorfst arc by arc while keeping it sorted (I need to check if an arc already exists before adding it). It seems like I should be able to do a binary search at each insert and add the new arc, but I can't find anything in the interface to let me do that. Is there anything?
</noautolink>


---+++ Main.DoganCan - 02 May 2012 - 00:12
<noautolink>
Hi Micha,

You can use a Sorted Matcher to query the arcs that match a particular input (or output) label. Check [[FST.FstAdvancedUsage#Matchers]] for more info and [[FST.FstQuickTour#FstMatcher]] for an example.

Cheers, Dogan
</noautolink>

---+++ Main.MichaElsner - 02 May 2012 - 13:57
<noautolink>
Yes, I know how to do that. I need to insert a new arc into the correct list position. If the matcher had an InsertBefore method, I'd be set... but it doesn't seem to.
</noautolink>

---+++ Main.DoganCan - 06 May 2012 - 04:11
<noautolink>
Hi Micha,

Aha, I see your problem. Unfortunately, I don't think the library has this functionality since it is an odd operation for the current implementation of arc lists. Arcs are kept in C++ vectors and insertion has linear complexity with vectors. It appears like the easy (but ugly) solution is to add a new method to the VectorFst Class which will do both the binary search (since matchers won't really help in finding the actual position) and the insertion operation.

Do you mind explaining a little bit why you need this functionality? Kaldi toolkit has a hash-table based arc-list implementation which might fit the bill if you are aiming for efficient search on a non-static fst.

Cheers, Dogan
</noautolink>

---+++ Main.AlexZatv - 11 May 2012 - 06:29
<noautolink>
VectorFst is rather simple class.I think you can easily borrow it's code,and add the InsertBefore function.
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ fstencode problem 
---+++ Main.DominicHowell - 30 Apr 2012 - 17:36
<noautolink>
Hi
I am using fstencode to both encode and decode my WFSTs (they have non-zero arc weights) to perform determinisation and minimisation. The fstencode in version 1.2.7 works fine with my FSTs but for some reason, the new update (1.3.1) seems to corrupt my FSTs so that when I run fstinfo I get the following:

ERROR: Verify: Fst error property is set
FATAL: FstInfo: Verify: FST not well-formed.

Any help would be much appreciated.

</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ Problem in shared JNI library.  Symbol not found:  _FLAGS_fst_align 
---+++ Main.KennethRBeesley - 20 Apr 2012 - 15:04
<noautolink>
Background:  After a year of inactivity, I'm reviving a programming language based on OpenFst.  The language itself is implemented in Java and it accesses the OpenFst library via JNI, the Java Native Interface.

It worked a year ago with openfst-1.1, and I'm upgrading to 1.3.1.  Obviously there have been some changes.

When the language is launched, the Java code that wraps the openfst library loads a shared JNI library called libkleeneopenfst.jnilib, which is a prebuilt "native" C++ library that links in the openfst library.

When loadLibrary() is called, I get the following exception:

Exception in thread "main" java.lang.UnsatisfiedLinkError: /Users/beesley/projects/Kleene2012/Kleene/src/java/libkleeneopenfst.jnilib:  Symbol not found: _FLAGS_fst_align   Referenced from: /Users/beesley/projects/Kleene2012/Kleene/src/java/libkleeneopenfst.jnilib   Expected in: flat namespace  in /Users/beesley/projects/Kleene2012/Kleene/src/java/libkleeneopenfst.jnilib

<verbatim>
	at java.lang.ClassLoader$NativeLibrary.load(Native Method)
	at java.lang.ClassLoader.loadLibrary0(ClassLoader.java:1827)
	at java.lang.ClassLoader.loadLibrary(ClassLoader.java:1742)
	at java.lang.Runtime.loadLibrary0(Runtime.java:823)
	at java.lang.System.loadLibrary(System.java:1045)
	at OpenFstLibraryWrapper.<clinit>(OpenFstLibraryWrapper.java:300)
	at InterpreterKleeneVisitor.<init>(InterpreterKleeneVisitor.java:102)
	at Kleene.<clinit>(Kleene.java:27)
</verbatim>

Question:  Any idea why this symbol _FLAGS_fst_align is not found, and how I can fix the problem?  My own source code doesn't use _FLAGS_fst_align or FLAGS_fst_align.  





</noautolink>


---+++ Main.KennethRBeesley - 22 Apr 2012 - 14:52
<noautolink>
More background to the problem above:  To implement the JNI bridge to OpenFst, following usual JNI practice, I write a C++ file (kleeneopenfst.cc) that contains the "native" (i.e. C++) functions actually called by the Java code.  These native functions in kleeneopenfst.cc in turn call functions in the OpenFst library.  This kleeneopenfst.cc has to #include certain include files from OpenFst and ICU4C, and is currently compiled thus on OS X:

<verbatim>
g++ -O2 -o kleeneopenfst.o -c \
-I/Users/beesley/projects/Kleene2012/Kleene/src/java/../../../tools/OpenFst/openfst-1.3.1/src/include  \
-I/System/Library/Frameworks/JavaVM.framework/Headers \
-I/Users/beesley/projects/Kleene2012/Kleene/src/java/../../../tools/ICU4C/icu/source/common  \
kleeneopenfst.cc
</verbatim>

This seems to compile cleanly, producing kleeneopenfst.o

Then this kleeneopenfst.o is made into a shared (dynamic) library, linking in OpenFst (on OS X, libfst.dylib) to create
libkleeneopenfst.jnilib, which is the "shared" library loaded by the Java code that wraps the OpenFst library.
Here is the call that creates libkleeneopenfst.jnilib:

<verbatim>
g++ -dynamiclib -flat_namespace -undefined suppress \
-Wl,-L/Users/beesley/projects/Kleene2012/Kleene/src/java/../../../tools/OpenFst/openfst-1.3.1/src/lib/.libs,\
-L/Users/beesley/projects/Kleene2012/Kleene/src/java/../../../tools/ICU4C/icu/source/lib \
-o libkleeneopenfst.jnilib \
kleeneopenfst.o \
-framework JavaVM
</verbatim>

This too seems to compile cleanly, producing libkleeneopenfst.jnilib

As per the usual JNI pattern, the Java class OpenFstLibraryWrapper, which contains Java
methods that call "native" functions in kleeneopenfst.cc, contains the following static block

static {
    System.loadLibrary("kleeneopenfst") ;
}

that causes Java to look for and load the shared library libkleeneopenfst.jnilib.  In OS X, it looks in the directories designated
in the environment variable DYLD_LIBRARY_PATH, which is set appropriately.   It appears that this all works, and the shared library
gets loaded.  

However, when the shared library is loaded, I get the exception as shown in the first message above, complaining that
the symbol _FLAGS_fst_align is not found.

Looking in the OpenFst C++ code (I'm definitely not a C++ programmer) I find that <fst/fst.h> has the line

DECLARE_bool(fst_align) ;

which apparently creates a symbol named FLAGS_fst_align, which is used in the struct FstWriteOptions (also in fst.h).
(Other symbols are defined similarly in the <fst/flags.h> file, which is included by compat.h, which is included by fst.h.

My kleeneopenfst.cc file includes this <fst/fst.h> file, but I still get the exception originally supported.

Any help figuring out this problem would be much appreciated.

Ken
</noautolink>

---+++ Main.PaulDixon - 24 Apr 2012 - 18:14
<noautolink>
The fst_align flags is quite new. One possibility is you're building against OpenFst 1.31 but when you run your application it is loading an older version of libfst.so. Perhaps you could try strace  and to see which version of libfst.so is loaded. You might have a 1.1 version of  OpenFst that is  loaded from /usr/local/lib/ 
</noautolink>

---+++ Main.KennethRBeesley - 24 Apr 2012 - 23:29
<noautolink>
Many thanks for the reply.  (Sigh)  I just found the problem, which turned out to be a simple typo in my Makefile.  All seems to be working now, with 1.3.1.
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Current usage of .FstType() and .ArcType() 
---+++ Main.KennethRBeesley - 19 Apr 2012 - 21:08
<noautolink>
Assume that I have a pointer fstp that points to a StdVectorFst (or to some other class of Fst).  Given fstp, how can I invoke the methods .FstType() and .ArcType() ?
</noautolink>


---+++ Main.PaulDixon - 20 Apr 2012 - 07:34
<noautolink>
I think FstType and ArcType are members of the script wrapper classes (or FstHeader). The below code creates an FstClass and calls the members or defines some global functions call the same underlying methods as the FstType and ArcType from the FstClass

<verbatim>
#include <fst/script/fst-class.h>
.
.
.
.
fst::script::FstClass fstc(pfst);
cout << fstc.FstType() << endl;
cout << fstc.ArcType() << endl;

template<class Arc>
const string& ArcType(const Fst<Arc>& fst) {
  return Arc::Type();
}

template<class Arc>
const string& FstType(const Fst<Arc>& fst) {
  return fst.Type();
}

//Call like this
ArcType(*pfst);
FstType(*pfst);

</verbatim>

</noautolink>

---+++ Main.KennethRBeesley - 20 Apr 2012 - 14:40
<noautolink>
Paul:  Many many thanks.  That seems to work, but I used
#include "fst/script/fst-class.h"
with double quotes.
</noautolink>

---+++ Main.KennethRBeesley - 05 May 2013 - 21:18
<noautolink>

</noautolink>

---+++ Main.KennethRBeesley - 05 May 2013 - 21:30
<noautolink>
Paul:  Your solution above worked in 1.3.2, but I've just moved to 1.3.3, and I'm again having some difficulty with FstClass and .ArcType().  Here's my code (from a JNI bridge to OpenFst).  The offending line 2474 is marked with a comment:

<verbatim>
JNIEXPORT jstring JNICALL
Java_OpenFstLibraryWrapper_getArcTypeNative
	(JNIEnv *env, jclass cls,
	 jlong fstPtr)
{
        // create fstp as a pointer to a VectorFst<StdArc>
	VectorFst<StdArc> * fstp = (VectorFst<StdArc> *)(uintptr_t) fstPtr ;

        // call FstClass constructor
	fst::script::FstClass fstc(fstp) ;      //   <--- this is the error line 2474, it worked in 1.3.2 but not in 1.3.3

	// error message 2013-05-05:
	// kleeneopenfst.cc:2474: error: no matching function for call to ‘fst::script::FstClass::FstClass(fst::VectorFst<fst::ArcTpl<fst::TropicalWeightTpl<float> > >*&)’

        // get a string representation of the ArcType
	string s = fstc.ArcType() ;

	return env->NewStringUTF(s.c_str()) ;
}
</verbatim>

Any idea what has changed?  I looked at http://www.openfst.org/twiki/bin/view/FST/FstAdvancedUsage#FstClass
but couldn't see anything obvious (obvious to a non-expert in C++).  Here's the error message in a bit more context

<verbatim>
#g++ -O2 -o kleeneopenfst.o -c -I/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/OpenFst/openfst-1.3.3/src/include -I/System/Library/Frameworks/JavaVM.framework/Headers -I/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/ICU4C/icu/source/common kleeneopenfst.cc
g++ -O2 -o kleeneopenfst.o -c -I/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/OpenFst/openfst-1.3.3/src/include -I/System/Library/Frameworks/JavaVM.framework/Headers -I/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/ICU4C/icu/source/common -I/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang /Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../cpp/org/kleene-lang/kleeneopenfst.cc
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../cpp/org/kleene-lang/kleeneopenfst.cc: In function ‘_jstring* Java_OpenFstLibraryWrapper_getShortFstInfoNative(JNIEnv*, _jclass*, jlong)’:
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../cpp/org/kleene-lang/kleeneopenfst.cc:2447: error: no matching function for call to ‘fst::script::FstClass::FstClass(fst::StdVectorFst*&)’
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/OpenFst/openfst-1.3.3/src/include/fst/script/fst-class.h:246: note: candidates are: fst::script::FstClass::FstClass(fst::script::FstClassImplBase*)
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/OpenFst/openfst-1.3.3/src/include/fst/script/fst-class.h:174: note:                 fst::script::FstClass::FstClass(const fst::script::FstClass&)
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/OpenFst/openfst-1.3.3/src/include/fst/script/fst-class.h:167: note:                 fst::script::FstClass::FstClass()
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../cpp/org/kleene-lang/kleeneopenfst.cc: In function ‘_jstring* Java_OpenFstLibraryWrapper_getArcTypeNative(JNIEnv*, _jclass*, jlong)’:
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../cpp/org/kleene-lang/kleeneopenfst.cc:2474: error: no matching function for call to ‘fst::script::FstClass::FstClass(fst::VectorFst<fst::ArcTpl<fst::TropicalWeightTpl<float> > >*&)’
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/OpenFst/openfst-1.3.3/src/include/fst/script/fst-class.h:246: note: candidates are: fst::script::FstClass::FstClass(fst::script::FstClassImplBase*)
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/OpenFst/openfst-1.3.3/src/include/fst/script/fst-class.h:174: note:                 fst::script::FstClass::FstClass(const fst::script::FstClass&)
/Users/beesley/projects/kleene-lang/kleene/src/main/java/org/kleene-lang/../../../../../../tools/OpenFst/openfst-1.3.3/src/include/fst/script/fst-class.h:167: note:                 fst::script::FstClass::FstClass()
</verbatim>

Any help would be much appreciated.
Ken
</noautolink>

---+++ Main.PaulDixon - 06 May 2013 - 02:57
<noautolink>
Hi Ken, 
The contructor signature in 1.3.3 takes a const references instead of pointer, deferencing the pointer should work:

    fst::script::FstClass fstc(*fstp);


</noautolink>

---+++ Main.KennethRBeesley - 06 May 2013 - 11:07
<noautolink>
That did it.  Thank you so much.  Ken
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ "State structure" of FST after look-ahead composition 
---+++ Main.AlexZatv - 17 Apr 2012 - 06:27
<noautolink>
Hello! I have an T1oT2 transducers. T1 have "state structure" -- I mean, for each state, all edges that enters to this state, have the same input label. In other words, for such transducer I can even write the input-labels on states, not on edges.

Hence, T1oT2 will also have the "state structure", if I use usual composition.
But, am I right, that using look-ahead composition algorithm (from OpenFst), this "state structure" will remain?
</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ FATAL: FastLogAcumulator::LogMinus: f1 >= f2 with f1 = 0 and f2 = 0 
---+++ Main.AlexZatv - 14 Apr 2012 - 11:20
<noautolink>
I have problem while trying to make look-ahead composition. It fails with message:

++ fstcompose curFst/HCL.fst curFst/GT.fst
FATAL: FastLogAcumulator::LogMinus: f1 >= f2 with f1 = 0 and f2 = 0


Some details:  
1. curFst/GT.fst is a language model in openFst format. If I make GT.fst with lmScale=1, wdAdd=0 ,  fstcompose work fine. If I'm trying to set some other values of lmScale or wdAdd (just multiply and add), it fails with this message.
2. curFst/HCL.fst is olabel-lookahead, and curFst/GT.fst is relabeled, as mentioned in Paul Dixon's post   http://www.edobashira.com/2010/08/openfst-12.html
3. OpenFst's version is 1.3.1
</noautolink>


---+++ Main.AlexZatv - 14 Apr 2012 - 11:24
<noautolink>
some lines was glued in my message. To make it clear, output of fstcompose was 
"FATAL: FastLogAcumulator::LogMinus: f1 >= f2 with f1 = 0 and f2 = 0 "
</noautolink>
%COMMENT{type="mythreadmode"}% 


---++ Compatibility issues with new C++0x (C++11) and gcc 4.6 
---+++ Main.VicentAlabau - 20 Feb 2012 - 06:05
<noautolink>
I am trying to compile a c++11 program that uses openfst but I obtain the following error:

/usr/include/fst/interval-set.h: In member function 'void fst::IntervalSet<T>::Intersect(const fst::IntervalSet<T>&, fst::IntervalSet<T>*) const':
/usr/include/fst/interval-set.h:221:16: error: parse error in template argument list
/usr/include/fst/interval-set.h: In member function 'void fst::IntervalSet<T>::Complement(T, fst::IntervalSet<T>*) const':
/usr/include/fst/interval-set.h:243:18: error: parse error in template argument list
/usr/include/fst/interval-set.h:250:16: error: parse error in template argument list
/usr/include/fst/interval-set.h: In member function 'bool fst::IntervalSet<T>::Contains(const fst::IntervalSet<T>&) const':
/usr/include/fst/interval-set.h:351:54: error: expected ')' before 'it1'

I seems that gcc gets confused with the member variables 'begin' and 'end' in 'struct Interval', probably because they interfere with the new c++11 feature  [[http://en.wikipedia.org/wiki/C%2B%2B11#Range-based_for-loop Range-based for-loop]].

The problem can be easily solved by renaming such variables for instance to 'begin_' and 'end_', respectively.

If it does not break compatibility with older code or libraries, would you mind considering to update your source code?

Thank you in advance.
</noautolink>


---+++ Main.VicentAlabau - 20 Feb 2012 - 06:24
<noautolink>
I have attached an updated interval-set.h. openfst compiles and passes the checks, though they seem not to make use of InvervalSet. I hope not to have introduced any bugs. I look forward for your opinion.
</noautolink>

---+++ Main.VicentAlabau - 20 Feb 2012 - 06:25
<noautolink>
By the way, you can obtain the error by configuring openfst like this:

./configure CXXFLAGS=-std=c++0x

Thanks
</noautolink>

---+++ Main.LauriLyly - 15 Dec 2012 - 18:55
<noautolink>
I noticed the same problem. In this specific file, you can fix those instances by modifying lines like:

 if (it1->end < it2->end) 
to
 if ((it1->end) < it2->end)

This avoids the compiler thinking you are using some kind of template notation.
</noautolink>

---+++ Main.LauriLyly - 15 Dec 2012 - 18:55
<noautolink>
I noticed the same problem. In this specific file, you can fix those instances by modifying lines like:

 if (it1->end < it2->end) 
to
 if ((it1->end) < it2->end)

This avoids the compiler thinking you are using some kind of template notation.
</noautolink>

---+++ Main.WaleedAmmar - 09 Mar 2013 - 14:51
<noautolink>
This is likely to be a compiler bug in gcc 4.6-4.7.2(current). Lauri's solution works fine. The llvm compiler does not give an error, by the way.

Could you please modify those lines in the next release?
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Cannot figure how to get reference to pass to SingleShortestPath 
---+++ Main.NitinMadnani - 19 Feb 2012 - 16:16
<noautolink>
I have the following code:

<verbatim>
...

StdVectorFst* m_transA2 = new StdVectorFst();
Map(m_transA, m_transA2, LogToStdMapper());

// .. some more processing with m_transA2

StdVectorFst* m_transA3 = new StdVectorFst();
vector<Weight> *distance;


SingleShortestPath(*m_transA2, m_transA3, distance)
...

</verbatim>

However, when trying to compile this code, I get an error that this signature does not match the defined SingleShortestPath signature. What am I doing wrong?

However, w
</noautolink>


---+++ Main.PaulDixon - 20 Feb 2012 - 02:16
<noautolink>

</noautolink>

---+++ Main.PaulDixon - 20 Feb 2012 - 02:17
<noautolink>
<verbatim>
typedef  StdArc::Weight Weight;
  StdVectorFst* m_transA2 = new StdVectorFst();  
  StdVectorFst* m_transA3 = new StdVectorFst();
  AnyArcFilter<StdArc> filter;
  vector<Weight> distance;
  AutoQueue<StdArc::StateId> Q(*m_transA2, &distance, filter);
  ShortestPathOptions<StdArc, AutoQueue<StdArc::StateId>, AnyArcFilter<StdArc> > opts(&Q, filter);
  SingleShortestPath(*m_transA2, m_transA3, &distance, opts);
  //This should do the same
  ShortestPath(*m_transA2, m_transA3);
</verbatim>
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Converting from Tropical Weight to Log Weight 
---+++ Main.NitinMadnani - 16 Feb 2012 - 18:33
<noautolink>
I am an OpenFST newbie and I am really confused. If I convert a standard FST to the log semiring using fstmap --map_type=to_log, shouldn't that also actually change the weights in the FST. Right now, it seems like all it does is change the arc type but keeps the actual weights the same. Does that mean I need to convert the weights myself?

Also, would using Map(ifst, &ofst, StdToLogMapper()) have the same behavior or would that actually do the weighty conversion?

Tnx!
</noautolink>


---+++ Main.PaulDixon - 17 Feb 2012 - 20:25
<noautolink>
Values  in the tropical (standard) and log semirings are the same, the difference is the Plus operator
</noautolink>

---+++ Main.NitinMadnani - 19 Feb 2012 - 15:21
<noautolink>
I think I understand now. I have to do the weight conversion myself.
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Thrax newbie question 
---+++ Main.PierreIsabelle - 16 Feb 2012 - 11:04
<noautolink>
I have started playing with the Thrax grammar compiler and I have a very simple question. 

Is there any ready made tool that I can use to transform a text file into a basic fsa?

  -- Pierre
</noautolink>


---+++ Main.PierreIsabelle - 16 Feb 2012 - 14:01
<noautolink>

</noautolink>

---+++ Main.PierreIsabelle - 16 Feb 2012 - 14:07
<noautolink>
Just in case the above request wasn't clear enough: what I mean by "basic fsa" there is an fsa that encodes the text simply as a sequence of characters. Such an fsa will then become the input to the tokenizing transducer I am developing.

  -- Pierre




</noautolink>

---+++ Main.AlexZatv - 22 Feb 2012 - 09:51
<noautolink>
it is very easy operation. In case if you need it, I have python script which can make such operation for any sequence of words, or for HTK MLF files (it make an fst-file for each sub-file in mlf). I can send it to you.
</noautolink>

---+++ Main.AlexZatv - 22 Feb 2012 - 09:51
<noautolink>
it is very easy operation. In case if you need it, I have python script which can make such operation for any sequence of words, or for HTK MLF files (it make an fst-file for each sub-file in mlf). I can send it to you.
</noautolink>

---+++ Main.CyrilAllauzen - 28 Feb 2012 - 20:45
<noautolink>
You can also use the =farcompilestrings= command-line tool in =extensions/far=. Use =./configure --enable-far= to compile. 
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ far weirdness strikes again 
---+++ Main.DoganCan - 13 Feb 2012 - 06:02
<noautolink>
Hi everyone,

I am having a problem similar to [[#FarWeirdness][this post]] with the latest release (1.2.10) on a 64-bit Ubuntu 11.10 machine. Here is what I get when I try to use the far binaries to read a far file created by another far binary:

<verbatim>
echo "0 1" | farcompilestrings | farinfo -
ERROR: Error reading FAR: -
ERROR: GenericRegister::GetEntry : -arc.so: cannot open shared object file: No such file or directory
FATAL: No operation found for "FarInfo" on arc type
</verbatim>

Has anyone come across this problem?

Cheers,

Dogan

</noautolink>




---+++ Main.DoganCan - 14 Feb 2012 - 23:38
<noautolink>
Never mind, I figured out the problem. It seems like far binaries do not work with the stdio streams.

Cheers, Dogan
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Minimizing an unweighted transducer is slow 
---+++ Main.ErikAxelson - 09 Feb 2012 - 09:08
<noautolink>
Hi all,

I'm using OpenFst for compilation of natural language morphologies. Minimization of big unweighted transducers (~ 100 000 states) seems to be about four times slower than with other freely available finite-state transducer libraries. I'm using StdVectorFst with weight values TropicalWeight::Zero() and TropicalWeight::One(), so i guess that weight handling shouldn't be an issue?

Minimization is carried out for an unweighted transducer t as follows:

<verbatim>
    RmEpsilon<StdArc>(t);
    EncodeMapper<StdArc> encode_mapper(kEncodeLabels,ENCODE);
    Encode(t, &encode_mapper);
    StdVectorFst * det = new StdVectorFst();
    Determinize<StdArc>(*t, det);
    Minimize<StdArc>(det);
    Decode(det, encode_mapper);
    return det;
</verbatim>

Is there something in the above code that could be optimized? I already tried (kEncodeLabels | kEncodeWeights) instead of (kEncodeLabels), but it didn't have any effect.

regards,
Erik
</noautolink>


---+++ Main.MichaelRiley - 10 Feb 2012 - 14:26
<noautolink>
The encode and decode steps are unnecessary if the input
is unweighted (i.e restricted to Zero() and One()). Also be sure you have latest version, since there was a suboptimal hash function for determinization in earlier versions.
the latest version
</noautolink>

---+++ Main.ErikAxelson - 13 Feb 2012 - 06:25
<noautolink>
It seems that my comment got for some reason under another topic, so here it is again:

I tried omitting the encode and decode steps, but it made the compilation just a couple of seconds faster, so it still takes about seven minutes to compile the whole morphology. I'm using the newest version of OpenFst, 1.2.10. Thanks for the tip, anyway. 

 - Erik
</noautolink>

---+++ Main.ErikAxelson - 20 Feb 2012 - 09:02
<noautolink>
Hi.

Could it be that OpenFst's minimization algorithm is not optimized well enough? Minimization used to be slow in SFST library as well, but now it is faster because of the changes made in SFST's code based on our benchmarking tests in the HFST project. 

If I have understood correctly, it requires some work to implement Hopcroft's algorithm so that its performance will actually be the theoretical O(n log (n)). Of course, it is also possible that we are not using the OpenFst functions right.

- Erik
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Using feature vector as input 
---+++ Main.DominicHowell - 13 Jan 2012 - 11:54
<noautolink>
Hi
Has anyone used this toolbox with feature vector inputs instead of symbols in the application of speech recognition?


</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ Segmentation Fault at initialization (Static Order Initialization Fiasco instance?) 
---+++ Main.AntoineRaux - 10 Jan 2012 - 21:17
<noautolink>
I have a program that links to libfst.so (openfst-1.2.10, under Ubuntu 11.10, gcc 4.6.1) and it dies at start up. Other programs such as the openfst command line tools work fine. Also the problem does not occur on a different machine... 

Starting up in a debugger shows that the crash happens in float_weight.h, specifically at the following line (which is the initialization of a static class member):
<verbatim>
template <class T>
const T FloatLimits<T>::kPosInfinity = numeric_limits<T>::infinity();
</verbatim>
I am now wondering if it could not be an issue with static order initialization (see e.g. http://yosefk.com/c++fqa/ctors.html#fqa-10.12), i.e. that the templated class numeric_limits<T> is not yet initialized when that line is called and thus the call to the static member function infinity() crashes. Does this make sense? This problem is intrinsically hard to reproduce since it depends on compiler optimization, runtime issues, ... Has anyone else encountered this? If so, how can that be fixed? If not, any idea what might be happening?

Thanks.

</noautolink>


---+++ Main.AntoineRaux - 11 Jan 2012 - 12:33
<noautolink>
Actually a better explanation of the static order initialization fiasco is at http://www.parashift.com/c++-faq-lite/ctors.html#faq-10.14
In my copy of float_weight.h, I (temporarily) replaced "numeric_limits<T>::infinity()" with "((T)1)/((T)0)" (and similarly "numeric_limits<T>::bad_number()" with "((T)0))/((T)0)"), thus removing the call to a static member function in kPosInfinity's initialization, and my program now works correctly, which seems to confirm my first impression about the cause of the segfault. Of course, this does not look like a good long term solution...
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Problem with PhiMatcher: "ComposeFst: 1st argument cannot match on output labels and 2nd argument cannot match on input labels (sort?)." 
---+++ Main.JuliusGoth - 08 Jan 2012 - 10:14
<noautolink>
I was able to figure out the answer to my previous question regarding matching on failure arcs.  Now, I'm at another stumbling block. I have a language model FST composed onto another FST, where I am trying to use Phi matchers to recursively search non-matched symbols from the 2nd FST. 

First, I rewrite the symbol id 0 I've allocated to "<phi>" in the textual representation of the FST to -2:

<verbatim>
vector<pair<LogArc::Label, LogArc::Label> >* ipairs;
vector<pair<LogArc::Label, LogArc::Label> >* opairs;
ipairs = new vector<pair<LogArc::Label, LogArc::Label> >;
opairs = new vector<pair<LogArc::Label, LogArc::Label> >;
pair<LogArc::Label,LogArc::Label> mypair(0,-2);
</verbatim>

Now I declare the matchers in the ComposeFst options object:

<verbatim>
opts.gc_limit = 0;
opts.matcher1 = new PM(*lm, MATCH_OUTPUT, -2);	
opts.matcher2 = new PM(*noise, MATCH_NONE, kNoLabel);
</verbatim>

Now, I try to compose the two FSTs:

<verbatim>
composition = new ComposeFst<LogArc>(*lm, *fst2, opts);
</verbatim>

This is where I get the error.  I stepped into the compose code and noticed that while I declared the matchers as MATCH_OUPUT/MATCH_NONE, the match_type variable is set to MATCH_NONE for both FSTs and thus failing to set a match_type.
</noautolink>


---+++ Main.JuliusGoth - 08 Jan 2012 - 10:16
<noautolink>
Pardon me, noise == fst2 in my previous example.  Sorry for the confusion.
</noautolink>

---+++ Main.PaulDixon - 08 Jan 2012 - 17:13
<noautolink>
Try sorting the fsts before composition

<verbatim>
ArcSort(lm, OLabelCompare<LogArc>());
ArcSort(fst2, ILabelCompare<LogArc>());
</verbatim>
</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ NumArcs(stateId) in a delayed FST without expanding 
---+++ Main.LexOr - 08 Jan 2012 - 06:26
<noautolink>
line1: ComposeFst<StdArc>  C( A, B ); <br>
line2: C.NumArcs( C.Start() );<br>

Why is C expanded in line2?<br>
How can I check whether C.Start() has no arcs without expanding C?<br>
In other words, how can I check that C.Start() is not connected to any other state without expanding C?<br>
Best Regards<br>
LexOr 
</noautolink>


---+++ Main.PaulDixon - 08 Jan 2012 - 16:40
<noautolink>
You have to expand C.Start() to count the arcs or even know if C.Start() has any arcs at all, see the background papers on composition, One expection where you could check if C.Start() is connected to any other states without expanding would be if A and/or B didn't have a valid start state in which case C wouldn't not have start state. You could check this by A.Start() == kNoStateId....

</noautolink>
%COMMENT{type="mythreadmode"}% 



---++ Can I use Rho/Phi matchers together with LookAheadMatcher?  
---+++ Main.LexOr - 05 Jan 2012 - 12:06
<noautolink>

</noautolink>

%COMMENT{type="mythreadmode"}% 



---++ Update on composition with failure transitions? 
---+++ Main.JuliusGoth - 04 Jan 2012 - 16:14
<noautolink>
Relating to the older posting from 21 Jul 2008:

"There is an undocumented support for failure transitions in composition. This feature is not documented and the handling of failure transitions will change significantly in the next version of the library. "

What is the current status of dealing with failure transitions?  I was interested in composing FSTs where the transitions in one FST do not always match with the LM FST.  I understand a PhiMatcher exists in the framework.  Is this still the optimal way of performing this operation?
</noautolink>






---++ Need an example for using LookAheadComposeFilter with LookAheadMatcher. 
---+++ Main.LexOr - 04 Jan 2012 - 09:59
<noautolink>
What is the problem with this: <br>
<verbatim>
....
VectorFst<StdArc> A, B;

typedef ArcLookAheadMatcher< SortedMatcher<StdVectorFst> > LAM;
typedef SequenceComposeFilter< LAM, LAM > SCF;
typedef LookAheadComposeFilter< SCF, LAM, LAM, MATCH_BOTH> LCF;

LAM* lam1 = new LAM(A, MATCH_OUTPUT);
LAM* lam2 = new LAM(B, MATCH_INPUT);

LCF* laf1 = new LCF( A, B, lam1, lam2, MATCH_BOTH ); //here is the compilation problem
...
</verbatim>
How do I use LookAheadComposeFilter? <br>
Thank You<br>
</noautolink>


---+++ Main.PaulDixon - 04 Jan 2012 - 17:47
<noautolink>
Try changing the last line to  LCF* laf1 = new LCF( A, B, lam1, lam2); 

But if you want to use the LookAheadComposeFilter for composition there are already definitions and conversion function in the library.

laf1 will take ownership of lam1,2 so there is no need to call delete on them.

</noautolink>

---+++ Main.LexOr - 05 Jan 2012 - 06:21
<noautolink>

</noautolink>

---+++ Main.LexOr - 05 Jan 2012 - 06:25
<noautolink>
Paul, Thank You. It is OK now. <br>
What conversion functions do you mean? <br>
Can I use Rho/Phi Matcher together with LookAheadMatcher? <br>

Regards, <br>
LexOr  
</noautolink>

---+++ Main.PaulDixon - 06 Jan 2012 - 05:33
<noautolink>
<verbatim>
StdFst* C = Convert(A, "arc_lookahead"); 
</verbatim>

Not sure if the arc_lookahead type needs B to be relabelled.
</noautolink>
%COMMENT{type="mythreadmode"}% 

Access control:
   * Set ALLOWTOPICCHANGE = Main.AllAuthUsersGroup
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
h	interval-set.h	r1	manage	11.1 K	2012-02-20 - 11:21	UnknownUser	Updated interval-set.h that supports C++11 under gcc 4.6
jpg	rmeps-det.jpg	r1	manage	66.6 K	2012-07-03 - 06:22	UnknownUser	Non-deterministic output of applying fstrmepsilon and fstdeterminize to a functional transducer
Topic revision: r2 - 2014-04-21 - CyrilAllauzen
Forum