private static MutableFst doCompose(Fst fst1, Fst fst2, Semiring semiring, boolean useSorted) {
    if (useSorted) {
      assert(FstUtils.symbolTableEquals(fst1.getOutputSymbols(), fst2.getInputSymbols()));
    }

    MutableFst res = new MutableFst(semiring, symbolTableEffectiveCopy(fst1.getInputSymbols()),
        symbolTableEffectiveCopy(fst2.getOutputSymbols()));

    // state map is q -> n where q is (q_i, q_j) a state pair made up of state from fst1 and a state from fst2 and
    // n is the new state index in the composed FST that represents this tuple
    HashMap<IndexPair, Integer> stateMap = Maps.newHashMap();
    Deque<IndexPair> queue = new LinkedList<>();

    IndexPair first = new IndexPair(fst1.getStartState().getId(), fst2.getStartState().getId());
    MutableState newStart = res.newStartState();
    newStart.setFinalWeight(semiring.times(fst1.getStartState().getFinalWeight(), fst2.getStartState().getFinalWeight()));
    stateMap.put(first, newStart.getId());
    queue.addLast(first);

    SymbolTable.InvertedSymbolTable fst1In = fst1.getInputSymbols().invert();
    SymbolTable.InvertedSymbolTable fst1Out = fst1.getOutputSymbols().invert();
    SymbolTable.InvertedSymbolTable fst2In = fst2.getInputSymbols().invert();
    SymbolTable.InvertedSymbolTable fst2Out = fst2.getOutputSymbols().invert();

    while (!queue.isEmpty()) {
      IndexPair p = queue.removeFirst();
      State s1 = fst1.getState(p.getLeft());
      State s2 = fst2.getState(p.getRight());
      MutableState resultState = res.getState(stateMap.get(p));
      if (useSorted) {
        assert (ArcSort.isSorted(s1, OLabelCompare.INSTANCE) && ArcSort.isSorted(s2, ILabelCompare.INSTANCE)) :
            "\ns1 " + s1.getArcs() + "\n s2 " + s2.getArcs();
      }

      int jstart = 0; // if not sorted jstart is never updated so always does full nested loop
      for (int i = 0; i < s1.getArcCount(); ++i) {
        Arc a1 = s1.getArc(i);
        for (int j = jstart; j < s2.getArcCount(); ++j) {
          Arc a2 = s2.getArc(j);
          if (useSorted && a1.getOlabel() < a2.getIlabel()) {
            break; // if we know the arcs are sorted then once we've gotten here we know there cant be more j's
          }
          String a1Isym = fst1In.keyForId(a1.getIlabel());
          String a1Osym = fst1Out.keyForId(a1.getOlabel());
          String a2Isym = fst2In.keyForId(a2.getIlabel());
          String a2Osym = fst2Out.keyForId(a2.getOlabel());
          if (a1Osym.equals(a2Isym)) {
            State nextState1 = a1.getNextState();
            State nextState2 = a2.getNextState();
            IndexPair nextPair = new IndexPair(nextState1.getId(), nextState2.getId());
            Integer nextState = stateMap.get(nextPair);
            MutableState realNextState;
            if (nextState == null) {
              realNextState = res.newState();
              realNextState.setFinalWeight(semiring.times(nextState1.getFinalWeight(), nextState2.getFinalWeight()));
              stateMap.put(nextPair, realNextState.getId());
              queue.addLast(nextPair);
            } else {
              realNextState = res.getState(nextState);
            }
            res.addArc(resultState, a1Isym, a2Osym, realNextState, semiring.times(a1.getWeight(), a2.getWeight()));
          } else if (useSorted && a1.getOlabel() > a2.getIlabel()) {
            // if we're sorted and outer is greater then we know we'll never need to eval this inner index again
            jstart = j + 1;
          }
        }
      }
    }
    return res;
  }
private static MutableFst doCompose ( Fst fst1 , Fst fst2 , Semiring semiring , boolean useSorted ) { if ( useSorted ) { assert ( FstUtils . symbolTableEquals ( fst1 . getOutputSymbols ( ) , fst2 . getInputSymbols ( ) ) ) ; } MutableFst res = new MutableFst ( semiring , symbolTableEffectiveCopy ( fst1 . getInputSymbols ( ) ) , symbolTableEffectiveCopy ( fst2 . getOutputSymbols ( ) ) ) ; HashMap < IndexPair , Integer > stateMap = Maps . newHashMap ( ) ; Deque < IndexPair > queue = new LinkedList < > ( ) ; IndexPair first = new IndexPair ( fst1 . getStartState ( ) . getId ( ) , fst2 . getStartState ( ) . getId ( ) ) ; MutableState newStart = res . newStartState ( ) ; newStart . setFinalWeight ( semiring . times ( fst1 . getStartState ( ) . getFinalWeight ( ) , fst2 . getStartState ( ) . getFinalWeight ( ) ) ) ; stateMap . put ( first , newStart . getId ( ) ) ; queue . addLast ( first ) ; SymbolTable . InvertedSymbolTable fst1In = fst1 . getInputSymbols ( ) . invert ( ) ; SymbolTable . InvertedSymbolTable fst1Out = fst1 . getOutputSymbols ( ) . invert ( ) ; SymbolTable . InvertedSymbolTable fst2In = fst2 . getInputSymbols ( ) . invert ( ) ; SymbolTable . InvertedSymbolTable fst2Out = fst2 . getOutputSymbols ( ) . invert ( ) ; while ( ! queue . isEmpty ( ) ) { IndexPair p = queue . removeFirst ( ) ; State s1 = fst1 . getState ( p . getLeft ( ) ) ; State s2 = fst2 . getState ( p . getRight ( ) ) ; MutableState resultState = res . getState ( stateMap . get ( p ) ) ; if ( useSorted ) { assert ( ArcSort . isSorted ( s1 , OLabelCompare . INSTANCE ) && ArcSort . isSorted ( s2 , ILabelCompare . INSTANCE ) ) : "\ns1 " + s1 . getArcs ( ) + "\n s2 " + s2 . getArcs ( ) ; } int jstart = 0 ; for ( int i = 0 ; i < s1 . getArcCount ( ) ; ++ i ) { Arc a1 = s1 . getArc ( i ) ; for ( int j = jstart ; j < s2 . getArcCount ( ) ; ++ j ) { Arc a2 = s2 . getArc ( j ) ; if ( useSorted && a1 . getOlabel ( ) < a2 . getIlabel ( ) ) { break ; } String a1Isym = fst1In . keyForId ( a1 . getIlabel ( ) ) ; String a1Osym = fst1Out . keyForId ( a1 . getOlabel ( ) ) ; String a2Isym = fst2In . keyForId ( a2 . getIlabel ( ) ) ; String a2Osym = fst2Out . keyForId ( a2 . getOlabel ( ) ) ; if ( a1Osym . equals ( a2Isym ) ) { State nextState1 = a1 . getNextState ( ) ; State nextState2 = a2 . getNextState ( ) ; IndexPair nextPair = new IndexPair ( nextState1 . getId ( ) , nextState2 . getId ( ) ) ; Integer nextState = stateMap . get ( nextPair ) ; MutableState realNextState ; if ( nextState == null ) { realNextState = res . newState ( ) ; realNextState . setFinalWeight ( semiring . times ( nextState1 . getFinalWeight ( ) , nextState2 . getFinalWeight ( ) ) ) ; stateMap . put ( nextPair , realNextState . getId ( ) ) ; queue . addLast ( nextPair ) ; } else { realNextState = res . getState ( nextState ) ; } res . addArc ( resultState , a1Isym , a2Osym , realNextState , semiring . times ( a1 . getWeight ( ) , a2 . getWeight ( ) ) ) ; } else if ( useSorted && a1 . getOlabel ( ) > a2 . getIlabel ( ) ) { jstart = j + 1 ; } } } } return res ; }
Computes the composition of two Fsts. Assuming no epsilon transitions.

Input Fsts are not modified.

@param fst1     the first Fst
@param fst2     the second Fst
@param semiring the semiring to use in the operation
@return the composed Fst