OpenFST初体验

  |   0 评论   |   0 浏览 
## 背景

OpenFst是一个加权有限状态转换器的构建、复合、优化和搜索的库。

这个为是由Google研究院和NYU Courant研究所开发。目标为一个综合的、可靠的、灵活的、高效的和可扩展的。(It is intended to be comprehensive, reliable, flexible, efficient, and to scale well。)

初体验

基础知识

WFST

有限加权状态转换机（Weighted Finite State Transducers, WFST）是有限自动机（Finite Automaton, FA）家族中的一员。

FA由（A, Q, E, I, F）五个元素组成，其中

  • Q为状态集合，表示图中的节点
  • A为Label集合，表示边上的符号
  • E为转移函数集合，两个状态节点和他们之间的边以及边上的label和weight构成了一次转移（transition）
  • I为初始状态，在图中使用较粗的圆圈表示，为搜索的起点
  • F为终止状态，在图中使用双环形圆圈表示，为搜索的终点。

如下图所示，

在这里插入图片描述

  • 初始状态为0，有且只有一个。
  • 终止状态为2，终止权重为3.5；终止状态可以有多个，任何一个有非无穷的终止权重的状态，都是终止状态。
  • 从0到1有一个弧，输入Label为a，输出Label为x，权重为0.5。
  • 此图中，字符串ac到xz的权重为6.5，即弧的权重 + 终止状态权重 = 0.5 + 2.5 + 3.5 = 6.5。

WFST的合并

在youtube视频《Lecture 9 Introduction to 5 Basic Operations for WFST Composition》，https://www.youtube.com/watch?v=DyY69sX7RGk中讲解的很详细。

图片.png

合并结果

图片.png

合并过程

图片.png

第一步，从(0a, 0b)出发，找到了(1a, 1b)

图片.png

第二步，从(1a, 1b)出发，找到了(0a, 1b), (2a, 1b), (3a, 1b)

图片.png

第三步，从(0a, 1b)出发，找到了(2a, 1b), (3a, 1b)

图片.png

第四步，从(2a, 1b)出发，找到了(3a, 1b)

图片.png

后面略，详见原文PPT

FA家族四个成员

参见FstSltTutorial教程，

图片.png

图片.png

图片.png

图片.png

工具小试

有了理论基础，来看一下工具的使用。

准备

创建三个文件，text.fst，isyms.txt 和 osyms.txt。

在openfst里面，text.fst中边的输入输出都用数字来代替，所以字典分别保存在isyms.txt和osyms.txt中。

cat >text.fst <<EOF
0 1 a x .5
0 1 b y 1.5
1 2 c z 2.5
2 3.5
EOF

cat >isyms.txt <<EOF
<eps> 0
a 1
b 2
c 3
EOF

cat >osyms.txt <<EOF
<eps> 0
x 1
y 2
z 3
EOF

将文本 fst 编译为 二进制文件

fstcompile --isymbols=isyms.txt --osymbols=osyms.txt text.fst binary.fst

将符号表排序

fstcompile --isymbols=isyms.txt --osymbols=osyms.txt --keep_isymbols --keep_osymbols text.fst binary.fst

访问fst

print，从binary生成text

fstprint --isymbols=isyms.txt --osymbols=osyms.txt binary.fst text.fst

draw

fstdraw --isymbols=isyms.txt --osymbols=osyms.txt binary.fst | dot -Tpdf > binary.pdf

其中dot在包graphviz，dot -Tpdf指输出为pdf格式文件。

查看fst文件信息

fstinfo binary.fst
fst type                                          vector
arc type                                          standard
input symbol table                                none
output symbol table                               none
# of states                                       3
# of arcs                                         3
initial state                                     0

fst compose

fst 的 weight 有两种运算: plux(x,y) 和 time(x,y)

# The FSTs must be sorted along the dimensions they will be joined.
# In fact, only one needs to be so sorted.
# This could have instead been done for "model.fst" when it was created. 
$ fstarcsort --sort_type=olabel input.fst input_sorted.fst
$ fstarcsort --sort_type=ilabel model.fst model_sorted.fst

# Creates the composed FST. 
$ fstcompose input_sorted.fst model_sorted.fst comp.fst

# Just keeps the output label 
$ fstproject --project_output comp.fst result.fst

# Do it all in a single command line. 
$ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst

工具复现上面的compose

isyms.txt

<eps> 0
a 1
b 2
c 3

2syms.txt

<eps> 0
m 1
n 2
o 3

osyms.txt

<eps> 0
x 1
y 2
z 3

a.txt

0	1	a	n	0.1
1	0	a	n	0.2
1	2	b	n	0.3
2	3	a	n	0.5
1	3	b	n	0.4
3	3	a	m	0.6
3	0.7

b.txt

0	1	n	y	0.1
1	1	n	x	0.2
1	2	m	y	0.3
2	3	m	y	0.5
1	3	m	y	0.4
2	3	n	x	0.5
3	0.6

编译：

fstcompile --isymbols=isyms.txt --osymbols=2syms.txt a.txt a.fst
fstcompile --isymbols=2syms.txt --osymbols=osyms.txt b.txt b.fst

画图：

fstdraw --isymbols=isyms.txt --osymbols=2syms.txt a.fst | dot -Tpdf > a.pdf
fstdraw --isymbols=2syms.txt --osymbols=osyms.txt b.fst | dot -Tpdf > b.pdf

a.pdf
图片.png

b.pdf

图片.png

合并

# 排序，本例中可略。
fstarcsort --sort_type=olabel a.fst a_sorted.fst
fstarcsort --sort_type=ilabel b.fst b_sorted.fst

# 合并
fstcompose a_sorted.fst b_sorted.fst comp.fst

# Just keeps the output label 
fstproject --project_output comp.fst result.fst

# Do it all in a single command line. 
$ fstarcsort --sort_type=ilabel model.fst | fstcompose input.fst - | fstproject --project_output result.fst

comp.fst
图片.png

result.fst
图片.png

不清楚fstproject是做啥的。

参考