HFST Performance Testing: Observations

Composition

for i in a b c d e; do  \
for j in '' a b c d e; do \
for k in '' a b c d e; do \
for l in '' a b c d e; do \
for m in '' a b c d e; do \
echo $i $j $k $l $m; \
done; done; done; done; done \
> 6480_words

for i in a b c d e f g h i j k l m n o p q r s t u v w x y z; do  \
for j in a b c d e f g h i j k l m n o p q r s t u v w x y z; do  \
for k in a b c d e f g h i j k l m n o p q r s t u v w x y z; do  \
for l in a b c d e f g h i j k l m n o p q r s t u v w x y z; do  \
for m in a b c d e f g h i j k l m n o p q r s t u v w x y z; do  \
echo $i $j $k $l $m;\
done; done; done; done; done \
> N_words

time cat 6480_words | ../hfst-strings2fst -e '<>' -p -S -j -o 6480_words.hfst

real    0m0.057s
user    0m0.056s
sys     0m0.008s

time cat 6480_words | ../hfst-strings2fst -w -e '<>' -p -S -j -o 6480_words.hwfst

real    0m0.050s
user    0m0.048s
sys     0m0.004s

time ../hfst-compose 6480_words.hfst 6480_words.hfst -o composed.hfst

time no epsilons epsilons
real 0m0.097s 0m0.243s
user 0m0.036s 0m0.112s
sys 0m0.060s 0m0.132s

time ../hfst-compose 6480_words.hwfst 6480_words.hwfst -o composed.hwfst

time no epsilons epsilons
real 0m0.016s 0m0.056s
user 0m0.012s 0m0.052s
sys 0m0.004s 0m0.008s

Inputs and results are in both cases non-minimal.

OMorFi

Below are compilation times for OMorFi. fst-compiler-utf8 is SFST version 1.3 compiler, hfst-calculate unweighted HFST compiler and hwfst-calculate weighted HFST compiler.

time fst-compiler-utf8 hfst-calculate hwfst-calculate
real 25m10.831s 25m15.849s 7m54.459s
user 25m8.830s 24m55.530s 7m52.230s
sys 0m1.890s 0m20.140s 0m2.180s

Results from SFST and unweighted HFST are equivalent. Unweighted and weighted HFST do not yield equivalent results, but input and output projections of the results are equivalent. This suggests that the results are functionally the same, but differ in their alignment.

The equivalence of input and output projections does not necessarily mean that each input produces the same output in weighted and unweighted results. Because the results are cyclic, it is impossible to check all possible input/output relations.

Subtracting unweighted and weighted results shows that the weighted result is a subset of the unweighted one. It seems that the unweighted result accepts more alignments for some input/output relations than the weighted one.

We can test this by subtracting the weighted result from the unweighted one and taking the input projection. Then we can test the weighted and unweighted results with these strings. It seems that the weighted result accepts only one alignment for each input/output relation but the unweighted one accepts several alignments. For example the input rht<53><34> produces in weighted result only one output:

<wb>  r  h t :<> :<> <verb>:<> <53>:<> <f>:<> <>:<~T> <pcpneg><34><c>

but in unweighted one three same outputs with different alignments:

<wb>  r  h t :<> :<> <verb>:<> <53>:<> <f>:<> <>:<~T> <pcpneg><34><c>
<wb>  r  h t :<> :<> <verb>:<> <53>:<> <>:<~T> <f>:<> <pcpneg><34><c>
<wb>  r  h t :<> :<> <verb>:<> <>:<~T> <53>:<> <f>:<> <pcpneg><34><c>

The reason for this is that implementations of composition differ in SFST and OpenFst. SFST implements a naive composition algorithm where labels with output epsilons (in the first transducer) and labels with input epsilons (in the second transducer) can appear in any order. In unweighted transducers this produces redundant paths but the result is still correct. However, in weighted transducers a naive composition will produce wrong results. That is why OpenFst's composition algorithm allows only one alignment. By default this is the alignment where labels with output epsilons (in the first transducer) come before labels with input epsilons (in the second transducer).

Pushing labels does not produce equivalent results. It is not possible to push labels in a minimal transducer. AN EXAMPLE why this is not possible.

Roark, Sproat: Computational Approaches to Morphology and Syntax, pages 14-15 Pereira, Riley: Finite-State Language Processing, pages 439-442 Mohri, Pereira, Riley: SPEECH RECOGNITION WITH WEIGHTED FINITE-STATE TRANSDUCERS, pages 13-14

Could OpenFst's algorithm be implemented in SFST? At least for testing purposes. How about filtering afterwards. If the naive composition is intersected with the following filter:

0
0 0 x x
0 0 x e
0 1 e x
1
1 1 e x
1 0 x x

This would clearly remove the redundant paths where input epsilons come before output epsilons. However, the filter does not know where these paths have originated; such paths that are present in one of the transducers before composition are also removed. If single epsilons (epsilons that occur only either in the input or output of a transition) in the argument transducers are substituted with an unused marker before composition and then substituted back to epsilons after composition and filtering? How much time does it take to do the filtering afterwards?

SMOR

phon.fst

SMOR files are encoded with ISO-8859. Because HFST does not support this encoding, files are converted to UTF-8. Original ISO files are moved to their own directory:

cat original-iso-8859-files/FOO.fst | iconv -f ISO-8859-1 -t UTF-8 > FOO.fst

First, phon.fst is compiled. phon.sfst and phon.hfst are equivalent, but phon.hwfst is not. Compiling of phon.fst takes about 3 seconds with all compilers.

Let's find out where hwfst-calculate goes wrong. Let's compare intermediate results from hfst-calculate and hwfst-calculate. All intermediate results are equivalent. The problem was in hfst-weighted2unweighted: in OpenFst the initial state number is not always zero as in SFST.

FIXED: hfst-fst2txt swaps numbers of initial state and state number zero if initial state is not number zero.

smor.fst

Next, smor.fst is compiled:

Compile times of smor (phon.fst not included) on hfst computer:

time fst-compiler (ISO-8859) fst-compiler-utf8 (UTF-8) hfst-calculate (UTF-8) hwfst-calculate (UTF-8)
real 107m33.037s 107m28.501s 108m9.322s 15m23.387s
user 107m28.220s 107m23.030s 108m2.310s 15m21.480s
sys 0m4.430s 0m4.940s 0m5.540s 0m1.770s

Compile times of smor (phon.fst not included) on hippu:

time fst-compiler (ISO-8859) fst-compiler-utf8 (UTF-8) hfst-calculate (UTF-8) hwfst-calculate (UTF-8)
real   192m20.061s 187m17.151s 29m51.434s
user   192m8.728s 187m6.549s 29m44.068s
sys   0m6.558s 0m6.485s 0m3.305s

smor.sfst and smor.hfst are equivalent, smor.hwfst is not. Let's check the equality of input and output projections. Number of epsilon transitions increases: determinization takes 300 GB of memory and more than a day to complete.

hfst-summarize smor.hfst
# of input/output epsilons      0
# of input epsilons             174646
# of output epsilons            390780

hfst-summarize smor.hwfst
# of input/output epsilons      0
# of input epsilons             173920
# of output epsilons            390780

Let's check the difference of smor.hfst and smor.hwfst: It seems that smor.hwfst is a subset of smor.hfst.

cat smor.hfst | hfst-unweighted2weighted > smor.hfst.hwfst
hfst-minus smor.hfst.hwfst smor.hwfst  # 862084 states, 2139005 arcs
hfst-minus smor.hwfst smor.hfst.hwfst  # empty

Let's try to limit the number of paths in smor.h(w)fst by intersecting it with a transducer accepting only paths not longer than 20 transitions.

hfst-intersect smor.h(w)fst max20.h(w)fst > smor.max20.h(w)fst
cat smor.max20.h(w)fst | hfst-project -p [input|output] > smor.max20.[input|output].h(w)fst 
cat smor.max20.[input|output].hfst | hfst-unweighted2weighted | hfst-compare smor.max20.[input|output].hwfst

Size of smor.max20.hfst is 320 MB.

A corpus of 700 words gives equivalent results.

NOTE: -g options are now removed from Makefiles of ofst/fst/lib and hfst-tools and -O3 options are added to Makefiles of ofst (subdirectories already had -O3 options) and hfst-tools. This can have some effect on the compiling times.

Callgrind

g++ -o testi.exe testi.C -g -pg
valgrind --tool=callgrind ./testi.exe
callgrind_annotate --inclusive=yes callgrind.out.<pid>
make -n test | head -10 | perl -pe "s/^(.*)$/echo TEST\: \'\1\'\; valgrind \1/; s/2\>1//g;" | sh >& LOG
cat LOG | egrep 'TEST\:|definitely|possibly'

Testing where the resources go:

valgrind --tool=callgrind hfst-calculate -i phonology.sfst -o phonology.sfsta >& LOG

First 10 replace rules in phonology.sfst:

91,393,080,369 (HFST::make_replace_in_context)
80,506,430,283 (HFST::operator!)
37,666,701,957 (HWFST::make_replace_in_context)
28,325,895,797 (HWFST::negate)

function argument processing
HFST::compose -
HWFST::compose arcs sorted
HFST::intersect arguments determinised
HWFST::intersect arguments epsilons removed, encoded, arcs sorted ( not determinised any more )
HFST::subtract complete alphabet, negation (arguments minimised) and intersection
HWFST::subtract arguments epsilons removed, encoded, arcs sorted second argument determinised

A transducer of 450,000 words:

program unweighted user time weighted user time
hfst-compose 0m2.350s 0m1.030s
hfst-intersect 0m1.870s 0m2.440s
hfst-subtract 0m2.010s 0m3.340s

A transducer of 450,000 wordpairs:

program unweighted user time weighted user time
hfst-compose 3m2.280s 2m52.990s
hfst-intersect 3m7.840s 3m15.530s
hfst-subtract 3m28.380s 3m23.390s

(It seems that composition takes most of the time in unweighted hfst. Epsilons are not filtered. Arcs are not sorted.)

Miscellaneous scripts

make-omorfi

/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i phonology.sfst -o phonology.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i inflection.sfst -o inflection.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i stemfill.sfst -o stemfill.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i stubify.sfst -o stubify.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i find-gradation.sfst -o find-gradation.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i plurale-tantum.sfst -o plurale-tantum.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i omorfi_1.sfst -o omorfi_1.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i omorfi_2.sfst -o omorfi_2.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i exceptions.sfst -o exceptions.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i compounds.sfst -o compounds.sfsta
/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i omorfi.sfst -o omorfi.sfsta
mv *.sfsta ./HFST-files/

make-omorfi-time

time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i phonology.sfst -o phonology.sfsta) 2>> phonology.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i inflection.sfst -o inflection.sfsta) 2>> inflection.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i stemfill.sfst -o stemfill.sfsta) 2>> stemfill.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i stubify.sfst -o stubify.sfsta) 2>> stubify.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i find-gradation.sfst -o find-gradation.sfsta) 2>> find-gradation.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i plurale-tantum.sfst -o plurale-tantum.sfsta) 2>> plurale-tantum.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i omorfi_1.sfst -o omorfi_1.sfsta) 2>> omorfi_1.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i omorfi_2.sfst -o omorfi_2.sfsta) 2>> omorfi_2.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i exceptions.sfst -o exceptions.sfsta) 2>> exceptions.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i compounds.sfst -o compounds.sfsta) 2>> compounds.LOG 
time (/home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i omorfi.sfst -o omorfi.sfsta) 2>> omorfi.LOG 
mv *.sfsta ./HFST-files/

make-omorfi-time-total

time ( /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i phonology.sfst -o phonology.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i inflection.sfst -o inflection.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i stemfill.sfst -o stemfill.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i stubify.sfst -o stubify.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i find-gradation.sfst -o find-gradation.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i plurale-tantum.sfst -o plurale-tantum.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i omorfi_1.sfst -o omorfi_1.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i omorfi_2.sfst -o omorfi_2.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i exceptions.sfst -o exceptions.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i compounds.sfst -o compounds.sfsta; /home/eaxelson/hfst/my-trunk/hfst-2.0/hfst-tools/src/HFST-calculate -i omorfi.sfst -o omorfi.sfsta;) 2>> LOG; mv *.sfsta ./HFST-files/

calculate the average from a logfile

# not in tabular format
for i in *.LOG; do echo $i": " | perl -pe 's/\n//g;' >> AVERAGES;   for j in real user sys; do   cat $i | grep $j | perl -pe 's/[^0-9]*([0-9]+m[0-9\.]+s).*/\1/g; s/m/*60 + /g; s/s//g;' | bc > TIMES; cat TIMES | perl -pe 's/\n/ +0/g;' > FOO; (cat FOO; echo -e "\n") | bc > SUM; cat SUM | perl -pe 's/^(.*)$/scale=2; \1\/10/g;' | bc | perl -pe 's/\n/ /g;' >> AVERAGES; done;   echo "" >> AVERAGES;  done;

# in seconds
for k in phonology inflection stemfill stubify find-gradation plurale-tantum omorfi_1 omorfi_2 exceptions compounds omorfi; do    echo $k | perl -pe 's/\n/: /g;' >> AVERAGES;     for i in $k.hfst.LOG $k.hfst.m.LOG $k.hwfst.LOG; do    for j in real user sys; do   cat $i | grep $j | perl -pe 's/[^0-9]*([0-9]+m[0-9\.]+s).*/\1/g; s/m/*60 + /g; s/s//g;' | bc > TIMES; cat TIMES | perl -pe 's/\n/ +0/g;' > FOO; (cat FOO; echo -e "\n") | bc > SUM; cat SUM | perl -pe 's/^(.*)$/scale=2; \1\/10/g;' | bc | perl -pe 's/\n/ /g;' >> AVERAGES; done;  done;  echo "" >> AVERAGES; done

# in minutes and seconds
for k in phonology inflection stemfill stubify find-gradation plurale-tantum omorfi_1 omorfi_2 exceptions compounds omorfi; do    echo $k | perl -pe 's/\n/: /g;' >> AVERAGES;     for i in $k.hfst.LOG $k.hfst.m.LOG $k.hwfst.LOG; do    for j in real user sys; do   cat $i | grep $j | perl -pe 's/[^0-9]*([0-9]+m[0-9\.]+s).*/\1/g; s/m/*60 + /g; s/s//g;' | bc > TIMES; cat TIMES | perl -pe 's/\n/ +0/g;' > FOO; (cat FOO; echo -e "\n") | bc > SUM; cat SUM | perl -pe 's/^(.*)$/scale=2; \1\/10/g;' | bc > AV;     cat AV | perl -pe 's/^(.*)$/\1 \/ 60/g;' | bc | perl -pe 's/\n/m/g;' >> AVERAGES;  cat AV | perl -pe 's/^(.*)$/\1 \% 60/g;' | bc | perl -pe 's/\n/s /g;' >> AVERAGES;          done;  done;  echo "" >> AVERAGES; done

cat AVERAGES_SEC | cut -d' ' -f 2 | perl -pe 's/\n/+0/g;' > TMP; echo "" >> TMP; cat TMP | bc

performance-tests

for i in 0 1 2 3 4 5 6 7 8 9; do   cat make-omorfi-time | perl -pe 's/HFST/hwfst/g; s/LOG/hwfst.LOG/g;'   ; done;
for i in 0 1 2 3 4 5 6 7 8 9; do   cat make-omorfi-time | perl -pe 's/HFST/hfst/g; s/\-i/-O -i/g; s/LOG/hfst.m.LOG/g;'   ; done;
for i in 0 1 2 3 4 5 6 7 8 9; do   cat make-omorfi-time | perl -pe 's/HFST/hfst/g; s/LOG/hfst.LOG/g;'   ; done;

Produce a non-minimal transducer from a list of words and draw it

echo "<>" | hwfst-calculate > words.hfst;
cat words.txt | while read line; do   echo $line | hwfst-calculate | hfst-disjunct -1 words.hfst > tmp.hfst; mv tmp.hfst words.hfst;    done;
cat words.hfst | hfst-remove-epsilons | hfst-fst2fst --format openfst | fstdraw > pic;
cat pic | perl -pe 's/orientation = Landscape\;\n//g; s/\"([a-z0-9]+):[a-z0-9]+\"/\"\1\"/g; s/(0 \[label = \"0\", shape =) doublecircle/\1 circle/g;' > TMP; mv TMP pic;
dot -Tps pic -o pic.ps;
gv pic.ps;

hfst-fst2txt comphyphen.sfsta | perl -pe 's/\t/ /g;' | cut -f1,3,4 -d' ' | perl -pe "s/^([^ ]+) ([^ ]+) ([^ ]+)$/\1 \2\3/g;" | sort -n | uniq -c | sort -nr | less

for i in phonology inflection stemfill stubify find-gradation plurale-tantum omorfi_1 omorfi_2 exceptions compounds omorfi; do echo $i ":"; hfst-summarize ./hfst-files/$i.sfsta | egrep '(of states)|(of arcs)|(cyclic)'  ; done


-- ErikAxelson - 2009-05-13
Topic revision: r72 - 2011-01-19 - ErikAxelson
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback