【JavaScript】 テキスト差分をWuらによるO(NP)アルゴリズムで算出してみる

const max = Math.max;
const AlgorithmCompare = () =>{
    const fp = [];
    for( let i = -(M+1) ; i <= N+1 ; i ++ ) fp[i] = -1;
    let p = -1;

    do{
        p ++;
        for( let k = -p ; k <= Δ -1 ; k ++ )  // ループ１
            fp[ k ] = snake( k, max( fp[ k - 1 ] + 1, fp[ k + 1 ] ) );
        for( let k = Δ + p ; k >= Δ + 1 ; k -- ) // ループ２
            fp[ k ] = snake( k, max( fp[ k - 1 ] + 1, fp[ k + 1 ] ) );
        fp[ Δ ] = snake( Δ, max( fp[ Δ - 1 ] + 1, fp[ Δ + 1 ] ) ); // Δの処理
    }while( fp[Δ] !== N );

    return Δ + 2 * p;
};
const snake = ( k , y ) =>{
    let x = y - k;
    while ( x < M && y < N && A[ x ] === B[ y ] ){
        x ++;y ++;
    }
    return y;
};

const [A,B] = text1.length < text2.length ? [text1,text2] : [text2,text1];
const [M,N] = [A.length , B.length];
const Δ = N - M;

while( fp[Δ] !== N );

const fp = [];
const path = [];

const AlgorithmCompare = () =>{
    for( let i = -(M+1) ; i <= N+1 ; i ++ ) fp[i] = {y:-1,previous:-1};
    path.length = 0;
    let p = -1;

    do{
        p ++;
        for( let k = -p ; k <= Δ -1 ; k ++ )
            fp[ k ].y = snake( k, max( fp[ k - 1 ].y + 1, fp[ k + 1 ].y ) );
        for( let k = Δ + p ; k >= Δ + 1 ; k -- )
            fp[ k ].y = snake( k, max( fp[ k - 1 ].y + 1, fp[ k + 1 ].y ) );
        fp[ Δ ].y = snake( Δ, max( fp[ Δ - 1 ].y + 1, fp[ Δ + 1 ].y ) );
    }while( fp[Δ].y !== N );

    return getSes( );
};
const snake = ( k , y ) =>{
    let x = y - k;
    const [sx,sy] = [x,y];
    while ( x < M && y < N && A[ x  ] === B[ y ] ){
        x ++;y ++;
    }
    const leftOrRight = fp[ k - 1 ].y + 1 >= fp[ k + 1 ].y ? -1 : 1;
    const previous = fp[ k + leftOrRight ].previous;

    if( sx !== x ){
        fp[ k ].previous = path.length;
        path.push( { endX : x-1 , endY : y -1 , length : x - sx ,previous:previous });
    }else{
        fp[ k ].previous = previous;
    }

    return y;
};
const DELETE = Symbol();
const INSERT = Symbol();
const COMMON = Symbol();

const getSes = () =>{
    const result = [];
    let [cX,cY] = [M-1,N-1];
    let [sX,sY] = [-1,-1];
    let previous = fp[ Δ ].previous;

    while (previous !== -1) {

        const {endX,endY,length} = path[ previous ];
        [sX,sY] = [endX - length +1,endY - length +1];

        if( cX !== endX ) result.push( {s:endX +1 , e:cX , flg:DELETE });
        if( cY !== endY ) result.push( {s:endY +1 , e:cY , flg:INSERT });
        result.push( {s:sX , e:endX , flg:COMMON });

        [cX,cY] = [sX-1,sY-1];
        previous = path[ previous ].previous;
    }
    if( sX !== 0) result.push( {s:0 , e:cX , flg:DELETE });
    if( sY !== 0) result.push( {s:0 , e:cY , flg:INSERT });
    result.reverse()
    return result;
}

const printSes = algorithmCompareResult => algorithmCompareResult.forEach( e=>{
    const data = {
        [DELETE] :{pre:"-",text:text1},
        [INSERT] :{pre:"+",text:text2},
        [COMMON] :{pre:" ",text:text1}
    }[ e.flg ];
    console.log( data.pre + data.text.substring( e.s,e.e+1) );
});
printSes( AlgorithmCompare() );

const getText = r => ({
    [DELETE] :text1,
    [INSERT] :text2,
    [COMMON] :text1
}[ r.flg ]).substring( r.s,r.e+1)

const processingSes = AlgorithmCompareResult => AlgorithmCompareResult.reduce(
    (a ,b , index )=>{
        if( a.insertChar !== null ){
            if( b.flg !== COMMON) a.data.push(  { s:b.s - 1, e:b.e-1 , flg:b.flg} );
            else {
                a.data.push(  { s:b.s - 1, e:b.e , flg:b.flg} );
                a.insertChar = null;
            }
            return a;
        }
        if( b.flg === COMMON && b.s === b.e ){
            const next1 = AlgorithmCompareResult[index+1];
            const next2 = AlgorithmCompareResult[index+2];
            if( next1 !== undefined && next2 !== undefined &&
                next1.flg !==  COMMON && next2.flg ===  COMMON){
                    const [t1,t2] = [ getText( b ) , getText( next1 )];
                    if( t2.endsWith(t1) ) {
                        a.insertChar = t1;return a;
                    }
            }
        }
        a.data.push( b );
        return a;
    },{ insertChar:null,data:[]}).data;

printSes( processingSes( result ) );

const getText = r => ({
    [DELETE] :text1,
    [INSERT] :text2,
    [COMMON] :text1
}[ r.flg ]).substring( r.s,r.e+1)

const processingSesTag = AlgorithmCompareResult =>{

    const workObj = {cp1:0,cp2:0, // 現在の文字位置
        ltPos:{index:-1,position:0,tp1:0,tp2:0},  // 開始タグ"<"の位置
        result:[],
        cp1Add:function (b){ this.cp1 += b.e - b.s + 1;return this;}, // text1の文字位置を進める
        cp2Add:function (b){ this.cp2 += b.e - b.s + 1;return this;}, // text2の文字位置を進める
        cpAdd:function (b){ return this.cp1Add(b).cp2Add(b);}
    };

    return AlgorithmCompareResult.reduce(
        (a,b)=>{
            const result = a.result;
            result.push( b );
            switch ( b.flg ){
                case DELETE:return a.cp1Add(b);
                case INSERT:return a.cp2Add(b);
                case COMMON:break;
                default:throw new TypeError("入力データ不正");
            }

            const ltPos = a.ltPos;

            const b2 = ltPos.index === -1 ? b : (()=>{
                  // ">"が最初に現れるとき、閉じタグとみなす
                const text = getText(b);
                const [lt,gt] = [text.indexOf("<"),text.indexOf(">")];
                if( gt >= lt ) return b;

                const {index,position,tp1,tp2} = ltPos;

                  // 編集データを再構成する
                const w = result[index];
                result.length = index;
                if( position > 0 ) result.push( {s:w.s,e:w.s+position-1,flg:COMMON} );
                result.push( {s:tp1 + position,e:a.cp1+gt,flg:DELETE}
                            , {s:tp2 + position,e:a.cp2+gt,flg:INSERT} );
                const afterCOMMON =  text.length === gt + 1 ? null :
                    { s:b.s + gt + 1,e:b.e,flg:COMMON};
                if( afterCOMMON !== null ) result.push( afterCOMMON );
                ltPos.index = -1;
                return afterCOMMON;
            })();

            if( b2 === null ) return a.cpAdd(b);
               // 文字列に閉じられていないタグがあるか確認
            const text = getText(b2);
            const [lt,gt] = [text.lastIndexOf("<"),text.lastIndexOf(">")];
            if( lt > gt ){ // タグ開始位置保存
                ltPos.index = result.length -1;
                ltPos.position = lt;ltPos.tp1 = a.cp1;ltPos.tp2 = a.cp2;
            }
            return a.cpAdd(b);
        },workObj
    ).result;
};

const text1 = "<div><p>テスト</p></div>";
const text2 = "<div><p id=\"id1\">テスト</p></div>";

printSes( processingSesTag( AlgorithmCompare() ) );

const onp = (()=>{
    const TEXT_SWAPPED  = true;
    const DELETE = 1;
    const INSERT = 2;
    const COMMON = 0;

    const onp = ( text1 , text2 ) => {

        const onpFUnc = {
            exec : function( text1 , text2  ){
                return this.initOnp( text1 , text2 ).onpMain().getSes();
            },
            initOnp :function (text1,text2) {  // 初期化
                                    
                const allocBuff = (size,intVal) =>(new Int32Array(size)).fill(intVal);

                const [M,N] = [text1.length,text2.length];
                const data = M > N ? {textX:text2,textY:text1,M:N,N:M,swappedFlg:TEXT_SWAPPED}
                    : {textX:text1,textY:text2,M:M,N:N,swappedFlg:!TEXT_SWAPPED};
                const flg = data.swappedFlg ? { ses_insert:DELETE,ses_delete:INSERT , commonType:onp.flg.TEXT2}
                    : { ses_insert:INSERT,ses_delete:DELETE , commonType:onp.flg.TEXT1}
                const size = M + N + 3;
                this.onpData = {
                    fp:allocBuff(size,-1) ,
                    pathRef:allocBuff(size,-1) ,
                    path:[],
                    offset : data.M + 1,
                    delta : data.N - data.M,
                    data : data,
                    flg : flg
                };
                return this;
            },
            onpMain : function(){

                const { fp , pathRef , path , offset , delta } = this.onpData;
                const { textX , textY , M , N  } = this.onpData.data;

                const snake = ( k ) => {
                    const kOffset = k + offset;
                    const kOffsetMinus = kOffset -1;
                    const kOffsetPlus = kOffset +1;

                    const p1 = fp[kOffsetMinus]+1;
                    const p2 = fp[kOffsetPlus];

                    let [previous,py] = p1 > p2 ? [pathRef[kOffsetMinus], p1]
                        :[ pathRef[kOffsetPlus] ,p2]

                    let px = py - k;
                    const sx = px;

                    while (px < M && py < N && textX[px] === textY[py]) {
                        px++;py++;
                    }

                    if( sx !== px ){
                        pathRef[kOffset] = path.length;
                        path.push( {endX:px-1, endY:py-1 , length:px-sx ,previous:previous } );
                    }else{
                        pathRef[kOffset] = previous;
                    }

                    fp[kOffset] = py;
                    return py;
                };

                let k,P;
                for (P = 0; P <= M; P++) {
                    for ( k = -P; k < delta; k++) snake(k);
                    for ( k = delta + P; k > delta; k--) snake(k);
                    if( snake(delta) === N ) break;
                }
                this.onpData.fp = null; // 参照オフ（気休め）
                return this;
            },
            getSes:function (){

                const epcData = [];

                const {  pathRef , path ,delta , offset } = this.onpData;
                const {  M , N  } = this.onpData.data;
                const { ses_insert ,  ses_delete } = this.onpData.flg;
                const ses_common = COMMON;

                let [cX,cY] = [M-1,N-1];
                let [sX,sY] = [-1,-1];
                let previous = pathRef[delta+offset];

                while (previous !== -1) {
                    let epc = path[previous];
                    const {endX,endY,length} = epc;
                    [sX,sY] = [endX - length +1,endY - length +1];

                    if( cX !== endX ) epcData.push( {s:endX +1 , e:cX , flg:ses_delete });
                    if( cY !== endY ) epcData.push( {s:endY +1 , e:cY , flg:ses_insert });
                    epcData.push( {s:sX , e:endX , flg:ses_common });

                    [cX,cY,previous] = [sX-1,sY-1,epc.previous];
                }
                if( sX !== 0) epcData.push( {s:0 , e:sX , flg:ses_delete });
                if( sY !== 0) epcData.push( {s:0 , e:sY , flg:ses_insert });
                epcData.reverse()

                this.onpData.pathRef = this.onpData.path = null; // 参照オフ（気休め）
                return {commonType:this.onpData.flg.commonType ,data:epcData};
            }
        };
        return  onpFUnc.exec( text1 , text2 ) ;
    };
    Object.defineProperty( onp ,"flg" , {
        writable:false,
        value:Object.freeze( {
            TEXT1 :  DELETE,
            TEXT2 :  INSERT,
            COMMON : COMMON
        })
    });
    return onp;
})();

const text1 = "JavaScriptかJSか？";
const text2 = "JSはJavascriptのことか？";

const result = onp( text1 , text2 );
const commonText = result.commonType ===  onp.flg.TEXT2 ? text2 : text1;

result.data.forEach( e=>{
    switch (e.flg){
        case onp.flg.TEXT2:
            console.log( "+" + text2.substring(e.s,e.e+1) );
            return;
        case onp.flg.TEXT1:
            console.log( "-" + text1.substring(e.s,e.e+1) );
            return
        case onp.flg.COMMON:
             console.log( " " + commonText.substring(e.s,e.e+1) );
            break;
    }
});