import { Grammar } from "../grammar/grammar" ; import { NonTerminal , Category , isNonTerminal , Terminal , WordWithTypes } from "../grammar/category" ; import { Rule } from "../grammar/rule" ; import { State } from "./chart/state" ; import { setViterbiScores , ViterbiScore } from "./chart/viterbi-score" ; import { Chart } from "./chart/chart" ; import { scan } from "./scan" ; import { predict } from "./predict" ; import { complete } from "./complete" ; import { ParseTree , addRightMost } from "./parsetree" ; export function addState < S , T > ( stateSets , index , ruleStartPosition , ruleDotPosition , rule , forward , inner ) { const state = stateSets . getOrCreate ( index , ruleStartPosition , ruleDotPosition , rule ) ; stateSets . setInnerScore ( state , inner ) ; stateSets . setForwardScore ( state , forward ) ; if ( stateSets . hasViterbiScore ( state ) ) { throw new Error ( "Viterbi score was already set for new chart?!" ) ; } return state ; } /**
 * Performs the backward part of the forward-backward algorithm
 */ export function getViterbiParseFromChart < S , T > ( state , chart ) { switch ( state . ruleDotPosition ) { case 0 : return { category : state . rule . left , children : [ ] } ; default : const prefixEnd = state . rule . right [ state . ruleDotPosition - 1 ] ; if ( ! isNonTerminal ( prefixEnd ) ) { if ( ! state . scannedToken ) throw new Error ( "Expected chart to be a scanned chart. This is a bug." ) ; const T = getViterbiParseFromChart ( chart . getOrCreate ( state . position - 1 , state . ruleStartPosition , state . ruleDotPosition - 1 , state . rule ) , chart ) ; addRightMost ( T , { token : state . scannedToken , category : state . scannedCategory , children : [ ] } ) ; return T ; } else { const viterbi = chart . getViterbiScore ( state ) ; const origin = viterbi . origin ; const T = getViterbiParseFromChart ( chart . getOrCreate ( origin . ruleStartPosition , state . ruleStartPosition , state . ruleDotPosition - 1 , state . rule ) , chart ) ; const Tprime = getViterbiParseFromChart ( origin , chart ) ; addRightMost ( T , Tprime ) ; return T ; } } } export function parseSentenceIntoChart < S , T > ( Start , grammar , tokens , scanProbability ? ) { const stateSets = new Chart ( grammar ) ; const wordToTypesMap = new Map < T , Terminal < T > [ ] > ( ) ; const tokensWithWords = tokens . map ( word => { if ( wordToTypesMap . has ( word ) ) return { types : wordToTypesMap . get ( word ) , word } ; else { const types = grammar . terminals . filter ( ( isOfType ) => isOfType ( word ) ) ; wordToTypesMap . set ( word , types ) ; return { types , word } ; } } ) ; const init = addState ( stateSets , 0 , 0 , 0 , { left : "<start>" , right : [ Start ] , probability : 1.0 } , grammar . probabilityMapping . ONE , grammar . probabilityMapping . ONE ) ; let i = 0 ; tokensWithWords . forEach ( ( token ) => { predict ( i , grammar , stateSets ) ; scan ( i , token , grammar . probabilityMapping . semiring , stateSets , scanProbability ) ; complete ( i + 1 , stateSets , grammar ) ; const completedStates = [ ] ; const completedStatez = stateSets . getCompletedStates ( i + 1 ) ; if ( ! ! completedStatez ) completedStatez . forEach ( s => completedStates . push ( s ) ) ; completedStates . forEach ( s => setViterbiScores ( stateSets , s , new Set < State < S , T > > ( ) , grammar . probabilityMapping ) ) ; i ++ ; } ) ; return [ stateSets , i , init ] ; } export interface ParseTreeWithScore < T > { parseTree : ParseTree < T > ; probability : number ; } export function getViterbiParse < S , T > ( Start , grammar , tokens , scanProbability ? ) { const [ chart , ignored , init ] = parseSentenceIntoChart ( Start , grammar , tokens , scanProbability ) ; if ( ! chart . has ( init . rule , tokens . length , 0 , init . rule . right . length ) ) throw new Error ( "Could not parse sentence." ) ; const finalState = chart . getOrCreate ( tokens . length , 0 , init . rule . right . length , init . rule ) ; const parseTree = getViterbiParseFromChart ( finalState , chart ) ; const toProbability = grammar . probabilityMapping . toProbability ; const finalScore = chart . getViterbiScore ( finalState ) . innerScore ; return { parseTree , probability : toProbability ( finalScore ) } ; }