import { StateIndex } from "./state-index" ; import { Grammar } from "../../grammar/grammar" ; import { State , isCompleted , isActive , getActiveCategory } from "./state" ; import { NonTerminal , Terminal , isNonTerminal } from "../../grammar/category" ; import { Semiring } from "semiring" ; import { getOrCreateSet , getOrCreateMap } from "../../util" ; import { isUnitProduction , Rule , invalidDotPosition } from "../../grammar/rule" ; import { ViterbiScore } from "./viterbi-score" ; import { StateToObjectMap } from "./state-to-object-map" ; export class Chart < T , S > { readonly grammar : Grammar < T , S > ; private states = new StateIndex < S , T > ( ) ; private byIndex = new Map < number , Set < State < S , T > > > ( ) ; /**
     * The forward probability <code>α_i</code> of a chart is
     * the sum of the probabilities of
     * all constrained paths of length i that end in that chart, do all
     * paths from start to position i. So this includes multiple
     * instances of the same history, which may happen because of recursion.
     */ private forwardScores = new StateToObjectMap < T , S > ( ) ; /**
     * The inner probability <code>γ_{i}</code> of a chart
     * is the sum of the probabilities of all
     * paths of length (i - k) that start at position k (the rule's start position),
     * and end at the current chart and generate the input the input symbols up to k.
     * Note that this is conditional on the chart happening at position k with
     * a certain non-terminal X
     */ private innerScores = new StateToObjectMap < T , S > ( ) ; private viterbiScores = new StateToObjectMap < T , ViterbiScore < S , T > > ( ) ; completedStates = new Map < number , Set < State < S , T > > > ( ) ; completedStatesFor = new Map < number , Map < NonTerminal , Set < State < S , T > > > > ( ) ; completedStatesThatAreNotUnitProductions = new Map < number , Set < State < S , T > > > ( ) ; statesActiveOnNonTerminals = new Map < number , Set < State < S , T > > > ( ) ; nonTerminalActiveAtIWithNonZeroUnitStarToY = new Map < number , Map < NonTerminal , Set < State < S , T > > > > ( ) ; statesActiveOnTerminals = new Map < number , Map < Terminal < T > , Set < State < S , T > > > > ( ) ; statesActiveOnNonTerminal = new Map < NonTerminal , Map < number , Set < State < S , T > > > > ( ) ; private EMPTY_SET : Set < State < S , T > > = new Set < State < S , T > > ( ) ; constructor ( grammar ) { this . grammar = grammar ; } getStatesActiveOnNonTerminalWithNonZeroUnitStarScoreToY ( index , Y ) { return getOrCreateSet ( getOrCreateMap ( this . nonTerminalActiveAtIWithNonZeroUnitStarToY , index ) , Y ) ; } getStatesActiveOnNonTerminal ( y , position , beforeOrOnPosition ) { if ( position <= beforeOrOnPosition ) return getOrCreateSet ( getOrCreateMap ( this . statesActiveOnNonTerminal , y ) , position ) ; else throw new Error ( "Querying position after what we're on?" ) ; } param s return public getForwardScore ( s ) { return this . forwardScores . getByStateOrDefault ( s , this . grammar . probabilityMapping . ZERO ) ; } addForwardScore ( state , increment , semiring ) { const fw = semiring . plus ( this . getForwardScore ( state ) , increment ) ; this . setForwardScore ( state , fw ) ; return fw ; } setForwardScore ( s , probability ) { return this . forwardScores . putByState ( s , probability ) ; } private hasForwardScore ( s ) { return this . forwardScores . hasByState ( s ) ; } public getState ( rule , positionInInput , ruleStartPosition , ruleDotPosition ) { return this . states . getState ( rule , positionInInput , ruleStartPosition , ruleDotPosition ) ; } param positionInInput param ruleStartPosition param ruleDotPosition param rule param scannedToken return public getOrCreate ( positionInInput , ruleStartPosition , ruleDotPosition , rule , scannedToken ? ) { if ( this . states . has ( rule , positionInInput , ruleStartPosition , ruleDotPosition ) ) { return this . states . getState ( rule , positionInInput , ruleStartPosition , ruleDotPosition ) ; } else { const scannedCategory = scannedToken ? < Terminal < T > > rule . right [ ruleDotPosition - 1 ] : undefined ; const state = { rule , position : positionInInput , ruleStartPosition , ruleDotPosition , scannedToken : scannedToken , scannedCategory } ; this . addState ( state ) ; return state ; } } hasState ( state ) { return this . states . has ( state . rule , state . position , state . ruleStartPosition , state . ruleDotPosition ) ; } has ( rule , index , ruleStart , ruleDot ) { return this . states . has ( rule , index , ruleStart , ruleDot ) ; } addState ( state ) { if ( state . ruleDotPosition < 0 || state . ruleDotPosition > state . rule . right . length ) invalidDotPosition ( state . ruleDotPosition , state ) ; this . states . addState ( state ) ; const position = state . position ; getOrCreateSet ( this . byIndex , position ) . add ( state ) ; if ( isCompleted ( state ) ) { getOrCreateSet ( this . completedStates , position ) . add ( state ) ; if ( ! isUnitProduction ( state . rule ) ) getOrCreateSet ( this . completedStatesThatAreNotUnitProductions , position ) . add ( state ) ; getOrCreateSet ( getOrCreateMap ( this . completedStatesFor , state . position ) , state . rule . left ) . add ( state ) ; } if ( isActive ( state ) ) { const activeCategory = getActiveCategory ( state ) ; if ( isNonTerminal ( activeCategory ) ) { getOrCreateSet ( getOrCreateMap ( this . statesActiveOnNonTerminal , activeCategory ) , state . position ) . add ( state ) ; getOrCreateSet ( this . statesActiveOnNonTerminals , state . position ) . add ( state ) ; this . grammar . unitStarScores . getNonZeroScoresToNonTerminals ( activeCategory ) . forEach ( ( FromNonTerminal ) => { getOrCreateSet ( getOrCreateMap ( this . nonTerminalActiveAtIWithNonZeroUnitStarToY , position ) , FromNonTerminal ) . add ( state ) ; } ) ; } else { getOrCreateSet ( getOrCreateMap ( this . statesActiveOnTerminals , position ) , activeCategory ) . add ( state ) ; } } } setInnerScore ( s , probability ) { this . innerScores . putByState ( s , probability ) ; } param v setViterbiScore ( v ) { this . viterbiScores . putByState ( v . resultingState , v ) ; } getViterbiScore ( s ) { return this . viterbiScores . getByState ( s ) ; } hasViterbiScore ( s ) { return this . viterbiScores . hasByState ( s ) ; } param s return public getInnerScore ( s ) { return this . innerScores . getByStateOrDefault ( s , this . grammar . probabilityMapping . ZERO ) ; } public getCompletedStatesThatAreNotUnitProductions ( position ) { return this . completedStatesThatAreNotUnitProductions . get ( position ) ; } public getCompletedStates ( position ) { if ( this . completedStates . has ( position ) ) return this . completedStates . get ( position ) ; else return this . EMPTY_SET ; } public getStatesActiveOnNonTerminals ( index ) { return this . statesActiveOnNonTerminals . get ( index ) ; } public getStatesActiveOnTerminals ( index , terminal ) { if ( this . statesActiveOnTerminals . has ( index ) ) return this . statesActiveOnTerminals . get ( index ) . get ( terminal ) ; else return undefined ; } }