public static void runOutsideAlgorithm ( final int [ ] sent , final CnfGrammar grammar , final LoopOrder loopOrder , final Chart inChart , final Chart outChart , final Scorer scorer ) { // Base case. // -- part I: outsideScore(S, 0, n) = 0 = log(1). ChartCell outRootCell = outChart . getCell ( 0 , sent . length ) ; outRootCell . updateCell ( grammar . getRootSymbol ( ) , 0 , - 1 , null ) ; // -- part II: outsideScore(A, 0, n) = -inf = log(0) for all A \neq S. // This second part of the base case is the default initialization for each cell. // We still start at width = n so that we can apply unary rules to our // base case root terminal S. // // For each cell in the chart. (width decreasing) for ( int width = sent . length ; width >= 1 ; width -- ) { for ( int start = 0 ; start <= sent . length - width ; start ++ ) { int end = start + width ; ChartCell outCell = outChart . getCell ( start , end ) ; // Apply unary rules. ScoresSnapshot scoresSnapshot = outCell . getScoresSnapshot ( ) ; int [ ] nts = outCell . getNts ( ) ; for ( final int parentNt : nts ) { for ( final Rule r : grammar . getUnaryRulesWithParent ( parentNt ) ) { // TODO: Check whether this outside rule even matters. // Arguably this would create an outside chart that is // incomplete. //ChartCell inCell = inChart.getCell(start, end); // TODO: move this out of the loop. //if (inCell.getScore(r.getLeftChild()) > Double.NEGATIVE_INFINITY) { double score = scorer . score ( r , start , end , end ) + scoresSnapshot . getScore ( parentNt ) ; outCell . updateCell ( r . getLeftChild ( ) , score , end , r ) ; //} } } // Apply binary rules. if ( loopOrder == LoopOrder . CARTESIAN_PRODUCT ) { processCellCartesianProduct ( grammar , inChart , outChart , start , end , outCell , scorer ) ; } else if ( loopOrder == LoopOrder . LEFT_CHILD ) { processCellLeftChild ( grammar , inChart , outChart , start , end , outCell , scorer ) ; } else if ( loopOrder == LoopOrder . RIGHT_CHILD ) { processCellRightChild ( grammar , inChart , outChart , start , end , outCell , scorer ) ; } else { throw new RuntimeException ( "Not implemented: " + loopOrder ) ; } } } // Apply lexical rules to each word. for ( int i = 0 ; i <= sent . length - 1 ; i ++ ) { ChartCell outCell = outChart . getCell ( i , i + 1 ) ; ScoresSnapshot scoresSnapshot = outCell . getScoresSnapshot ( ) ; for ( final Rule r : grammar . getLexicalRulesWithChild ( sent [ i ] ) ) { double score = scorer . score ( r , i , i + 1 , i + 1 ) + scoresSnapshot . getScore ( r . getParent ( ) ) ; outCell . updateCell ( r . getLeftChild ( ) , score , i + 1 , r ) ; } } }
Runs the outside algorithm given an inside chart .