export type BasicOperation < T > = { kind : 'append' | 'insert' ; updated : T ; } | { kind : 'delete' ; original : T ; } ; export type Operation < T , C > = C | BasicOperation < T > ; type GetChangeOp < T , C > = ( a : T , b : T ) => C | undefined ; export function levenshtein < T , C > ( a , b , getChangeOp ) { const matrix = buildMatrix ( a , b , getChangeOp ) ; return buildOps ( matrix , a , b ) ; } const CHANGE_COST = 3 ; const INSERTION_COST = 2 ; const DELETION_COST = 2 ; type MatrixOp < T , C > = BasicOperation < T > | { kind : 'change' ; change : C ; } | { kind : 'nop' ; } ; type MatrixEntry < T , C > = MatrixOp < T , C > & { totalCost : number ; predecessor ? : MatrixEntry < T , C > ; } ; function buildMatrix < T , C > ( a , b , getChangeOp ) { const matrix = new Array ( a . length + 1 ) ; matrix [ 0 ] = new Array ( b . length + 1 ) ; matrix [ 0 ] [ 0 ] = { kind : 'nop' , totalCost : 0 } ; for ( let j = 1 ; j <= b . length ; j ++ ) { matrix [ 0 ] [ j ] = insertion ( 0 , j ) ; } for ( let i = 1 ; i <= a . length ; i ++ ) { matrix [ i ] = new Array ( b . length + 1 ) ; matrix [ i ] [ 0 ] = deletion ( i , 0 ) ; for ( let j = 1 ; j <= b . length ; j ++ ) { matrix [ i ] [ j ] = minBy ( [ change ( i , j ) , insertion ( i , j ) , deletion ( i , j ) ] , e => e . totalCost ) ; } } return matrix ; function insertion ( i , j ) { const updated = b [ j - 1 ] ; const predecessor = matrix [ i ] [ j - 1 ] ; const predCost = predecessor . totalCost ; if ( j > a . length ) { return { kind : 'append' , totalCost : predCost , predecessor , updated } ; } else { return { kind : 'insert' , totalCost : predCost + INSERTION_COST , predecessor , updated } ; } } function deletion ( i , j ) { const original = a [ i - 1 ] ; const predecessor = matrix [ i - 1 ] [ j ] ; const predCost = predecessor . totalCost ; return { kind : 'delete' , totalCost : predCost + DELETION_COST , predecessor , original } ; } function change ( i , j ) { const original = a [ i - 1 ] ; const updated = b [ j - 1 ] ; const predecessor = matrix [ i - 1 ] [ j - 1 ] ; const predCost = predecessor . totalCost ; const change = getChangeOp ( original , updated ) ; if ( change !== undefined ) { return { kind : 'change' , totalCost : predCost + CHANGE_COST , predecessor , change } ; } else { return { kind : 'nop' , totalCost : predCost , predecessor } ; } } } function minBy < T > ( arr , value ) { let min = arr [ 0 ] ; let minValue = value ( min ) ; for ( const item of arr ) { const itemValue = value ( item ) ; if ( itemValue < minValue ) { min = item ; minValue = itemValue ; } } return min ; } function buildOps < T , C > ( matrix , a , b ) { const ops = [ ] ; let entry = matrix [ a . length ] [ b . length ] ; while ( entry !== undefined ) { if ( entry . kind === 'change' ) { ops . unshift ( entry . change ) ; } else if ( entry . kind !== 'nop' ) { ops . unshift ( entry ) ; } entry = entry . predecessor ; } return ops ; }