/takker/O(NP) algorithm - Scrapbox Reader

generated at 2/16/2025, 12:30:27 PM
O(NP) algorithm
O(ND) algorithmより高速なdiff algorithm
論文

用語メモ
このalgorithmではなく、編集距離で使われる一般的な用語だけど
SES: shortest edit script
ある要素列を別の要素列に変換するための最短手順
LCS: longest common subsequence
最長共通部分列
from diffの動作原理を知る～どのようにして差分を導き出すのか：一般記事｜gihyo.jp … 技術評論社

考え方
D=\Delta+2p
D: 編集距離
\Delta: 二つの要素列の長さの差
p: SES中の削除の合計数
一般的な解説
二つの要素列のうち、短い方をA、長い方をBとする
AからBに変換するには、AとBの長さの差(\Delta)だけ挿入したあと、Bと同じになるまで要素を置換(削除&挿入 x p回)すればいい
よって、編集距離は挿入(コスト1)と置換(コスト2)の合計値\Delta+2pとなる
これ以上編集距離を縮めることはできない
証明は論文読んだら書く
例
 cosense を helpfeel に変換するには、少なくとも1文字追加して0~7文字挿入&削除する必要がある
これ以上追加操作を減らせないし、挿入＆削除操作の回数範囲を狭くすることもできない
この1が\Deltaに、0~7がpに相当する

References
差分検出アルゴリズム三種盛り - Object.create(null)
この記事のV_D(k)が下のコードの fp に該当する
https://github.com/cubicdaiya/onp/blob/master/javascript/onp.js
https://qiita.com/convto/items/8faf530d304024a22769
via /Mijinko-other/O(NP)アルゴリズム
この記事知らなかった


https://github.com/cubicdaiya/onp/blob/master/javascript/onp.js をrefactoringしたもの
ライセンスがよくわからない
k,x,yの意味を理解したい
mod.ts/**
 * The algorithm implemented here is based on "An O(NP) Sequence Comparison Algorithm"
 * by described by Sun Wu, Udi Manber and Gene Myers */

/** LICENSE: https://github.com/cubicdaiya/onp/blob/master/COPYING */

type Position = {
  x: number;
  y: number;
};
export interface Change<T> {
  value: T;
  type: "add" | "delete" | "common";
}

export interface DiffResult<T> {
  from: ArrayLike<T>;
  to: ArrayLike<T>;
  editDistance: number;
  buildSES(): Generator<Change<T>, void, unknown>;
}


export const diff = <T>(
  left: ArrayLike<T>,
  right: ArrayLike<T>,
): DiffResult<T> => {
  const reversed = left.length > right.length;
  const a = reversed ? right : left;
  const b = reversed ? left : right;
  
  const offset = a.length + 1;
  const MAXSIZE = a.length + b.length + 3;
 path はkから snake() で計算した座標が入っている pathpos の要素番号を取得する函数に相当するもの
 pathpos と path で単方向リストを実現しているっぽい？
なぜそんなことをしているかはまだわからない
変更がたくさんあると pathpos の要素数が500とか600に膨れ上がる
mod.ts  const path = new Array<number>(MAXSIZE);
  path.fill(-1);
  const pathpos = [] as [Position, number][];

  const snake = (k: number, p: number, pp: number) => {
    let y = Math.max(p, pp);
    let x = y - k;
同じ値が入っている要素番号を計算する
mod.ts    while (x < a.length && y < b.length && a[x] === b[y]) {
      ++x;
      ++y;
    }

    path[k + offset] = pathpos.length;
    pathpos.push([{ x, y }, path[k + (p > pp ? -1 : +1) + offset]]);
xはkとyから計算できるの(x=y-k)で返さなくていい
mod.ts    return y;
  };

編集距離を計算しつつ、辿った経路を記録する
mod.ts  const fp = new Array<number>(MAXSIZE);
  fp.fill(-1);
  let p = -1;
  const delta = b.length - a.length;
  do {
    ++p;
探索範囲は-p\le k\le\Delta+pで十分
それ以外の領域は編集距離Dが\Delta+2pを越えてしまうので、求める解が存在しない
配列の添え字に負の値は使えないので、 offset を足して正にしている
mod.ts    for (let k = -p; k <= delta - 1; ++k) {
      fp[k + offset] = snake(k, fp[k - 1 + offset] + 1, fp[k + 1 + offset]);
    }
    for (let k = delta + p; k >= delta + 1; --k) {
      fp[k + offset] = snake(k, fp[k - 1 + offset] + 1, fp[k + 1 + offset]);
    }
    fp[delta + offset] = snake(delta, fp[delta - 1 + offset] + 1, fp[delta + 1 + offset]);
f_p(\Delta)がBの長さと同じになったら終了
mod.ts  } while (fp[delta + offset] !== b.length);
最短経路の座標リストを作る
mod.ts  const epc = [] as Position[];
  {
    let r = path[delta + offset];
    while (r !== -1) {
      epc.push(pathpos[r][0]);
      r = pathpos[r][1];
    }
  }
mod.ts  console.log({ path, pathpos, epc });
  
  return {
    from: left,
    to: right,
    editDistance: delta + p * 2,

計算した経路を辿ってSESを構築する函数
mod.ts    buildSES: function* () {
      let xIndex = 0;
      let yIndex = 0;
      for (const { x, y } of reverse(epc)) {
        while (xIndex < x || yIndex < y) {
          if (y - x > yIndex - xIndex) {
            yield { value: b[yIndex], type: reversed ? "delete" : "add" };
            ++yIndex;
          } else if (y - x < yIndex - xIndex) {
            yield { value: a[xIndex], type: reversed ? "add" : "delete" };
            ++xIndex;
          } else {
            yield { value: a[xIndex], type: "common" };
            ++xIndex;
            ++yIndex;
          }
        }
      }
    },
  };
};

配列を逆順にiterateするhelper函数
mod.tsfunction* reverse<T>(list: ArrayLike<T>): Generator<T, void, unknown> {
  for (let i = list.length - 1; i >= 0; i--) {
    yield list[i];
  }
}

表示用
cli.tsimport { Command } from "https://deno.land/x/cliffy@v0.19.2/command/mod.ts";
import { diff } from "./mod.ts";

const { args, options } = await new Command()
  .name("diff")
  .version("0.1.0")
  .description(
    "O(NP) algorithmによる文字列差分表示のテストプログラム",
  )
  .arguments("<left> <right>")
  .option("--vertical", "差分を縦に表示する")
  .parse(Deno.args);

const left = String(args[0]);
const right = String(args[1]);
const { buildSES, from, to } = diff(left, right);
console.log(`${from} → ${to}`);
if (options?.vertical) {
  console.log(
    [...buildSES()].map(({ value, type }) =>
      type === "add"
        ? `+ ${value}`
        : type === "delete"
        ? `- ${value}`
        : `  ${value}`
    ).join("\n"),
  );
} else {
  let signs = "";
  let str = "";
  for (const {value, type} of buildSES()) {
    str += value;
    const half = value
    switch (type) {
      case "add":
        signs += "+";
        break;
      case "delete":
        signs += "-";
        break;
      default:
        signs += " ";
        break;
    }
  }
  console.log(`${signs}\n${str}`);
}
shdeno run "https://scrapbox.io/api/code/takker/O(NP)_algorithm/cli.ts" sitting kitten
log{
  path: [
    -1, -1, -1, -1, -1,  6,
     7,  8, 11, 10,  9, -1,
    -1, -1, -1, -1
  ],
  pathpos: [
    [ { x: 0, y: 0 }, -1 ],
    [ { x: 0, y: 1 }, 0 ],
    [ { x: 1, y: 0 }, 0 ],
    [ { x: 4, y: 4 }, 1 ],
    [ { x: 0, y: 2 }, 1 ],
    [ { x: 4, y: 5 }, 3 ],
    [ { x: 2, y: 0 }, 2 ],
    [ { x: 5, y: 4 }, 3 ],
    [ { x: 6, y: 6 }, 5 ],
    [ { x: 0, y: 3 }, 4 ],
    [ { x: 4, y: 6 }, 5 ],
    [ { x: 6, y: 7 }, 8 ]
  ],
  epc: [
    { x: 6, y: 7 },
    { x: 6, y: 6 },
    { x: 4, y: 5 },
    { x: 4, y: 4 },
    { x: 0, y: 1 },
    { x: 0, y: 0 }
  ]
}
kitten → sitting
+ s
- k
  i
  t
  t
+ i
- e
  n
+ g

#2024-06-09 05:23:46 
#2023-02-02 10:11:11 
#2021-10-28 12:46:45 
#2021-10-25 19:35:25 
#2021-10-20 08:00:53