cat 2gram.arpa | /kaldi/src/lmbin/arpa2fst --disambig-symbol=#0 --read-symbol-table=words.txt - G.fst

2gram.arpa

data
ngram 1=8
ngram 2=15

1-grams:
-0.6283889      </s>
-99     <s>     -0.4685211
-1.230449       不      -0.2466723
-0.9294189      不喜欢  -0.288065
-0.9294189      喜欢    -0.3258536
-0.7533277      小朱    -0.4130037
-0.9294189      小猪    -0.288065
-0.7533277      我      -0.3258535

2-grams:
-0.69897        <s> 不
-0.69897        <s> 小朱
-0.39794        <s> 我
-0.30103        不 小猪
-0.4771213      不喜欢 小朱
-0.4771213      不喜欢 我
-0.4771213      喜欢 小朱
-0.4771213      喜欢 小猪
-0.30103        小朱 </s>
-0.60206        小朱 不喜欢
-0.4771213      小猪 </s>
-0.4771213      小猪 喜欢
-0.60206        我 </s>
-0.60206        我 不喜欢
-0.60206        我 喜欢

end

Step1:对词典做消歧处理
ndisambig=$(utils/add_lex_disambig.pl $unk_opt --pron-probs $tmpdir/lexiconp.txt $tmpdir/lexiconp_disambig.txt)
Step2:构建L_disambig文本形式
utils/lang/make_lexicon_fst.py --sil-prob=$sil_prob --sil-phone=$silphone 
                               --sil-disambig='#'$ndisambig $tmpdir/lexiconp_disambig.txt | 
                    fstcompile --isymbols=$dir/phones.txt --osymbols=$dir/words.txt 
                               --keep_isymbols=false --keep_osymbols=falseL_disambig.txt $dir/L.fst
Step3:在词的出入口loop state上增加“#0:#0”自跳转边
fstaddselfloops  $dir/phones/wdisambig_phones.int $dir/phones/wdisambig_words.int $dir/L.fst | 
     fstarcsort --sort_type=olabel > $dir/L_disambig.fst

原始词典lexicon.txt
<unk>   sil
我      uo3
不      b u4
喜欢    x i3 h uan1
不喜欢  b u4 x i3 h uan1
小猪    x iao3 zh u1
小朱    x iao3 zh u1

在lexicon.txt中增加发音概率，一般取1.0
lexiconp.txt
<unk>   1.0     sil
我      1.0     uo3
不      1.0     b u4
喜欢    1.0     x i3 h uan1
不喜欢  1.0     b u4 x i3 h uan1
小猪    1.0     x iao3 zh u1
小朱    1.0     x iao3 zh u1

对lexiconp.txt相应部分增加辅助符号，做消歧处理
lexiconp_disambig.txt
<unk>   1.0     sil
我      1.0     uo3
不      1.0     b u4 #1
喜欢    1.0     x i3 h uan1
不喜欢  1.0     b u4 x i3 h uan1
小猪    1.0     x iao3 zh u1 #1
小朱    1.0     x iao3 zh u1 #2

#构建C.fst，输入为context_phone，输出为phone,disambig.list中为辅助符号
fstmakecontextfst --context-size=2 --central-position=1 --read-disambig-syms=disambig.list 5 ilabels.int > C.fst
#可视化的一些操作，构架三音子phone符号表
fstmakecontextsyms phones.txt ilabels.int > context_syms.txt
#可视化的一些操作，将二进制fst转成文本格式fst
fstprint --isymbols=context_syms.txt --osymbols=phones.txt C.fst > C.txt
#可视化的一些操作，画图
fstdraw --isymbols=context_syms.txt --osymbols=phones.txt C.fst > C.txt

音素表phones.txt
<eps> 0
a 1
b 2
#0 3
#1 4
辅助符号表
3
4

#kaldi utils/mkgraph.sh中构图的时候会将分成两个部分来构建Ha.fst
#Step1:构建HMM结构
make-h-transducer --disambig-syms-out=disambig_tid.int --transition-scale=1.0 ilabels_1_0 tree final.mdl Ha.fst #构建了一个不带self-loop的hmm.fst结构
#Step2:在phone的相应hmmstate上增加self-loop跳转边
add-self-loops --self-loop-scale=1.0 --disambig-syms=disambig_tid.int --reorder=true final.mdl Ha.fst H.fst

#以/kaldi/yesno为例
 fsttablecompose L_disambig.fst G.fst |  #复合操作
 fstdeterminizestar --use-log=true |   #确定化操作
 fstminimizeencoded |  #最小化操作
 fstpushspecial > LG.fst #权重前推

#为了提高效率，kaldi中将C.fst的构建和CLG复合过程一起完成
fstcomposecontext --context-size=$N --central-position=$P 
   --read-disambig-syms=$lang/phones/disambig.int 
   --write-disambig-syms=$lang/tmp/disambig_ilabels_${N}_${P}.int 
    ilabels_$N_$P $lang/tmp/LG.fst $lang/tmp/CLG.fst

#Step1:构建不带自跳转边的hmm结构Ha.fst
make-h-transducer --disambig-syms-out=disambig_tid.int --transition-scale=1.0 ilabels_1_0 tree final.mdl Ha.fst 
fsttablecompose $dir/Ha.fst "$clg" | fstdeterminizestar --use-log=true |  #compose操作
    fstrmsymbols $dir/disambig_tid.int |  #去除辅助符号
    fstrmepslocal |  #去除冗余的eps:eps跳转边
    fstminimizeencoded > $dir/HCLGa.fst #最小化操作
#Step3:在HCLGa.fst的相应hmmstate节点上加上自跳转边
 add-self-loops --self-loop-scale=1.0 --reorder=true final.mdl $dir/HCLGa.fst > $dir/HCLG.fst

Step1：初始化，保存初始状态信息；
Step2：在FST中进行非空输入跳转，在搜索路径上加上相应时刻的声学模型cost，
       对当前时刻可跳转到的所有nextstate计算经过该state的最优路径并保留其历史信息；
Step3：在FST中进行空输入跳转，
       对当前时刻可跳转到的所有nextstate计算经过该state的最优路径并保留其历史信息；
Step4：根据Beam值裁剪当前时刻的保留下来的所有路径，仅保留最有可能继续跳转的一些active paths；
Step5：对每个时刻重复Step2~Step4操作，直至最后一个时间窗；
Step6：检查最后时刻所有active paths的最后一个state是否为结束状态，舍弃未到结束状态的path，并为path加上final_cost；
Step7：计算最后时刻保留下来的active paths中的最短路径；
Step8：回溯该路径携带的历史信息，输出解码结果。

//Token
struct BackpointerToken {
  //从初始时刻到现在经过这state的所有路径中最短路径的total cost值
  BaseFloat tot_cost;
  //从初始时刻到现在经过这state的最短路径的cost值与该时刻最优local path的cost差值
  //一般在lattice裁剪的时候才会用到
  BaseFloat extra_cost;
  //该Token对应的state可扩展到的连接
  ForwardLinkT *links;
  //某时刻的所有Token会保存为一个链表，next指向该时刻Token链表的下一个Token
  BackpointerToken *next;
  //经过该Token的最优local路径的上一时刻Token
  Token *backpointer;
};

//ForwardLink
struct ForwardLink {
  using Label = fst::StdArc::Label;
  //link连接的下一Token
  Token *next_tok;  
  //link的输入输出标签ilabel/olabel
  Label ilabel;  // ilabel on arc
  Label olabel;  // olabel on arc
  //解码图HCLG上该link对应的cost值
  BaseFloat graph_cost;  // graph cost of traversing arc (contains LM, etc.)
  //该link输入ilabel表示的substate对应的声学模型得分
  BaseFloat acoustic_cost;  // acoustic cost (pre-scaled) of traversing arc
  //该link的起始Token跟下一时刻Token的所有连接都存储为链表，next为链表中的nextlink
  ForwardLink *next;  
};

template <typename FST, typename Token>
bool LatticeFasterDecoderTpl<FST, Token>::Decode(DecodableInterface *decodable) {

  //InitDecoding函数功能:
  // 初始状态设置
  //    1.在解码开始或解码过程中需要重新开始的时刻，清除内部变量保存的历史信息；
  //    2.获取解码图HCLG中的起始state和该state的所有<eps>_input边连接的nextstate；
  InitDecoding();

  //AdvanceDecoding函数功能:
  // 随音频的不断输入，流式解码
  //    1.某时刻，在HCLG中进行非<eps>_input跳转，进行Beam裁剪，
  //       并保留active_token的声学模型得分、graph边长、输入输出label等历史信息；
  //    2.某时刻，在HCLG中进行<eps>_input跳转，进行Beam裁剪，
  //       并保留active_token的graph边长、输入输出label等历史信息；
  //    3.在达到设置的prune间隔时，根据预设的lattice_beam裁剪active Tokens和相应ForwardLink,
  //       减少内存占用；
  AdvanceDecoding(decodable);

  //FinalizeDecoding函数功能:
  // 音频结尾时，处理final状态
  //    1.解码结束时，为最后时刻的active Tokens加上HCLG上相应state的final cost；
  //    2.获取解码图HCLG中的起始state和该state的所有<eps>_input边连接的nextstate；
  //    3.根据预设的lattice_beam裁剪active Tokens和相应ForwardLink；
  FinalizeDecoding();
}

template <typename FST, typename Token>
void LatticeFasterDecoderTpl<FST, Token>::InitDecoding() {
  // Step1:清除变量保存的所有历史信息
  DeleteElems(toks_.Clear());
  cost_offsets_.clear();
  ClearActiveTokens(); //清除所有active token及相应Link的内存占用
  warned_ = false;
  num_toks_ = 0;
  decoding_finalized_ = false;
  final_costs_.clear();

  // Step2:获取解码图HCLG中的START state，作为t=0时刻Token
  StateId start_state = fst_->Start();
  KALDI_ASSERT(start_state != fst::kNoStateId);
  active_toks_.resize(1);
  Token *start_tok = new Token(0.0, 0.0, NULL, NULL, NULL);
  active_toks_[0].toks = start_tok;
  toks_.Insert(start_state, start_tok);
  num_toks_++;

  // Step3:解码图START state存在<eps>_input跳转边，获取所有graph_cost<beam值的nextstate，
  //       并存入t=0时刻的active Token链表中，同时保留它们之间的连接关系。
  ProcessNonemitting(config_.beam);
}

template <typename FST, typename Token>
void LatticeFasterDecoderTpl<FST, Token>::AdvanceDecoding(DecodableInterface *decodable,
                                                int32 max_num_frames) {
  //Step1: 等待DNN声学模型部分计算完成
  int32 num_frames_ready = decodable->NumFramesReady();
  int32 target_frames_decoded = num_frames_ready;
  if (max_num_frames >= 0)
    target_frames_decoded = std::min(target_frames_decoded,
                                     NumFramesDecoded() + max_num_frames);

  //Step2: 对每个chunk进行解码
  while (NumFramesDecoded() < target_frames_decoded) {
    //Step2.1：达到prune间隔周期时，修剪与当前时刻最优路径cost值相差大于
    //         预设lattice_beam值的active路径上的token及forwardlink，释放内存
    if (NumFramesDecoded() % config_.prune_interval == 0) {
      PruneActiveTokens(config_.lattice_beam * config_.prune_scale);
    }

    //Step2.2：解码图上的非<eps> input跳转,在跳转路径上加上相应声学模型得分
    //  1.根据上一时刻的active Tokens, 根据预设的最大最小active token数量及beam值
    //    计算应用于当前时刻BeamSearch的adaptive_beam值；
    //  2.计算当前时刻加上声学模型得分后跳转得到的最优local path；
    //  3.将上一时刻满足cur_cutoff(=cur_min_cost + adaptive_beam)条件的active_token
    //    进行解码图上的非eps_input跳转，保留满足next_cutoff(=next_min_cost + adaptive_beam)的
    //    link,并存入当前时刻的active_token列表中
    BaseFloat cost_cutoff = ProcessEmitting(decodable);

    //Step2.3：解码图上的<eps> input跳转
    //  将当前时刻满足cur_cutoff(=cur_min_cost + adaptive_beam)条件的active_token进行解码图上的
    //  eps_input跳转，保留满足cur_cutoff的link,并存入当前时刻的active_token列表中
    ProcessNonemitting(cost_cutoff);
  }
}

template <typename FST, typename Token>
void LatticeFasterDecoderTpl<FST, Token>::FinalizeDecoding() {

  // Step1: 解码到达音频结尾处时，为最后时刻的Token加上解码图上的final_prob，获取最优路径的
  //        获取最优路径的长度min_cost，修剪掉与min_cost差值大于lattice_beam值的Tokens和links
  int32 final_frame_plus_one = NumFramesDecoded();
  int32 num_toks_begin = num_toks_;
  PruneForwardLinksFinal();

  // Step2: 从后向前，修剪掉与最优路径总长min_cost差值大于lattice_beam值的Tokens和links
  for (int32 f = final_frame_plus_one - 1; f >= 0; f--) {
    bool b1, b2; // values not used.
    BaseFloat dontcare = 0.0; // delta of zero means we must always update
    PruneForwardLinks(f, &b1, &b2, dontcare);
    PruneTokensForFrame(f + 1);
  }
  PruneTokensForFrame(0);
  KALDI_VLOG(4) << "pruned tokens from " << num_toks_begin
                << " to " << num_toks_;
}