import { NonTerminal , Category , isNonTerminal } from "./category" ; import { Rule , isUnitProduction } from "./rule" ; import { getOrCreateMap , getOrCreateSet } from "../util" ; /**
 * Returns the inverse of matrix `M`.
 * Use Gaussian Elimination to calculate the inverse:
 * (1) 'augment' the matrix (left) by the identity (on the right)
 * (2) Turn the matrix on the left into the identity by elemetry row ops
 * (3) The matrix on the right is the inverse (was the identity matrix)
 *
 * There are 3 elementary row ops: (I combine b and c in my code)
 * (a) Swap 2 rows
 * (b) Multiply a row by a scalar
 * (c) Add 2 rows
 */ function invert ( M ) { if ( M . length !== M [ 0 ] . length ) { throw new Error ( "Matrix must be square" ) ; } const dim = M . length ; const I = [ ] ; const C = [ ] ; for ( let i = 0 ; i < dim ; i += 1 ) { I [ I . length ] = [ ] ; C [ C . length ] = [ ] ; for ( let j = 0 ; j < dim ; j += 1 ) { if ( i == j ) { I [ i ] [ j ] = 1 ; } else { I [ i ] [ j ] = 0 ; } C [ i ] [ j ] = M [ i ] [ j ] ; } } for ( let i = 0 ; i < dim ; i += 1 ) { let e = C [ i ] [ i ] ; if ( e === 0 ) { for ( let ii = i + 1 ; ii < dim ; ii += 1 ) { if ( C [ ii ] [ i ] !== 0 ) { for ( let j = 0 ; j < dim ; j ++ ) { e = C [ i ] [ j ] ; C [ i ] [ j ] = C [ ii ] [ j ] ; C [ ii ] [ j ] = e ; e = I [ i ] [ j ] ; I [ i ] [ j ] = I [ ii ] [ j ] ; I [ ii ] [ j ] = e ; } break ; } } e = C [ i ] [ i ] ; if ( e == 0 ) { throw new Error ( "Matrix was not invertable" ) ; } } for ( let j = 0 ; j < dim ; j ++ ) { C [ i ] [ j ] = C [ i ] [ j ] / e ; I [ i ] [ j ] = I [ i ] [ j ] / e ; } for ( let ii = 0 ; ii < dim ; ii ++ ) { if ( ii == i ) { continue ; } e = C [ ii ] [ i ] ; for ( let j = 0 ; j < dim ; j ++ ) { C [ ii ] [ j ] -= e * C [ i ] [ j ] ; I [ ii ] [ j ] -= e * I [ i ] [ j ] ; } } } return I ; } /**
 * Information holder for left-corner relations and left*-corner relations. Essentially a map from  Category * to  Category with some indexing.
  export class LeftCorners < T > { /**
     * X -L> Y probability, undefined for 0.0
     */ private readonly map : Map < Category < T > , Map < Category < T > , number > > ; /**
     * X -L> Y is greater than 0.0
     */ private nonZeroScores : Map < Category < T > , Set < Category < T > > > ; /**
     * X -L> Y is greater than 0.0, and Y is a non-terminal
     */ private nonZeroScoresToNonTerminals : Map < Category < T > , Set < NonTerminal > > ; readonly ZERO : number ; /**
     * Information holder for left-corner relations and left*-corner relations. Essentially a map from  Category * to  Category with some utility functions to deal with probabilities.
     *  param ZERO constructor ( ZERO = 0 ) { this . ZERO = ZERO ; this . map = new Map < Category < T > , Map < Category < T > , number > > ( ) ; this . nonZeroScores = new Map < NonTerminal , Set < Category < T > > > ( ) ; this . nonZeroScoresToNonTerminals = new Map < NonTerminal , Set < NonTerminal > > ( ) ; } param x param y param probability public add ( x , y , probability ) { const newProbability = this . get ( x , y ) + probability ; if ( ! isFinite ( newProbability ) ) { throw new Error ( "Invalid left-[*]-corner probability: " + newProbability + " for " + x + " -L> " + y + " ... " ) ; } this . set ( x , y , newProbability ) ; } return public get ( x , y ) { if ( ! this . map ) throw new Error ( "Map was not defined" ) ; const yToP = getOrCreateMap ( this . map , x ) ; if ( ! yToP ) return this . ZERO ; else return yToP . get ( y ) || this . ZERO ; } param x param y param val public set ( x , y , val ) { if ( val !== this . ZERO ) { const yToProb = getOrCreateMap ( this . map , x ) ; yToProb . set ( y , val ) ; getOrCreateSet ( this . nonZeroScores , x ) . add ( y ) ; if ( isNonTerminal ( y ) ) getOrCreateSet ( this . nonZeroScoresToNonTerminals , x ) . add ( y ) ; } } public getNonZeroScores ( x ) { return this . nonZeroScores . get ( x ) ; } public getNonZeroScoresToNonTerminals ( x ) { return this . nonZeroScoresToNonTerminals . get ( x ) ; } } /**
 * Uses a trick to compute left*Corners (R_L), the reflexive transitive closure of leftCorners:
 *
 * ~~ P must have its scores defines as ordinary probabilities between 0 and 1 ~~
 *
 * <code>R_L = I + P_L R_L = (I - P_L)^-1</code>
 */ export function getReflexiveTransitiveClosure < T > ( nonTerminals , P , zero = 0.0 ) { const nonterminalz = [ ] ; nonTerminals . forEach ( a => nonterminalz . push ( a ) ) ; const R_L_inverse = [ ] ; for ( let row = 0 ; row < nonterminalz . length ; row ++ ) { const X = nonterminalz [ row ] ; R_L_inverse [ row ] = [ ] ; for ( let col = 0 ; col < nonterminalz . length ; col ++ ) { const Y = nonterminalz [ col ] ; const prob = P . get ( X , Y ) ; R_L_inverse [ row ] [ col ] = ( row === col ? 1 : 0 ) - prob ; } } const R_L = invert ( R_L_inverse ) ; const m = new LeftCorners < T > ( zero ) ; /**
     * Copy all matrix values into our  LeftCorners object
      for ( let roww = 0 ; roww < nonterminalz . length ; roww ++ ) { for ( let coll = 0 ; coll < nonterminalz . length ; coll ++ ) { m . set ( nonterminalz [ roww ] , nonterminalz [ coll ] , R_L [ roww ] [ coll ] ) ; } } return m ; } export function getUnitStarCorners < T > ( rules , nonTerminals , zero = 0.0 ) { const P_U = new LeftCorners ( zero ) ; rules . forEach ( ( rule ) => { if ( isUnitProduction ( rule ) ) P_U . add ( rule . left , rule . right [ 0 ] , rule . probability ) ; } ) ; return getReflexiveTransitiveClosure ( nonTerminals , P_U , zero ) ; } /**
 * Compute left corner relations
 */ export function getLeftCorners < T > ( rules , ZERO = 0.0 ) { const leftCorners = new LeftCorners ( ZERO ) ; rules . forEach ( ( rule ) => { if ( rule . right . length > 0 && isNonTerminal ( rule . right [ 0 ] ) ) { leftCorners . add ( rule . left , rule . right [ 0 ] , rule . probability ) ; } } ) ; return leftCorners ; }