JSON配列内の移動したアイテムの検出

配列要素が変更されずに位置だけ変わった場合、ナイーブなdiffアルゴリズムはそれを古いインデックスでの削除と新しいインデックスでの追加として報告します。移動検出は、このパターンを認識し、代わりに単一の「移動」操作として報告する高度な機能です。

移動検出の問題:

// 変更前
{
  "steps": [
    { "id": "build", "name": "Build" },
    { "id": "test", "name": "Test" },
    { "id": "lint", "name": "Lint" },
    { "id": "deploy", "name": "Deploy" }
  ]
}

// 変更後
{
  "steps": [
    { "id": "lint", "name": "Lint" },
    { "id": "build", "name": "Build" },
    { "id": "test", "name": "Test" },
    { "id": "deploy", "name": "Deploy" }
  ]
}

移動検出なし（インデックスベースのdiff）：

• インデックス0：build から lint に変更
• インデックス1：test から build に変更
• インデックス2：lint から test に変更

これはノイズが多く、実際の変更を隠します：lint がインデックス2からインデックス0に移動しました。

移動検出あり（id を使用したIDベースのdiff）：

• lint：インデックス2からインデックス0に移動

これは発生した単一の並べ替え操作を正確に表現します。

移動検出の仕組み:

1. IDマッチング: アルゴリズムはまず一意の識別子（id など）を使用して、両方の配列間で要素をマッチングします。
2. 位置比較: マッチした要素のインデックスが比較されます。異なるインデックスの要素が移動操作の候補です。
3. LCS最適化: マッチした要素の最長共通部分列が、どの要素がその場に留まり、どの要素が移動したかを決定します。

RFC 6902 JSON Patch:

JSON Patch標準は "move" 操作を含みます：

{ "op": "move", "from": "/steps/2", "path": "/steps/0" }

これは特に大きな配列では、別々のremove+add操作よりもコンパクトで効率的です。

移動検出が重要な場面:

• CI/CDパイプラインステップ: ビルドステップの並べ替えは、明確に可視化されるべき一般的な変更です。
• 優先度リスト: 優先度によって並べ替えられるタスクやキューアイテム。
• カラムレイアウト: 表示カラムの順序が変わるUI設定。