Published on

Delta 的合并算法

Authors

如果 Delta 不断膨胀，如何删除冗余操作，使其更加紧凑？

🛠 如何优化 Delta 以减少冗余操作并保持紧凑？

随着 Delta 记录的变更操作不断增加，数据结构会逐渐膨胀，导致 存储占用增加、编辑响应变慢、渲染性能下降。为了解决这个问题，我们可以使用 优化策略 来删除冗余操作，使 Delta 更加紧凑。

🔍 1. Delta 膨胀的根本原因

❓ 为什么 Delta 会变得越来越大？

  1. 重复的 retain 操作

    • 多次应用样式变更（如加粗/取消加粗）会产生冗余 retain。

  2. 重复的 insert 操作未合并

    • 例如用户多次插入文本 "Hello " 和 "World"，但 Delta 仍然记录多个 insert 而不是合并它们。

  3. 无效的 delete 操作

    • 某些 delete 操作可能已经被后续操作覆盖，但仍然存在于 Delta 中。

  4. 撤销/重做导致的重复变更

    • 用户多次撤销/重做时，Delta 可能会存储多个版本的相同修改，造成数据膨胀。

🚀 2. 关键优化策略

✅ 2.1 合并连续的 insert 操作

当 Delta 里有多个相邻的 insert，可以将它们合并成一个单一 insert。

优化前

[
  { "insert": "Hello" },
  { "insert": " World" }
]

优化后

[
  { "insert": "Hello World" }
]

如何实现？

function mergeInsert(delta) {
  let newDelta = [];
  for (let i = 0; i < delta.length; i++) {
    if (i > 0 && "insert" in delta[i] && "insert" in delta[i - 1]) {
      newDelta[newDelta.length - 1].insert += delta[i].insert;
    } else {
      newDelta.push(delta[i]);
    }
  }
  return newDelta;
}

✅ 2.2 合并连续的 retain 操作

如果多个 retain 共享相同的 attributes，它们可以合并。

优化前

[
  { "retain": 5, "attributes": { "bold": true } },
  { "retain": 5, "attributes": { "bold": true } }
]

优化后

[
  { "retain": 10, "attributes": { "bold": true } }
]

实现方式

function mergeRetain(delta) {
  let newDelta = [];
  for (let i = 0; i < delta.length; i++) {
    if (
      i > 0 &&
      "retain" in delta[i] &&
      "retain" in delta[i - 1] &&
      JSON.stringify(delta[i].attributes) === JSON.stringify(delta[i - 1].attributes)
    ) {
      newDelta[newDelta.length - 1].retain += delta[i].retain;
    } else {
      newDelta.push(delta[i]);
    }
  }
  return newDelta;
}

✅ 2.3 移除不必要的 delete 操作

如果 delete 操作已经删除了部分文本，而之后的 delete 操作仍在尝试删除已不存在的内容，则这些 delete 可以被移除。

优化前

[
  { "delete": 5 },
  { "delete": 5 }
]

优化后

[
  { "delete": 10 }
]

实现方式

function mergeDelete(delta) {
  let newDelta = [];
  for (let i = 0; i < delta.length; i++) {
    if (i > 0 && "delete" in delta[i] && "delete" in delta[i - 1]) {
      newDelta[newDelta.length - 1].delete += delta[i].delete;
    } else {
      newDelta.push(delta[i]);
    }
  }
  return newDelta;
}

✅ 2.4 使用 Delta.compose() 进行增量合并

Delta.compose() 是 Quill.js 提供的合并函数，它能自动优化 Delta 结构，减少冗余操作。

示例

const delta1 = new Delta().insert("Hello ");
const delta2 = new Delta().insert("World");

const merged = delta1.compose(delta2);
console.log(merged);

结果

[
  { "insert": "Hello World" }
]

✅ compose() 能自动合并 insert、delete 和 retain，大幅减少冗余。

✅ 2.5 采用 Delta.transform() 解决冲突

当多用户协作编辑时，可能出现冲突的 Delta，Delta.transform() 允许不同的 Delta 版本合并，并正确调整文本偏移量。

示例

const deltaA = new Delta().retain(5).insert("X");
const deltaB = new Delta().insert("Y");

const transformed = deltaA.transform(deltaB, true);
console.log(transformed);

Delta.transform() 使协作编辑更加流畅，避免数据膨胀。

✅ 2.6 定期快照并清理历史

当 Delta 变得过大，可以定期生成 快照（Snapshot），并丢弃历史变更。

实现方式

  1. 每 1000 次操作，保存当前 Delta 快照。
  2. 清理超过 1000 条的 insert、delete 记录，仅保留最终文本和格式。
  3. 恢复时，直接从最近的快照加载，而不是逐步回放 Delta 变更。

🎯 3. 组合优化策略

我们可以将所有优化策略整合到一个方法中，使 Delta 保持紧凑。

function optimizeDelta(delta) {
  delta = mergeInsert(delta);
  delta = mergeRetain(delta);
  delta = mergeDelete(delta);
  return delta;
}

🏆 4. 测试优化效果

我们创建一个测试文档，并应用优化策略，看看 Delta 变得多么紧凑。

测试数据

[
  { "insert": "Hello " },
  { "insert": "World" },
  { "retain": 5, "attributes": { "bold": true } },
  { "retain": 5, "attributes": { "bold": true } },
  { "delete": 5 },
  { "delete": 5 }
]

优化后

[
  { "insert": "Hello World" },
  { "retain": 10, "attributes": { "bold": true } },
  { "delete": 10 }
]

🔥 5. 关键结论

优化方法效果
合并 insert减少文本重复存储，降低存储占用。
合并 retain避免不必要的格式变更，提高解析效率。
合并 delete减少多余的删除记录，优化撤销操作。
使用 Delta.compose()自动优化 Delta，减少代码复杂度。
采用 Snapshot避免 Delta 变得过大，提升恢复速度。

✅ 通过以上优化，我们可以让 Delta 保持紧凑，减少存储开销，并提升文本编辑性能！ 🚀

通过什么算法可以让已经验证膨胀的 Delta 数据快速变得紧凑？

📌 让膨胀的 Delta 数据快速变得紧凑的算法

当 Delta 数据由于长时间编辑、撤销/重做、协作编辑而膨胀，我们需要高效的算法来去除冗余，优化存储，提升性能。
以下是几种可行的优化算法：

🚀 1. Delta 数据紧凑化的核心目标

  1. 合并冗余 insert 操作
  2. 合并冗余 retain 操作（样式变更）
  3. 合并冗余 delete 操作
  4. 删除无效 retain 和 delete（避免无意义的占位符）
  5. 基于快照裁剪历史变更
  6. 高效计算 Delta 差异，去除重复变更

🔍 2. 可用算法

算法作用适用场景
Delta Compose 合并合并连续的 insert 和 retain适用于局部优化
Sliding Window 滑动窗口遍历 Delta 并合并相邻操作适用于整个 Delta 结构紧凑化
Run-Length Encoding压缩重复 retain 操作适用于格式变更过多的文档
Undo Pruning（撤销修剪）删除无法重用的历史记录适用于频繁撤销/重做的编辑
Delta Fast Forward直接应用所有操作并保存最终状态适用于超大 Delta 数据优化

📌 3. 关键算法实现

🛠 3.1 Delta Compose 合并

核心思想：遍历 Delta，合并相邻的 insert、retain 和 delete 操作。

🔧 实现

function compactDelta(delta) {
  let newDelta = [];
  let prevOp = null;

  for (const op of delta) {
    if (prevOp) {
      if ("insert" in op && "insert" in prevOp) {
        // 合并连续的 insert
        prevOp.insert += op.insert;
        continue;
      }
      if ("retain" in op && "retain" in prevOp && JSON.stringify(op.attributes) === JSON.stringify(prevOp.attributes)) {
        // 合并连续的 retain
        prevOp.retain += op.retain;
        continue;
      }
      if ("delete" in op && "delete" in prevOp) {
        // 合并连续的 delete
        prevOp.delete += op.delete;
        continue;
      }
    }
    newDelta.push(op);
    prevOp = op;
  }
  return newDelta;
}

✨ 优化前

[
  { "insert": "Hello " },
  { "insert": "World" },
  { "retain": 5, "attributes": { "bold": true } },
  { "retain": 5, "attributes": { "bold": true } },
  { "delete": 3 },
  { "delete": 2 }
]

⚡ 优化后

[
  { "insert": "Hello World" },
  { "retain": 10, "attributes": { "bold": true } },
  { "delete": 5 }
]

🏃‍♂️ 3.2 Sliding Window（滑动窗口）

核心思想：维护一个固定大小的窗口，每次检查 Delta 是否可以优化。

🔧 实现

function slidingWindowCompact(delta, windowSize = 3) {
  let optimizedDelta = [];
  let buffer = [];

  for (const op of delta) {
    buffer.push(op);
    if (buffer.length >= windowSize) {
      buffer = compactDelta(buffer);
    }
  }

  return optimizedDelta.concat(compactDelta(buffer));
}

✨ 优势

  • ✅ 适用于大规模 Delta 数据。
  • ✅ 在 O(n) 复杂度内完成压缩，避免一次性处理过大数据导致的性能问题。

🏗 3.3 Run-Length Encoding（RLE）

核心思想：压缩重复的 retain 记录，以减少 Delta 体积。

🔧 实现

function rleCompressRetain(delta) {
  let newDelta = [];
  let lastOp = null;

  for (const op of delta) {
    if ("retain" in op && lastOp && "retain" in lastOp && JSON.stringify(op.attributes) === JSON.stringify(lastOp.attributes)) {
      lastOp.retain += op.retain;
    } else {
      newDelta.push(op);
      lastOp = op;
    }
  }
  return newDelta;
}

✨ 优化前

[
  { "retain": 5, "attributes": { "bold": true } },
  { "retain": 5, "attributes": { "bold": true } }
]

⚡ 优化后

[
  { "retain": 10, "attributes": { "bold": true } }
]

🔥 3.4 Undo Pruning（撤销修剪）

核心思想：删除 Delta 中无法重做的 undo 记录，减少数据冗余。

🔧 实现

function pruneUndoHistory(delta, maxUndoSteps = 50) {
  return delta.slice(-maxUndoSteps);
}

✨ 优势

  • 适用于撤销/重做频繁的应用。
  • 避免 Delta 无限制增长。

🚀 3.5 Delta Fast Forward

核心思想：应用所有 Delta 操作，生成最终文本，并仅存储最终版本。

🔧 实现

function fastForwardDelta(delta) {
  let text = "";
  let attributes = {};
  
  for (const op of delta) {
    if (op.insert) text += op.insert;
    if (op.attributes) attributes = { ...attributes, ...op.attributes };
  }
  
  return [{ "insert": text, "attributes": attributes }];
}

✨ 优势

  • 适用于超大 Delta 数据集。
  • 直接计算最终文本，避免存储大量历史操作。

📊 4. 方案对比

优化算法时间复杂度适用场景适用 Delta 规模
Delta ComposeO(n)适用于常规 Delta 合并优化小型-中型
Sliding WindowO(n)适用于大数据流的 Delta 处理大型
Run-Length EncodingO(n)适用于大量格式变更的 Delta中型-大型
Undo PruningO(1)适用于撤销/重做操作优化大型
Delta Fast ForwardO(n)适用于完全裁剪历史，仅保留最终状态超大型

🎯 5. 结论

✅ 最佳策略

  1. 小型 Delta（≤ 1KB）：
    • 直接使用 Delta.compose() 合并操作。
  2. 中型 Delta（1KB ~ 1MB）：
    • 采用 Sliding Window 避免一次性处理过多数据。
  3. 大型 Delta（>1MB）：
    • 结合 Run-Length Encoding、Undo Pruning 和 Fast Forward。
  4. 超大 Delta（>10MB）：
    • 直接裁剪历史，仅存最终版本！

🔥 最终结论：

合理的 Delta 结构优化可以有效减少 30%~90% 的存储占用，并提高富文本编辑器的性能！ 🚀

Discuss on Twitter • View on GitHub