新一代Kaldi文章来源于新一代Kaldi，作者NGK编辑部
本文介绍新一代 Kaldi 项目的 Ragged 数据结构 相关代码：文中作图代码对应的colab: https://colab.research.google.com/drive/1kQc3co8gYbJwRNjdIe2NSRPD8ijSjwV8?usp=sharing k2 ragged 代码： https://github.com/k2-fsa/k2/blob/master/k2/csrc/ragged.h
本文主要探讨 k2 中不规则数据 Ragged 类型
1 缘起 Ragged
2 矩阵与 Ragged 数据索引计算方式对比分析
2.1 矩阵中坐标与存储位置互相推导
和存贮位置
的互换。即
。或者反过来
。
aux_labels = [h e sh an t on g yi]2.2 Ragged 数据坐标与存储位置的互相推导
2.2.1 使用 row_splits 由坐标计算存储位置
# 注意最后有两个 7， 解释见3.1
row_splits = [0, 2, 4, 7, 7]offset = row_splists[2] + 2 = 4 + 2 = 6
# 对应的 phone 为：
# aux_labels[6], 即为 g[
[h e]
[sh an]
[t on g]
[yi]
]2.2.2 使用 row_ids 由存储位置计算坐标
offset = 6
word = 0
foriinrange(len(row_splits) - 1):
if row_splits[i] <= offset and row_splits[i + 1] > offset:
word = irow_ids = [0, 0, 1, 1, 2, 2, 2, 3]word = row_ids[6] = 2# 找到该 word 的起始 start_phone 对应的 offset:
word_start_phone_offset = row_splits[2] = 4
# phone 的 offset 与 start_phone 的 offset
# 差值就是 phone 在当前 word 中的坐标
offset_inside_word = 6 - 4 = 23 更深层次的 Ragged 数据解析
# 最外层 国家 （对应 china_univ_fsav）
[
# 省份层
# 陕西省 (对应 china_univ_fsav 中的 fsa level)
[
# 城市层
# 西安市 (对应 china_univ_fsav 中的 state level)
[
# 高校层
西北工业大学 (对应 china_univ_fsav 中的 arc level)
西安交通大学
西安电子科技大学
长安大学
]
# 延安市
[
延安大学
]
# 汉中市
[
陕西理工大学
]
]
# 台湾省 (对应 china_univ_fsav 中的各个 fsa level)
[
# 台南市 (对应 china_univ_fsav 中的各个 state level)
[
成功大学 (对应 china_univ_fsav 中的各个 arc level)
]
# 台中市
[
逢甲大学
]
]
]provinces = [陕西省， 台湾省]
cites = [西安市， 延安市，汉中市，台南市， 台中市]
univs = [西北工业大学，西安交通大学，西安电子科技大学，长安大学，延安大学，陕西理工大学，成功大学，逢甲大学]3.1 k2 中 state 与 arc 的“从属”关系
state 0(西安) --> [西工大，西交，西电，长安大学]
state 1(延安) --> [延安大学]
state 2(汉中) --> [陕西理工大学]
state 3(辅助 state) --> [-1 辅助 arc]
state 4(辅助终止 state) --> []# 注意末尾有两个 7
# 7（最后一个） - 7（倒数第二个） = 0；
# 表示最后一个 state 对应的包含的 arc 为 []row_splits = [0, 4, 5, 6, 7, 7]3.2 多个 Ragged 可以构建更高一维的 Ragged
Provice[Cites[Universities]]Country[Provices[Cites[Universities]]]
china_univ_fsav = k2.create_fsa_vec([shaanxi_univ_fsa, taiwan_univ_fsa])shape = china_univ_fsav.arcs.shape()
print(shape)
# 对应输出
# [ [ [ x x x x ] [ x ] [ x ] [ x ] [ ] ] [ [ x ] [ x ] [ x ] [ ] ] ]provinces = [陕西省， 台湾省]
cites = [西安市， 延安市， 汉中市，辅助state, 辅助终止state, 台南市， 台中市, 辅助state, 辅助终止state]
univs = [西北工业大学，西安交通大学，西安电子科技大学，长安大学，延安大学，延安大学，陕西理工大学，辅助arc, 成功大学，逢甲大学, 辅助arc]print(f"shape.row_ids(1): {shape.row_ids(1)}")
print(f"shape.row_splits(1): {shape.row_splits(1)}")
# 对应输出
# shape.row_ids(1): tensor([0, 0, 0, 0, 0, 1, 1, 1, 1], dtype=torch.int32)
# shape.row_splits(1): tensor([0, 5, 9], dtype=torch.int32)“城市 -- 高校” 级别的 row_ids/row_splits:
print(f"shape.row_ids(2): {shape.row_ids(2)}")
print(f"shape.row_splits(2): {shape.row_splits(2)}")
# 对应输出
# shape.row_ids(2): tensor([0, 0, 0, 0, 1, 2, 3, 5, 6, 7], dtype=torch.int32)
# shape.row_splits(2): tensor([ 0, 4, 5, 6, 7, 7, 8, 9, 10, 10], dtype=torch.int32)3.2.1 由坐标计算存储位置 offset
province, city = 1, 0
city_offset = shape.row_splits(1)[province] + city = 5 + 0 = 5
# 到此环节可得出目标城市为
# 台南市 = cites[city_offset] = cites[5]univ = 0
univ_offset = shape.row_splits(2)[city_offset] + univ = 7 + 0 = 7
# 所以可得出目标高校为
# 成功大学 = univs[univ_offset] = univs[7]3.2.2 由存储位置 offset 计算坐标
city_offset = shape.row_ids(2)[univ_offset] = 6
# 所以目标城市为：
# 台中市 = cites[city_offset] = cities[6]province_offset = shape.row_ids(1)[city_offset] = 1
# 所以目标省份为：
# 台湾省 = provinces[province_offset] = provinces[1]province_start_city_offset = shape.row_splits(1)[province_offset] = 5
offset_inside_province = city_offset - province_start_city_offset = 6 - 5 = 1city_start_univ_offset = shape.row_splits(2)[city_offset] = 8
offset_inside_city = univ_offset - city_start_univ_offset = 8 - 8 = 0
4 对应代码实现
class RaggedShape{
...
private:
...
std::vector layers_;
}; struct RaggedShapeLayer {
...
Array1 row_splits;
...
Array1 row_ids;
... }; template
struct Ragged {
RaggedShape shape;
...
Array1 values;
}; struct Arc {
int32_t src_state;
int32_t dest_state;
int32_t label;floatscore;
...
};
...
using Fsa = Ragged; // 2 axes: state,arc
using FsaVec = Ragged; // 3 axes: fsa,state,arc. Note, the src_state
// and dest_stateinthe arc are *within the // FSA*, i.e. they are idx1 not idx01. using FsaOrVec = Ragged; //forwhen we don't know if it will have 2 or // 3 axes. (i.e. Fsa or FsaVec) ... 5 总结
6 展望
参考资料
[1]k2项目首页: https://github.com/k2-fsa/k2
[2]Ragged 头文件: https://github.com/k2-fsa/k2/blob/master/k2/csrc/ragged.h
[3]row_ids / row_splits概念: https://github.com/k2-fsa/k2/blob/7dcabf85e8bf06984c4abab0400ef1322b5ff3df/k2/csrc/utils.h#L50
