Fsa algorithms

This tutorial describes algorithms supported by k2. Most of the algorithms support both CPU and CUDA. A few of them support only CPU, which is documented explicitly in the corresponding documentation.

Note

All algorithms support FsaVec. A few of them also support single FSAs.

invert

k2.invert() swaps the labels and aux_labels of a k2.Fsa.

The following is an example swapping the labels and aux_labels of an FSA.

Listing 1 Example code for k2.invert()

s = '''
0 1 2 10 0.1
1 2 -1 -1 0.2
2
'''
fsa = k2.Fsa.from_str(s, acceptor=False)
inverted_fsa = k2.invert(fsa)
fsa.draw('before_invert.svg', title='before invert')
inverted_fsa.draw('after_invert.svg', title='after invert')

Its outputs are given below:

When aux_labels is a ragged tensor, new arcs will be added after the invert.

The following code applies k2.invert() to an FSA with ragged tensors as aux_labels.

Listing 2 k2.invert() for FSAs with ragged tensors as aux_labels

s = '''
0 1 2 0.1
1 2 -1 0.2
2
'''
fsa = k2.Fsa.from_str(s)
fsa.aux_labels = k2.RaggedTensor('[ [10 20] [-1] ]')
inverted_fsa = k2.invert(fsa)
fsa.draw('before_invert_aux.svg',
         title='before invert with ragged tensors as aux_labels')
inverted_fsa.draw('after_invert_aux.svg', title='after invert')

after_invert_aux — Fig. 15 Example of `k2.invert()` for FSAs with ragged tensors as `aux_labels`.

Note

k2.invert() supports CUDA as well as CPU.
autograd is also supported.
Its input can be either a single FSA or a FsaVec.

arc_sort

k2.intersect() and k2.compose() require two arc-sorted inputs. You can use k2.arc_sort() to convert an unsorted FSA/FsaVec into a sorted FSA/FsaVec.

An FSA is sorted if for each state, its leaving arcs are sorted by labels in ascending order. If there is a tie, destination states are used for sorting.

Caution

Arcs entering the final state have label -1. During sorting, -1 is reinterpreted as an unsigned number. Internally, all labels are reinterpreted as unsigned numbers during sorting.

An example of k2.arc_sort() is given below.

Listing 3 k2.arc_sort() example

s = '''
0 2 -1  0.0
0 1 2 0.2
0 1 1 0.3
1 2 -1 0.4
2
'''
fsa = k2.Fsa.from_str(s)
sorted_fsa = k2.arc_sort(fsa)
fsa.draw('before_sort.svg', title='before sort')
sorted_fsa.draw('after_sort.svg', title='after sort')

Note

k2.arc_sort() supports CUDA as well as CPU.
autograd is also supported.
Its input can be either a single FSA or a FsaVec.

Hint

Inside k2.arc_sort() it checks whether the input FSA is sorted or not. If the input is already sorted, it is returned directly. Otherwise, a new sorted FSA is returned.

intersect

The following is an example of k2.intersect().

Listing 4 Example code for k2.intersect()

s1 = '''
0 1 0 0.1
0 1 1 0.2
1 1 2 0.3
1 2 -1 0.4
2
'''

s2 = '''
0 1 1 1
0 1 2 2
1 2 -1 3
2
'''

a_fsa = k2.Fsa.from_str(s1)
b_fsa = k2.Fsa.from_str(s2)
c_fsa = k2.intersect(a_fsa, b_fsa)

a_fsa.draw('a_fsa_intersect.svg', title='a_fsa')
b_fsa.draw('b_fsa_intersect.svg', title='b_fsa')
c_fsa.draw('c_fsa_intersect.svg', title='c_fsa')

The outputs are shown below

k2.intersect() has an optional argument treat_epsilons_specially. Its default value is True. If it is set to False, then the label 0 is treated as a normal label. The following is an example setting treat_epsilons_specially to False.

Listing 5 Example code for k2.intersect() with treat_epsilons_specially=False

s1 = '''
0 1 0 0.1
0 1 1 0.2
1 1 2 0.3
1 2 -1 0.4
2
'''

s2 = '''
0 1 1 1
0 1 2 2
1 2 -1 3
2
'''

a_fsa = k2.Fsa.from_str(s1)
b_fsa = k2.Fsa.from_str(s2)
c_fsa = k2.intersect(a_fsa, b_fsa, treat_epsilons_specially=False)

a_fsa.draw('a_fsa_intersect2.svg', title='a_fsa')
b_fsa.draw('b_fsa_intersect2.svg', title='b_fsa')
c_fsa.draw('c_fsa_intersect2.svg', title='c_fsa')

The outputs are shown below

k2.add_epsilon_self_loops() can be used to add epsilon self loops to an FSA when treat_epsilons_specially is False but you want to treat them specially. The following is an example using k2.add_epsilon_self_loops() with treat_epsilons_specially == False.

Listing 6 k2.intersect() with treat_epsilons_specially=False and k2.add_epsilon_self_loops()

s1 = '''
0 1 0 0.1
0 1 1 0.2
1 1 2 0.3
1 2 -1 0.4
2
'''

s2 = '''
0 1 1 1
0 1 2 2
1 2 -1 3
2
'''

a_fsa = k2.Fsa.from_str(s1)
b_fsa = k2.Fsa.from_str(s2)
b_fsa = k2.add_epsilon_self_loops(b_fsa)
c_fsa = k2.intersect(a_fsa, b_fsa, treat_epsilons_specially=False)

a_fsa.draw('a_fsa_intersect3.svg', title='a_fsa')
b_fsa.draw('b_fsa_intersect3.svg', title='b_fsa')
c_fsa.draw('c_fsa_intersect3.svg', title='c_fsa')

Note

k2.intersect() works ONLY on CPU when treat_epsilons_specially=True. When treat_epsilons_specially=False and both a_fsa and b_fsa are on GPU, then this function works on GPU; in this case, the two input FSAs do not need to be arc sorted.
autograd is also supported.
Its input can be either a single FSA or a FsaVec.
The input FSAs have to be arc sorted when treat_epsilons_specially=True.

compose

The composition is a straightforward generalization of the intersection from acceptors to transducers. The following is an example of k2.compose().

Listing 7 Example code for k2.compose()

s = '''
0 1 1 1 0
1 2 2 2 0
2 3 -1 -1 0
3
'''

a_fsa = k2.ctc_topo(max_token=2, modified=False) 
b_fsa = k2.Fsa.from_str(s, acceptor=False)
c_fsa = k2.compose(a_fsa, b_fsa)

a_fsa.draw('a_fsa_compose.svg', title='a_fsa')
b_fsa.draw('b_fsa_compose.svg', title='b_fsa')
c_fsa.draw('c_fsa_compose.svg', title='c_fsa')

The outputs are shown below

k2.compose() has an optional argument treat_epsilons_specially. Its default value is True. If it is set to False, then the label 0 is treated as a normal label. The following is an example setting treat_epsilons_specially to False.

Listing 8 Example code for k2.compose() with treat_epsilons_specially=False

s = '''
0 1 1 1 0
1 2 2 2 0
2 3 -1 -1 0
3
'''

a_fsa = k2.ctc_topo(max_token=2, modified=False) 
b_fsa = k2.Fsa.from_str(s, acceptor=False)
c_fsa = k2.compose(a_fsa, b_fsa, treat_epsilons_specially=False)

a_fsa.draw('a_fsa_compose2.svg', title='a_fsa')
b_fsa.draw('b_fsa_compose2.svg', title='b_fsa')
c_fsa.draw('c_fsa_compose2.svg', title='c_fsa')

The outputs are shown below

k2.add_epsilon_self_loops() can be used to add epsilon self loops to an FSA when treat_epsilons_specially is False but you want to treat them specially. The following is an example using k2.add_epsilon_self_loops() with treat_epsilons_specially == False.

Listing 9 k2.intersect() with treat_epsilons_specially=False and k2.add_epsilon_self_loops()

s = '''
0 1 1 1 0
1 2 2 2 0
2 3 -1 -1 0
3
'''

a_fsa = k2.ctc_topo(max_token=2, modified=False)
b_fsa = k2.Fsa.from_str(s, acceptor=False)
b_fsa = k2.add_epsilon_self_loops(b_fsa)
c_fsa = k2.compose(a_fsa, b_fsa, treat_epsilons_specially=False)

a_fsa.draw('a_fsa_compose3.svg', title='a_fsa')
b_fsa.draw('b_fsa_compose3.svg', title='b_fsa')
c_fsa.draw('c_fsa_compose3.svg', title='c_fsa')

Note

k2.compose() works ONLY on CPU when treat_epsilons_specially=True. When treat_epsilons_specially=False and both a_fsa and b_fsa are on GPU, then this function works on GPU; in this case, the two input FSAs do not need to be arc sorted.
autograd is also supported.
Its input can be either a single FSA or a FsaVec.
The input FSAs have to be arc sorted when treat_epsilons_specially=True.

connect

k2.connect() removes states that are neither accessible nor co-accessible. It is often used after k2.intersect() or k2.compose().

The following is an example.

Listing 10 k2.connect() example

s1 = '''
0 0 1 0.1
0 1 2 0.2
1 2 -1 0.3
2
'''
s2 = '''
0 1 1 1
0 1 2 2
1 2 -1 3
2
'''
a_fsa = k2.Fsa.from_str(s1)
b_fsa = k2.Fsa.from_str(s2)
c_fsa = k2.intersect(a_fsa, b_fsa)
connected = k2.connect(c_fsa)
a_fsa.draw('a_fsa_1.svg', title='a_fsa')
b_fsa.draw('b_fsa_1.svg', title='b_fsa')
c_fsa.draw('before_connect.svg', title='intersect(a_fsa, b_fsa)')
connected.draw('after_connect.svg', title='after connect')

Note

k2.connect() supports ONLY CPU
autograd is also supported.
Its input can be either a single FSA or a FsaVec.

get_forward_scores

k2.Fsa.get_forward_scores() computes and returns forward scores per state (like alphas in Baum-Welch) or forward best-path scores if log_semiring is False.

Caution

Arc scores are in log scale.

We will use the following code as an example to demonstrate how k2.Fsa.get_forward_scores() works in k2.

Listing 11 k2.Fsa.get_forward_scores() example

s = '''
0 1 1 1.2
0 1 3 0.8
0 2 2 0.5
1 2 5 0.1
1 3 -1 0.6
2 3 -1 0.4
3
'''
fsa = k2.Fsa.from_str(s)
fsa.draw('get_forward_scores.svg', title='get_forward_scores example')
fsa_vec = k2.create_fsa_vec([fsa])
log_semiring = fsa_vec.get_forward_scores(use_double_scores=True,
                                          log_semiring=True)
tropical_semiring = fsa_vec.get_forward_scores(use_double_scores=True,
                                               log_semiring=False)
print('get_forward_scores for log semiring:', log_semiring)
print('get_forward_scores for tropical semiring:', tropical_semiring)

The outputs are:

get_forward_scores for log semiring: tensor([0.0000, 1.7130, 2.0513, 3.0777], dtype=torch.float64)
get_forward_scores for tropical semiring: tensor([0.0000, 1.2000, 1.3000, 1.8000], dtype=torch.float64)

k2.Fsa.get_forward_scores() has two arguments:

use_double_scores

When it is True, double precision floats are used in the computation and the returned tensor has dtype torch.float64; when it is False, the computation uses single precision floats and returned tensor’s dtype is torch.float32.

log_semiring

When it is True, this function combines path scores with LogAdd, e.g., \(\log(e^a + e^b)\). When it is False, path scores are combined with \(\max(a, b)\)

The following two subsections illustrate step by step how to obtain the above printed results. For ease of reference, we use \(f_i\) to denote the forward score of state \(i\).

log_semiring==True

It uses LogAdd to combine path scores.

State 0 is the start state and \(f_0\) is defined to be 0.
\(f_1\) is computed with the following formula:

\[f_1 = \log(e^{f_0 + 1.2} + e^{f_0 + 0.8}) = \log(e^{1.2} + e^{0.8}) = 1.7130\]

where 1.2 is the score of one of the two arcs from state 0 to state 1; 0.8 is the score of the other arc from state 0 to state 1.

\(f_2\) is computed by:

\[f_2 = \log(e^{f_0 + 0.5} + e^{f_1 + 0.1}) = \log(e^{0.5} + e^{1.8130}) = 2.0513\]
\(f_3\) can be computed from \(f_1\) and \(f_2\):

\[f_3 = \log(e^{f_1 + 0.6} + e^{f_2 + 0.4}) = \log(e^{2.3130} + e^{2.4513}) = 3.0777\]

log_semiring==False

It uses max to combine path scores.

State 0 is the start state and \(f_0\) is defined to be 0
\(f_1 = \max(f_0 + 1.2, f_0 + 0.8) = \max(1.2, 0.8) = 1.2\)
\(f_2 = \max(f_0 + 0.5, f_1 + 0.1) = \max(0.5, 1.3) = 1.3\)
\(f_3 = \max(f_1 + 0.6, f_2 + 0.4) = \max(1.8, 1.7) = 1.8\)

Note

k2.Fsa.get_forward_scores() supports CUDA as well as CPU.
autograd is also supported.
It supports only FsaVec.

get_tot_scores

k2.Fsa.get_tot_scores() computes and returns forward scores of the final state of each FSA. Refer to get_forward_scores for how to compute forward scores.

The following is an example of k2.Fsa.get_tot_scores().

Listing 12 k2.Fsa.get_tot_scores() example

s = '''
0 1 1 1.2
0 1 3 0.8
0 2 2 0.5
1 2 5 0.1
1 3 -1 0.6
2 3 -1 0.4
3
'''
fsa = k2.Fsa.from_str(s)
fsa.draw('get_tot_scores.svg', title='get_tot_scores example')
fsa_vec = k2.create_fsa_vec([fsa])
log_semiring = fsa_vec.get_tot_scores(use_double_scores=True,
                                      log_semiring=True)
tropical_semiring = fsa_vec.get_tot_scores(use_double_scores=True,
                                           log_semiring=False)
print('get_tot_scores for log semiring:', log_semiring)
print('get_tot_scores for tropical semiring:', tropical_semiring)

It prints:

get_tot_scores for log semiring: tensor([3.0777], dtype=torch.float64)
get_tot_scores for tropical semiring: tensor([1.8000], dtype=torch.float64)

Note

k2.Fsa.get_tot_scores() supports CUDA as well as CPU.
autograd is also supported.
It supports only FsaVec.